Логическая функция F задаётся выражением:
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
| ??? | ??? | ??? | ??? | F |
|---|---|---|---|---|
| 0 | 1 | 1 | ||
| 1 | 0 | 1 | ||
| 0 | 0 | 0 | 1 |
Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть заданы выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности.
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Составим таблицу истинности для выражения
вручную или при помощи языка Python:
print("x y z w")
for x in range(0, 2):
for y in range(0, 2):
for z in range(0, 2):
for w in range(0, 2):
if ((x==y) <= (not(z) or w)) == (not(( w <= x) or (y <= z))):
print(x, y, z, w)
Далее выпишем те наборы переменных, при которых данное выражение равно 1. В наборах переменные запишем в порядке х, y, z, w.
Получим следующие наборы:
(0, 0, 1, 0),
(0, 1, 0, 1),
(1, 1, 1, 0).
Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.
Третьей строке может соответствовать только набор (0, 0, 1, 0), тогда второй столбец соответствует переменной z.
Рассмотрим вторую строку таблицы. Поскольку второй столбец это z, то во втором столбце стоит 0, тогда строка соответствует набору (0, 1, 0, 1). Второй 0 в этом наборе соответствует переменной x, тогда четвертый столбец — это x.
Рассмотрим первую строку таблицы. Она может соответствовать набору (1, 1, 1, 0). Поскольку второй столбец это z и он равен 1. Тогда w — это 0 и соответствует первому столбцу, а y — третьему столбцу.
Ответ: wzyx.
Приведем решение Юрия Красильникова на языке Python:
import itertools,re
def f(vars):
x,y,z,w = vars
return ((x!=y)or(not z or w))!=((not w or z )or(not y or z))
matrix = ['01..1', '..101', '0.001']
numvars=len(matrix[0])-1
table=[''.join(map(str,vars)) + str(int(f(vars))) for vars in itertools.product( [0,1], repeat=numvars )]
for perm in itertools.permutations(range(numvars)):
permtable=[''.join([line[perm[i]] for i in range(numvars)])+line[-1] for line in table]
for lines in itertools.permutations(permtable,len(matrix)):
if re.search(''.join(matrix),''.join(lines)):
print(''.join(['xyzw'[perm[i]] for i in range(numvars)]))