📋 Условие
Миша заполнял таблицу истинности логической функции F = (x ≡ y) ∨ ((y ∨ z) → w), но успел заполнить лишь фрагмент из трёх различных её строк.
🔍 Подробное решение
Миша заполнял таблицу истинности логической функции F, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.
Решение:
Смотрим и замечаем, что у нас два действия И и результат в таблице ИСТИНА во всех случаях, отсюда делаем вывод, что все 3 части выражения должны быть истиной, т.е. 1 И 2 И 3 = 1.
Последнее выражение упрощает поиск: NOT W должно быть истиной, значит W должно быть ложью, соответственно W можно поставить только в 4 столбик.
Разберём вторую скобку (там проще). Она должна быть истинна, соответственно YZ не может стоять в позициях 1,3 и 2,3, остаётся 1 вариант — 1,2. Отсюда получаем, что X будет на 3 позиции. И укажем сразу, что Y и Z должны быть разными. Также если посмотреть на таблицу (а в таблице не может быть одинаковых строк), то оставшееся место для X будет 0.
От заполненной таблицы можем определить, что Y будет на 2 позиции. Почему? Потому что по первой скобке выражения, чтобы получилась ИСТИНА, нужно, чтобы хотя бы одна из переменных была истиной, а такое невозможно (по строке 2 таблицы), если Y будет на 1 позиции. То есть X у нас должен быть всегда 0, отсюда делаем вывод, что X стоит в третьем столбце и всегда будет 0.
Соответственно, получаем ответ: zyxw
Ответ: zyxw
Решение:
Смотрим и замечаем, что у нас два действия И и результат в таблице ИСТИНА во всех случаях, отсюда делаем вывод, что все 3 части выражения должны быть истиной, т.е. 1 И 2 И 3 = 1.
Последнее выражение упрощает поиск: NOT W должно быть истиной, значит W должно быть ложью, соответственно W можно поставить только в 4 столбик.
Разберём вторую скобку (там проще). Она должна быть истинна, соответственно YZ не может стоять в позициях 1,3 и 2,3, остаётся 1 вариант — 1,2. Отсюда получаем, что X будет на 3 позиции. И укажем сразу, что Y и Z должны быть разными. Также если посмотреть на таблицу (а в таблице не может быть одинаковых строк), то оставшееся место для X будет 0.
От заполненной таблицы можем определить, что Y будет на 2 позиции. Почему? Потому что по первой скобке выражения, чтобы получилась ИСТИНА, нужно, чтобы хотя бы одна из переменных была истиной, а такое невозможно (по строке 2 таблицы), если Y будет на 1 позиции. То есть X у нас должен быть всегда 0, отсюда делаем вывод, что X стоит в третьем столбце и всегда будет 0.
Соответственно, получаем ответ: zyxw
Ответ: zyxw
📚 Теория
Логические функции и таблицы истинности. Используем перебор всех комбинаций для восстановления таблицы.
🐍 Шаблон Python
Python
# Способ 1 — itertools
from itertools import *
def f(x, y, z, w):
# тут пишем логическое условие из задачи
return ((y and (x == (not z))) <= w) and (z <= y)
for x1, x2, x3, x4, x5 in product([0, 1], repeat=5):
# x1,x2,x3 — пропуски в таблице
# repeat = столько, сколько пропусков
t = (
(0, 0, x1, x2, 0),
(0, x3, 0, 0, 0),
(1, x4, x5, 1, 0),
) # таблица из задания
if len(t) == len(set(t)):
for p in permutations('xywz', r=4):
if all(f(**dict(zip(p, l))) == l[-1] for l in t):
print(*p)🐍 Альтернативный способ
Способ 2
# Способ 2 — вложенные циклы
print('x y z w')
for x in range(0, 2):
for y in range(0, 2):
for w in range(0, 2):
for z in range(0, 2):
if not(not((x == (not(y)))) or ((x and w) == z)):
print(x, y, z, w)