Задание №2 — Построение таблицы истинности

Решение:

В задании известны только фрагменты трёх различных строк таблицы истинности, причём неизвестно, какая переменная стоит в каком столбце. Приём здесь всегда один: сначала выписываем все наборы, на которых функция принимает указанное значение, а затем прикладываем к ним строки фрагмента и смотрим, при каком порядке столбцов всё сходится.

Выражение $\neg y \lor ( y \rightarrow x ) \lor \neg ( z \rightarrow w )$ равно нулю, когда нулевые все слагаемые. Из $\neg y = 0$ следует $y = 1$, а тогда $(y \rightarrow x) = 0$ даёт $x = 0$. Условие $\neg ( z \rightarrow w ) = 0$ равносильно $z \rightarrow w = 1$, то есть запрещена лишь пара $z = 1,\ w = 0$. Остаются три набора:

w	x	y	z	F
0	0	1	0	0
1	0	1	0	0
1	0	1	1	0

На всех трёх наборах $x = 0$ и $y = 1$: значит, в столбце $x$ нет единиц, а в столбце $y$ нет нулей. В фрагменте единицы стоят в первом и втором столбцах, а нули — в первом, втором и третьем. Следовательно, $y$ — четвёртый столбец (единственный без нулей), а $x$ — третий (единственный из оставшихся без единиц). Во второй строке фрагмента первый столбец равен 0, а второй равен 1; среди наших наборов переменные $w$ и $z$ различаются только на наборе $w = 1,\ z = 0$, поэтому первый столбец — $z$, а второй — $w$.

Те же три набора нетрудно получить и перебором:

from itertools import product


def impl(a, b):
    return (not a) or b


def F(w, x, y, z):
    return (not y) or impl(y, x) or (not impl(z, w))


for w, x, y, z in product((0, 1), repeat=4):
    if not F(w, x, y, z):
        print(w, x, y, z)

Ответ: zwxy