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

Решение:

Дизъюнкция равна нулю только тогда, когда равно нулю каждое слагаемое. Значит во всех трёх строках $z=0$, выражение $w \equiv y$ ложно, то есть $w \ne y$, и $\neg x \land y = 0$, то есть $x=1$ или $y=0$.

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

Так как $z=0$ везде, в столбце переменной $z$ не может быть единиц. Единицы есть в первом, втором и четвёртом столбцах, значит $z$ — третий столбец.

Столбцы $w$ и $y$ обязаны различаться всюду, где обе клетки заполнены. В третьей строке первый и второй столбцы оба равны 1, во второй строке первый и четвёртый столбцы оба равны 1 — эти пары отпадают. Остаётся, что $w$ и $y$ стоят во втором и четвёртом столбцах, а $x$ — в первом.

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

Тот же результат даёт перебор всех 24 расстановок переменных по столбцам:

from itertools import permutations, product

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

rows = [t for t in product([0, 1], repeat=4) if not F(*t)]   # наборы (w, x, y, z) с F = 0

frag = [[None, None, 0, 1],
        [1, 0, None, 1],
        [1, 1, 0, None]]

for cols in permutations('wxyz'):        # cols[i] — переменная в i-м столбце
    for order in permutations(rows, 3):  # какой набор какой строке фрагмента
        val = [dict(zip('wxyz', t)) for t in order]
        if all(frag[r][i] is None or frag[r][i] == val[r][cols[i]]
               for r in range(3) for i in range(4)):
            print(''.join(cols))
            break

Ответ: xyzw