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

Решение:

Конъюнкция равна единице, значит истинны оба множителя. Из $\neg(y \rightarrow (w \equiv z)) = 1$ следует $y=1$ и $w \ne z$, а второй множитель даёт $w \rightarrow x = 1$.

Подходящих наборов ровно три: $(w,x,y,z)$ равно $(0,0,1,1)$, $(0,1,1,1)$ или $(1,1,1,0)$.

Все заполненные клетки фрагмента — единицы, поэтому условие $y=1$ само по себе ничего не отсеивает. Зато сильно работает условие $w \ne z$: столбцы $w$ и $z$ не могут содержать единицы в одной и той же строке. Вторая строка запрещает пары столбцов 1 и 2, 1 и 4, 2 и 4; первая строка — пары 2 и 3, 2 и 4, 3 и 4; третья строка — пару 3 и 4. Уцелела единственная пара: первый и третий столбцы. Значит $w$ и $z$ стоят в столбцах 1 и 3, а $x$ и $y$ — в столбцах 2 и 4.

Если бы $w$ стоял в третьем столбце, то в первой и третьей строках было бы $w=1$, а набор с $w=1$ всего один — $(1,1,1,0)$, и эти строки совпали бы. Значит $w$ — первый столбец, $z$ — третий.

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

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

from itertools import permutations, product

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

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

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

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

Ответ: wxzy