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

Решение:

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

Дизъюнкция $( x \land \neg y ) \lor ( y \equiv z ) \lor \neg w$ равна нулю только тогда, когда нулём является каждое слагаемое. Из $\neg w = 0$ следует $w = 1$; из $(y \equiv z) = 0$ следует $y \ne z$; кроме того, $x \land \neg y = 0$. При $y = 0,\ z = 1$ имеем $\neg y = 1$, поэтому обязательно $x = 0$; при $y = 1,\ z = 0$ конъюнкция нулевая сама собой и $x$ произвольно. Подходящих наборов ровно три:

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

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

from itertools import product


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


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