Задание 2. Таблицы истинности – ЕГЭ по информатике

Что проверяет задание

Задание 2 – логическая функция от трёх или четырёх переменных и кусочек её таблицы истинности. Столбцы в этом кусочке не подписаны, и восстановить их подписи – это и есть задача: какая переменная стоит в каком столбце. Строки при этом идут не в том порядке, что в обычной таблице, а часть клеток пуста.

1 балл, норматив 3 минуты. Компьютер здесь не обязателен: задание решается на листочке, если уметь читать выражение с конца. Решить программой тоже можно – она в конце разбора.

Что нужно знать заранее:

таблицы истинности пяти операций: $\neg$, $\land$, $\lor$, $\to$, $\equiv$. Подзабыли – они разобраны в учебнике: НЕ, И, ИЛИ и импликация и эквивалентность;
приоритет: сначала $\neg$, затем $\land$, затем $\lor$, и только потом $\to$ и $\equiv$. Поэтому $x \lor y \to z$ – это $(x \lor y) \to z$;
у функции от $n$ переменных в таблице $2^n$ строк: 8 для трёх переменных, 16 для четырёх.

Типовой пример

Задание 2 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Миша заполнял таблицу истинности логической функции

$F = ((x \equiv \neg y) \to \neg (w \to x)) \lor \neg z$,

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


	0	1	0
0			0
	1	1

Определите, какому столбцу таблицы соответствует каждая из переменных $w$, $x$, $y$, $z$. В ответе напишите буквы $w$, $x$, $y$, $z$ в том порядке, в котором идут соответствующие им столбцы, без разделителей.

Как рассуждать

Первое: посмотреть на столбец F. Во фрагменте у всех трёх строк $F = 0$ – значит, из всей таблицы нам нужны только строки, где функция ложна, остальные не понадобятся.

Разбираем выражение с последней операции. У $F$ это $\lor$: $F = A \lor \neg z$, где $A = (x \equiv \neg y) \to \neg(w \to x)$. Дизъюнкция ложна, только если ложны оба: сразу $\neg z = 0$, то есть $z = 1$, и $A = 0$.
Спускаемся ниже. $A$ – импликация, она ложна только в случае $1 \to 0$: посылка $(x \equiv \neg y)$ истинна, следствие $\neg(w \to x)$ ложно. Первое означает $x \ne y$, второе – что $w \to x$ истинна.
Выписываем строки. Условия $z = 1$, $x \ne y$, $w \to x$ даёт три набора: при $x = 1, y = 0$ импликация истинна при любом $w$ (две строки), при $x = 0, y = 1$ – только при $w = 0$ (одна). Итого строки $(w, x, y, z)$: $(0, 1, 0, 1)$, $(1, 1, 0, 1)$, $(0, 0, 1, 1)$. Три строки решения и три строки фрагмента – значит, это одни и те же строки, только столбцы переставлены и порядок строк свой.
Дальше – восстановление. Соответствие столбцов ищут примерно как решают судоку: нашли то, что определено однозначно, дописали в пустые клетки полученные значения, посмотрели, что открылось после этого. Смотреть нужно и по столбцам, и по строкам.

Ниже эти шаги разобраны на нашей задаче – по одному, с таблицей перед глазами.

Второй способ: пусть таблицу построит Python

Разбор выше – способ для листочка: таблицу мы не строили, нужные наборы достали из самой формулы. Второй способ – ровно наоборот: экзамен сдают за компьютером, значит можно не разбирать выражение, а поручить машине перебрать все наборы и показать те, что нужны. Дальше всё то же: три набора, восстановление фрагмента, ответ.

Программа простая: четыре вложенных цикла гоняют все 16 наборов, а печатаются только те, на которых функция ложна. Разбирать выражение не нужно вовсе – достаточно записать его на Python и не ошибиться со скобками.

Второй способ: программа

def F(w, x, y, z):
    # Импликация a -> b на Python: a <= b, ведь False меньше True.
    return ((x == (not y)) <= (not (w <= x))) or (not z)

# Четыре вложенных цикла – все 16 наборов. Печатаем только те,
# на которых функция ложна: именно они попали во фрагмент.
for w in 0, 1:
    for x in 0, 1:
        for y in 0, 1:
            for z in 0, 1:
                if not F(w, x, y, z):
                    print(w, x, y, z)

# Программа напечатает:
# 0 0 1 1
# 0 1 0 1
# 1 1 0 1

Решайте здесь – любую задачу этого типа

Введите функцию в поле сверху и нажмите «Построить». Пишите на Python: not, and, or, ==, !=; импликация $a \to b$ – это a <= b.
Заполните фрагмент слева: клик по клетке ставит 0, второй – 1, третий очищает. Клетки, которых нет в условии, оставьте пустыми. Строки добавляйте и убирайте кнопками.
Отберите нужные строки справа – фильтром $F = 0$ или $F = 1$.
Дописывайте восстановленное в тот же фрагмент, как только значение клетки стало понятным.
Отмечайте пары цветом: возьмите цвет справа, кликните по столбцу слева и по столбцу справа. Пара подпишется на кнопке цвета – это и есть ответ.

Кнопка «Из условия» вернёт разобранную задачу.

И про скобки. В Python сравнения выполняются раньше логических операций: сначала ==, !=, <=, и только потом not, and, or. Поэтому x <= y and z – это (x <= y) and z, тогда как математическая запись $x \to y \land z$ означает $x \to (y \land z)$. Ставьте скобки везде – так в поле окажется то выражение, которое вы имели в виду.

Типичные ошибки

Переписали функцию с ошибкой. Условие переносят на черновик руками, и одна потерянная скобка или отрицание не у той переменной меняют всю таблицу. Дальше решение будет безупречным – но не для этой задачи. Сверьте выражение с бланком, прежде чем считать.
Неверно вспомнили таблицу истинности. Чаще всего страдает импликация: она ложна ровно в одном случае, $1 \to 0$, и это единственная несимметричная операция – $a \to b$ и $b \to a$ разные вещи.
Перепутали приоритет. Сначала $\neg$, затем $\land$, затем $\lor$, и только потом $\to$ и $\equiv$. Прочитанное не с той операции выражение даёт другой набор строк. В программе приоритет свой, питоновский, – там сравнения идут раньше логических операций, поэтому в коде скобки ставят везде.
При восстановлении получили две одинаковые строки. Так не бывает: в таблице истинности все наборы разные, и в условии прямо сказано, что строки фрагмента различны. Совпали – значит ошиблись раньше: либо в самих наборах, либо в подписи столбца. Это самая дешёвая проверка по ходу решения – взгляните на фрагмент целиком, когда клетки заполнены.