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

Решение:

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

Здесь функция равна единице, значит истинны оба сомножителя выражения $\neg ( y \rightarrow ( z \equiv w ) ) \land ( x \rightarrow z )$. Из $\neg ( y \rightarrow ( z \equiv w ) ) = 1$ следует, что импликация ложна, то есть $y = 1$ и $z \ne w$. Условие $x \rightarrow z = 1$ запрещает пару $x = 1,\ z = 0$. При $z = 1,\ w = 0$ переменная $x$ любая, при $z = 0,\ w = 1$ обязательно $x = 0$. Наборы:

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

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

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

from itertools import product


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


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


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

Ответ: wzyx