Задание 2 ЕГЭ по информатике: логические функции и таблицы истинности — решение на Python

Задание 2 ЕГЭ по информатике — одно из самых «программируемых» в КЕГЭ (компьютерном ЕГЭ по информатике). Его можно решить на бумаге, но короткая программа на Python справится за минуту и почти без риска ошибиться в вычислениях. Ниже разберём, что требуется в задании и как записать логические операции на Python, решим пример двумя способами и покажем ловушки, на которых чаще всего теряют балл.

Что требуется в задании 2

В формате последних лет условие выглядит так. Дана логическая функция $F$ от четырёх переменных $x, y, z, w$ — например, $F = ((x \to y) \land \lnot z) \lor (w \equiv x)$. Дан фрагмент её таблицы истинности: несколько строк, в которых $F$ принимает одно и то же значение (0 или 1). Какие-то ячейки фрагмента пустые, а вместо названий переменных в шапке стоят знаки вопроса.

Нужно определить, какому столбцу соответствует каждая переменная. Ответ — буквы переменных в том порядке, в каком идут столбцы, без пробелов и запятых: например, wxyz.

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

Логические операции и их запись в Python

Импликация — главный источник ошибок. Запись x <= y работает потому, что в Python False < True, а значит x <= y ложно ровно в одном случае: x = 1, y = 0. Это и есть таблица импликации. Проверим:

print('x y | x->y  x==y')
for x in (False, True):
    for y in (False, True):
        print(int(x), int(y), '|', int(x <= y), '    ', int(x == y))

Вывод:

x y | x->y  x==y
0 0 | 1      1
0 1 | 1      0
1 0 | 0      0
1 1 | 1      1

Импликация ложна только в строке 1 0, эквивалентность истинна при совпадающих значениях — всё сходится.

Разбор примера

Дано: функция $F = ((x \to y) \land \lnot z) \lor (w \equiv x)$ и фрагмент из трёх различных строк, в которых $F = 0$.

Найти: какой переменной соответствует каждый столбец.

Решение «руками»

1. Когда $F = 0$? Дизъюнкция ложна, только если ложны обе скобки. Значит, $w \ne x$, и при этом $(x \to y) \land \lnot z = 0$, то есть $z = 1$ или $x \to y$ ложна ($x = 1$, $y = 0$). Выпишем все наборы $(x, y, z, w)$, где $F = 0$: при $x = 0$ должно быть $w = 1$, $z = 1$ — это 0011 и 0111; при $x = 1$ должно быть $w = 0$, а $z = 1$ или $y = 0$ — это 1000, 1010, 1110. Всего пять строк.
2. Вторая строка фрагмента 0 1 0 0 содержит ровно одну единицу. Среди пяти наборов такой только один — 1000, где единица у $x$. Значит, второй столбец — $x$, а оставшиеся три столбца соответствуют $y, z, w$ в каком-то порядке.
3. Третья строка: во втором столбце 0, то есть $x = 0$. Тогда $z = w = 1$. В третьем столбце стоит 0 — это может быть только $y$. Первый и четвёртый столбцы — это $z$ и $w$.
4. Первая строка: в первом столбце 0. Пусть первый столбец — $z$. Тогда $z = 0$, а при таком $z$ функция равна нулю, только если $x = 1$, $y = 0$, $w = 0$. Получаем строку 0 1 0 0 — точную копию второй строки. Строки обязаны различаться, поэтому этот вариант отпадает. Остаётся: первый столбец — $w$, четвёртый — $z$.

Ответ: wxyz.

Решение программой

Идея перебора простая: пустые ячейки заполняем всеми возможными способами (itertools.product), для каждого заполнения перебираем все 24 порядка переменных (itertools.permutations) и проверяем, что функция на каждой строке даёт нужное значение. Заполнения, при которых строки совпадают, пропускаем.

from itertools import product, permutations

def f(x, y, z, w):
    return ((x <= y) and not z) or (w == x)

answers = set()
for a, b, c, d, e in product([0, 1], repeat=5):
    table = [(0, a, b, c),
             (0, 1, 0, 0),
             (d, 0, 0, e)]
    if len(set(table)) < len(table):   # строки фрагмента обязаны быть разными
        continue
    for p in permutations('xyzw'):
        if all(f(**dict(zip(p, row))) == 0 for row in table):
            answers.add(''.join(p))
print(answers)

Вывод:

{'wxyz'}

Как это работает:

• пять пустых ячеек — пять переменных a, b, c, d, e, поэтому repeat=5;
• set(table) убирает повторы: если множество короче списка, две строки совпали;
• zip(p, row) сопоставляет столбцы с буквами, например ('w', 0), ('x', 0), ..., а f(**dict(...)) передаёт значения по именам — порядок аргументов функции при этом не важен;
• ответы складываем в множество, потому что один и тот же порядок может подойти при разных заполнениях.

Если программа вывела ровно один вариант — это и есть ответ. Если несколько — ищите ошибку в функции или в переписанной таблице.

Что будет без проверки различности строк

Уберём строку с set(table) и запустим снова:

from itertools import product, permutations

def f(x, y, z, w):
    return ((x <= y) and not z) or (w == x)

answers = set()
for a, b, c, d, e in product([0, 1], repeat=5):
    table = [(0, a, b, c), (0, 1, 0, 0), (d, 0, 0, e)]
    for p in permutations('xyzw'):
        if all(f(**dict(zip(p, row))) == 0 for row in table):
            answers.add(''.join(p))
print(sorted(answers))

Вывод:

['wxyz', 'zxyw']

Появился лишний вариант zxyw — ровно тот, который мы отбросили в пункте 4 ручного решения: при нём первая строка совпадает со второй. Если на экзамене программа выдала два ответа и непонятно почему, первым делом проверьте различность строк.

где теряют баллы

Путают импликацию: $x \to y$ — это не x >= y и не x and y, а x <= y или (not x) or y; ложна она только при $1 \to 0$. Забывают, что строки различны, — перебор без этой проверки может выдать несколько ответов, и угадать верный не получится. Пишут ответ не в том порядке: нужны буквы по столбцам слева направо, а не по алфавиту и не в порядке, в каком вы их нашли. Не учитывают приоритет операций в Python: сначала выполняются сравнения (<=, ==, !=), потом not, потом and, потом or. Поэтому импликацию между выражениями всегда берите в скобки.

Приоритет операций: проверка на примерах

Вот три пары записей, которые выглядят почти одинаково, а дают разный результат:

x, y, z = False, True, False
print(x and y <= z, (x and y) <= z)   # x ∧ (y → z)  против  (x ∧ y) → z
print(not x <= y, (not x) <= y)       # ¬(x → y)     против  ¬x → y

x, y, z = True, False, False
print(x <= y <= z, (x <= y) <= z)     # цепочка сравнений  против  (x → y) → z

Вывод:

False True
False True
False True

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

Задачи для самопроверки

Решите сначала «руками», затем проверьте программой — достаточно поменять функцию, таблицу и значение $F$ в коде из разбора.

Задача 1

Функция $F = (x \to y) \land \lnot(y \equiv z) \land \lnot w$. Дан фрагмент таблицы истинности, все строки различны, во всех $F = 1$:

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

Задача 2

Функция $F = (x \land \lnot y) \lor (y \equiv z) \lor \lnot w$. Дан фрагмент таблицы истинности, все строки различны, во всех $F = 0$:

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

Подсказка к задаче 2: если ваша программа нашла два ответа, проверьте, не забыли ли вы условие о различных строках.

Итог

Задание 2 решается по одной схеме: выписать функцию на Python, аккуратно перенести фрагмент таблицы, перебрать заполнения пустых ячеек и порядки переменных, отбросить совпадающие строки. Ручное решение всё равно стоит знать: оно помогает понять, почему ответ именно такой, и выручает, если программа выдала странный результат. А программа страхует от ошибок в вычислениях.

Если хотите разобрать все задания КЕГЭ в такой же логике — с практикой каждый день и ответами на вопросы между занятиями, — посмотрите наш курс подготовки к ЕГЭ по информатике. Проверить, как вы справляетесь с заданиями в реальном формате и по времени, можно на пробном ЕГЭ по информатике.

Ответы

• Задача 1: zwxy.
• Задача 2: zwyx.