Задание 2 ЕГЭ по информатике

Question

Логическая функция $F$ задаётся выражением $(x \to y) \land (y \to z) \land (z \to w)$. На рисунке приведён частично заполненный фрагмент таблицы истинности функции $F$, содержащий неповторяющиеся строки.
? | ? | ? | ? | F
1 | 0 | 1
0 | 1 | 1
1 | 0 | 1
Определите, какому столбцу таблицы соответствует каждая из переменных $w,x,y,z$.
В ответе напишите буквы $x, y, z, w$ в том порядке, в котором идут соответствующие им столбцы (сначала - буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Accepted Answer

Путём очевидных рассуждений получим, что $F = 1$ при $x \leqslant y \leqslant z \leqslant w$. Получаем следующую таблицу.
$x$ | $y$ | $z$ | $w$ | $F$
0 | 0 | 0 | 0 | 1
0 | 0 | 0 | 1 | 1
0 | 0 | 1 | 1 | 1
0 | 1 | 1 | 1 | 1
1 | 1 | 1 | 1 | 1
Заметим, что первую и последнюю строки нельзя получить в нашей таблице, поэтому остается следующая таблица:
$x$ | $y$ | $z$ | $w$ | $F$
0 | 0 | 0 | 1 | 1
0 | 0 | 1 | 1 | 1
0 | 1 | 1 | 1 | 1
Также заметим, что три единицы могут быть только в первом столбце, а три нуля - только во втором, следовательно, W - первый столбец, X - второй столбец. Получаем следующую таблицу
$w$ | $x$ | $?$ | $?$ | $F$
1 | 0 | 1 | 0 | 1
1 | 0 | 1 | 1
1 | 0 | 0 | 1
Из первой строки становится очевидно, что третий столбец - z, а четвертый - y. Получаем финальную таблицу
$w$ | $x$ | $z$ | $y$ | $F$
1 | 0 | 1 | 0 | 1
1 | 0 | 1 | 1 | 1
1 | 0 | 0 | 0 | 1

\(x\)	\(y\)	\(z\)	\(w\)	\(F\)
0	0	0	0	1
0	0	0	1	1
0	0	1	1	1
0	1	1	1	1
1	1	1	1	1

\(x\)	\(y\)	\(z\)	\(w\)	\(F\)
0	0	0	1	1
0	0	1	1	1
0	1	1	1	1

\(w\)	\(x\)	\(?\)	\(?\)	\(F\)
1	0	1	0	1
1	0		1	1
1	0	0		1

\(w\)	\(x\)	\(z\)	\(y\)	\(F\)
1	0	1	0	1
1	0	1	1	1
1	0	0	0	1

Задание 2 ЕГЭ по информатике

Базовые случаи построения таблица истинности