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

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

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

Миша заполнял таблицу истинности логической функции F
¬(y → x) \/ (z → w) \/ ¬z,
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

			F
	0		0
0	1		0
1		0	0

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

		F
0	1	0

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

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

yxzw

Пояснение

Решение:

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

$\neg z = 0$ , то есть $z = 1$ ;
$(z \rightarrow w) = 0$ ; при $z = 1$ это даёт $w = 0$ ;
$\neg(y \rightarrow x) = 0$ , то есть $y \rightarrow x = 1$ : $y = 0$ или $x = 1$ .

Столбец $z$ . В нём во всех строках стоит 1. Второй столбец отпадает: в первой строке там 0. Первый столбец отпадает: во второй строке там 0. Четвёртый столбец отпадает: в третьей строке там 0. Значит $z$ — третий столбец.

Столбец $w$ . В нём во всех строках стоит 0. Второй столбец отпадает (во второй строке там 1), первый столбец отпадает (в третьей строке там 1), третий занят переменной $z$ . Значит $w$ — четвёртый столбец; в третьей строке там действительно 0.

Столбцы $x$ и $y$ . Им остаются первый и второй столбцы, а во второй строке в них стоят 0 и 1. Если бы $x$ был первым столбцом ( $x = 0$ ), а $y$ — вторым ( $y = 1$ ), то $y \rightarrow x = 0$ и $F = 1$ , что противоречит таблице. Значит $x$ — второй столбец, а $y$ — первый.

Проверка: первая строка (_ 0 _ _) даёт $x = 0$ , тогда $y = 0$ , и строка равна 0 0 1 0; вторая строка — 0 1 1 0; третья строка (1 _ _ 0) даёт $y = 1$ , тогда $x = 1$ , и строка равна 1 1 1 0. Все три строки различны, во всех $F = 0$ .

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

Ответ: yxzw