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

Решение:

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

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

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

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

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

from itertools import product


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


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


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

Ответ: xwyz