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

#69260Задание №2ФИПИ

Алгебра логики

Миша заполнял таблицу истинности функции $( x \land \neg y ) \lor ( x \equiv z ) \lor \neg w ,$ но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				$( x \land \neg y ) \lor ( x \equiv z ) \lor \neg w ,$
0	1	1	0	0
0				0
	1	0	1	0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идутсоответствующие им столбцы (сначала буква, соответствующая первомустолбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция задана выражением $\neg x \lor y ,$ зависящим от двухпеременных, а фрагмент таблицы имеет следующий вид.

		$\neg x \lor y$
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.

Правильный ответ

xwzy

Пояснение

Решение:

Функция $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