Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| ??? | ??? | ??? | ??? | F |
| 1 | 1 | 0 | ||
| 1 | 0 | |||
| 1 | 1 | 0 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 2 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Заметим, что в каждом столбце, кроме третьего, как минимум в одной строке встречается 1. Часть логического выражения
Переменные y и w не должны одновременно принимать значение 1. Следовательно, переменной y соответствует первый столбец, а переменной w соответствует второй столбец. Значит, четвёртый столбец фрагмента таблицы истинности соответствует переменной x.
Приведем другое решение.
Составим таблицу истинности для выражения ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)) вручную или при помощи языка 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 not(((x <= y) and (y <= w)) or (z == (x or y))):
print(x, y, z, w)
Далее выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке х, y, z,w.
Получим следующие наборы:
(0, 1, 0, 0),
(1, 0, 0, 0),
(1, 0, 0, 1),
(1, 1, 0, 0).
Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.
Заметим, что ни в одном из наборов переменная z не принимает единичное значение. Следовательно, переменной z соответствует третий столбец, и во всех строчках таблицы в третьем столбце стоит 0.
Переменная w принимает единичное значение только в одном наборе. Следовательно, переменной w соответствует второй столбец, и в первой и второй сточках таблицы во втором столбце стоит 0.
Третья строка таблицы, в которой переменная w принимает единичное значение, соответствует набору (1, 0, 0, 1). В этом наборе единичное значение принимает также переменная х. Следовательно, переменной х соответствует четвертый столбец.
Тогда первый столбец соответствует переменной у.
Ответ: ywzx.
Приведем решение Коломеец Юрия при помощи программы, которая сразу выдает ответ без промежуточных этапов. Программа из 24 строк, что для трехминутного задания многовато, но решение работает.
from random import *
s = []
null = lambda x, y, z, w: True if ((not x or y) and (not y or w)) or (z == (x or y)) else False # ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
act = True
while act:
active = 0
f = [randint(0,1) for i in range(4)]
if f[0] == 1 and f[3] == 1 and len(s) == 0:s.append(f)
if f[0] == 1 and len(s) == 1 and f not in s:s.append(f)
if f[1] == 1 and f[3] == 1 and len(s) == 2 and f not in s:s.append(f)
if len(s) == 3:
while active != 1000:
active += 1
i_x = choice([i for i in range(4)])
i_y = choice([i for i in range(4) if i != i_x])
i_z = choice([i for i in range(4) if i != i_x and i != i_y])
i_w = choice([i for i in range(4) if i != i_x and i != i_y and i != i_z])
if null(s[0][i_x], s[0][i_y], s[0][i_z], s[0][i_w]) == False:
if null(s[1][i_x], s[1][i_y], s[1][i_z], s[1][i_w]) == False:
if null(s[2][i_x], s[2][i_y], s[2][i_z], s[2][i_w]) == False and act == True:
for i in s:print(i)
print(f"Ответ: x = {i_x + 1}; y = {i_y + 1}; z = {i_z + 1}; w = {i_w + 1}")
act = False
if active == 1000:s.clear()
Приведем решение Красильникова Юрия на языке Python.
import itertools,re
def f(vars):
x,y,z,w = vars
return ((not x or y) and (not y or w)) or (z == (x or y))
matrix = ['1..10', '1...0', '.1.10']
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)]))
Приведем решение Владимира Бурмистрова на языке Python.
from itertools import *
def f(x, y, z, w):
return ((x <= y) and (y <= w)) or (z == (x or y))
for a1, a2, a3, a4, a5, a6, a7 in product([0, 1], repeat = 7):
table = [(1, a1, a2, 1), (1, a3, a4, a5), (a6, 1, a7, 1)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
if [f(**dict(zip(p, r))) for r in table] == [0, 0, 0]:
print(*p, sep='')