Задание 2 ЕГЭ по информатике на Python: таблица истинности

В задании 2 ЕГЭ по информатике дана логическая функция и кусок её таблицы истинности, а столбцы таблицы не подписаны: нужно понять, какая переменная стоит в каком столбце. Руками для этого строят таблицу из 16 строк и долго сверяют. На Python задача решается перебором: компьютер сам проверит все строки и все порядки переменных. Каждый пример ниже запускается прямо на странице — нажми «запустить» и сравни вывод. Пример задачи составлен для этой статьи, на экзамене функция и таблица будут другие, а код — тот же.

Перевести функцию на Python

Операции из задания переводятся по схеме выше. Импликация x → y ложна только в одном случае — когда x = 1, а y = 0; сравнение x <= y для нулей и единиц ведёт себя так же. Проверь это на всех четырёх парах:

print("x y x→y")
for x in (0, 1):
    for y in (0, 1):
        print(x, y, int(x <= y))

x y x→y
0 0 1
0 1 1
1 0 0
1 1 1

Каждую операцию бери в скобки, даже если кажется, что приоритет и так верный: так функция читается как в задании и не ломается на цепочке сравнений (об этом — в разделе с ошибками).

Пример задачи

Логическая функция F задана выражением ((x → y) ∧ ¬z) ∨ (w ≡ x). Дан фрагмент её таблицы истинности: три разные строки, в которых F = 0, некоторые клетки пустые. Определи, какому столбцу таблицы соответствует каждая из переменных x, y, z, w.

Шаг 1: все строки, где F = 0

Для четырёх переменных строк 16. itertools.product([0, 1], repeat=4) перебирает их все в порядке x, y, z, w, а условие оставляет только те, где функция ложна:

from itertools import product

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

print("x y z w")
for x, y, z, w in product([0, 1], repeat=4):
    if not F(x, y, z, w):
        print(x, y, z, w)

x y z w
0 0 1 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 1 0

F ложна в пяти строках из шестнадцати. Строки фрагмента — три из этих пяти, только переставленные по столбцам и с пустыми клетками. Сопоставлять их можно и глазами, но надёжнее поручить и это программе.

Шаг 2: перебрать порядок столбцов

Пустые клетки заполним всеми способами, а для каждого заполнения переберём все 24 порядка переменных — permutations("xyzw"). Порядок подходит, если на всех трёх строках F = 0:

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 = [(a, b, 1, 1), (0, c, d, 0), (0, 0, 0, e)]
    if len(set(table)) < 3:
        continue
    for names in permutations("xyzw"):
        if all(not F(**dict(zip(names, row))) for row in table):
            answers.add("".join(names))
print(*sorted(answers))

ywzx

• a, b, c, d, e — пять пустых клеток фрагмента: product подставляет в них все 32 сочетания нулей и единиц.
• len(set(table)) < 3 отбрасывает заполнения, где две строки совпали: по условию строки разные. Без этой проверки программа примет и такие заполнения, а для двух одинаковых строк условие слабее, и может пройти лишний порядок.
• dict(zip(names, row)) подписывает клетки строки именами переменных в проверяемом порядке, а F(**...) передаёт их в функцию по именам.
• answers — множество: один и тот же порядок подходит при разных заполнениях, а печатать его нужно один раз.

Как прочитать ответ

ywzx — переменные слева направо по столбцам: в первом столбце y, во втором w, в третьем z, в четвёртом x. Это и есть ответ к заданию. Если программа напечатала два порядка или ни одного, проверь, правильно ли функция и строки переписаны из условия: у задачи из ЕГЭ ответ единственный.

Частые ошибки

Цепочка сравнений вместо скобок. x <= y == z в Python означает (x <= y) and (y == z), а не (x <= y) == z:

x, y, z = 0, 0, 1
print((x <= y) == z)
print(x <= y == z)

True
False

Так эквивалентность импликации и переменной молча считается не так, как в задании. Скобки вокруг каждой операции снимают вопрос.

Тильда вместо not. ~ в Python — побитовое отрицание целого числа, а не логическое:

x = 1
print(~x, bool(~x))
print(not x)

-2 True
False

~1 равно −2, а любое ненулевое число в условии считается истиной. Для логики пиши not.

= вместо ==. В выражении функции эквивалентность — это сравнение ==. Одиночное = — присваивание, и Python остановится ещё до запуска с подсказкой: SyntaxError: invalid syntax. Maybe you meant '==' or ':=' instead of '='?

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