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

Решение:

Функция $F = (x \land \neg y) \lor (x \equiv z) \lor \neg w$ — это дизъюнкция трёх слагаемых. Во всех трёх заполненных строках $F = 0$, а дизъюнкция равна нулю только тогда, когда каждое слагаемое равно нулю. Значит в каждой строке одновременно выполняется:

• $\neg w = 0$, то есть $w = 1$;
• $(x \equiv z) = 0$, то есть $x \ne z$;
• $(x \land \neg y) = 0$, то есть $x = 0$ или $y = 1$.

Ищем столбец переменной $w$. В нём во всех строках должна стоять единица. В первой строке (0 1 1 0) единицы стоят только во втором и третьем столбцах, а в третьей строке (_ 1 0 1) третий столбец равен нулю. Остаётся второй столбец: $w$ — это второй столбец.

Ищем столбец переменной $z$. В первой строке оставшиеся столбцы 1, 3, 4 равны 0, 1, 0. Так как $x \ne z$, одна из этих двух переменных стоит в третьем столбце. Пусть в третьем столбце стоит $x$; тогда $x = 1$, и из условия $x \land \neg y = 0$ следует $y = 1$. Но в первой строке в первом и четвёртом столбцах нули, поэтому $y = 1$ невозможно. Значит в третьем столбце стоит $z$, а переменные $x$ и $y$ занимают первый и четвёртый столбцы.

Различаем $x$ и $y$. Пусть $x$ — четвёртый столбец, а $y$ — первый. Разберём вторую строку (0 _ _ _): $y = 0$, поэтому из $x \land \neg y = 0$ получаем $x = 0$; далее $z \ne x$ даёт $z = 1$, а $w = 1$. Строка однозначно восстанавливается как 0 1 1 0 и совпадает с первой строкой, а по условию все три строки различны. Значит этот вариант отпадает.

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

Итак, столбцы слева направо: $x$, $w$, $z$, $y$.

Ответ: xwzy