Задание 2: алгебра логики и таблицы истинности

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

Что нужно знать

Логические операции

В основе задания — логические операции: способы соединять высказывания так, чтобы получить новое высказывание, истинное или ложное. Базовый набор:

• Инверсия (НЕ, ¬A) — переворачивает значение: если A истинно, ¬A ложно, и наоборот.
• Конъюнкция (И, A∧B) — логическое умножение. Истинна, только если истинны оба операнда.
• Дизъюнкция (ИЛИ, A∨B) — логическое сложение. Ложна, только если ложны оба операнда.
• Импликация (A→B, «если A, то B») — ложна только в одном случае: когда A истинно, а B ложно.
• Эквивалентность (A↔B) — истинна, когда A и B имеют одинаковое значение.

Приоритет операций

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

Правило. В выражении без скобок порядок такой: ¬ → ∧ → ∨ → → → ↔. Если сомневаетесь — расставьте скобки сами и считайте по шагам, это дешевле, чем ошибка в уме.

Таблица истинности

Таблица истинности — это полный перечень всех возможных комбинаций значений переменных (0 и 1) вместе с результатом выражения для каждой комбинации. Для трёх переменных таких комбинаций 2³ = 8, для четырёх — 2⁴ = 16 и так далее: строк всегда 2ⁿ, где n — число переменных.

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

Именно на этой идее построена самая частая разновидность задания 2 (встречается на сайтах-тренажёрах вроде sdamgia.ru и 4ege.ru): дают формулу с переменными x, y, z и обрезанный фрагмент таблицы истинности — например, только строки, где функция истинна, но столбцы подписаны нейтрально («Столбец 1», «Столбец 2», «Столбец 3»). Нужно восстановить, какой столбец — какая переменная.

Встречаются и другие форматы этого задания: подобрать выражение, которое соответствует данной таблице, среди нескольких вариантов ответа; посчитать, сколько строк таблицы дают 1 (или 0); построить таблицу для составного выражения самостоятельно. Но логика решения везде одна — терпеливо и по шагам проверять комбинации.

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

Задача (по мотивам реального задания с sdamgia.ru, id 10376): логическая функция F задаётся выражением

F = (x ∧ ¬y) ∨ (x ∧ z)

На рисунке — фрагмент таблицы истинности этой функции, содержащий все наборы аргументов, при которых F истинна:

Определите, какая переменная (x, y или z) соответствует каждому из столбцов 1, 2, 3. Ответ запишите без пробелов, например «xyz».

Как думать. Не нужно перебирать все 8 строк таблицы вручную для каждого варианта — выгоднее сначала упростить саму формулу. Заметим, что x — общий множитель: F = x ∧ (¬y ∨ z). Значит, F точно ложна при x = 0, и все три строки в фрагменте, где F = 1, обязаны иметь x = 1. Смотрим, в каком из трёх столбцов таблицы не встречается 0 среди этих строк, — это кандидат на x. Дальше для оставшихся двух столбцов (y и z) достаточно проверить обе перестановки и увидеть, какая не даёт противоречий.

Показать решение и ответ

Шаг 1. Упрощаем выражение: F = (x ∧ ¬y) ∨ (x ∧ z) = x ∧ (¬y ∨ z). Значит, F = 1 возможно только при x = 1.

Шаг 2. Смотрим на столбцы фрагмента: столбец 1 содержит значения 0, 0, 1 — там есть нули, значит это не x. Столбец 2 содержит только единицы (1, 1, 1) — кандидат на x. Столбец 3 содержит 0, 1, 1 — тоже есть ноль, не x.

Шаг 3. Пробуем: столбец 2 = x, столбец 1 = y, столбец 3 = z. Проверяем все три строки по формуле F = x ∧ (¬y ∨ z):

• строка 1: x=1, y=0, z=0 → ¬y∨z = 1∨0 = 1 → F = 1∧1 = 1 ✓
• строка 2: x=1, y=0, z=1 → ¬y∨z = 1∨1 = 1 → F = 1 ✓
• строка 3: x=1, y=1, z=1 → ¬y∨z = 0∨1 = 1 → F = 1 ✓

Все три строки совпадают с таблицей — значит, назначение верное. Для контроля можно убедиться, что обратная перестановка (столбец 1 = x) сразу даёт противоречие в первой же строке, где столбец 1 = 0.

Ответ: yxz (столбец 1 — y, столбец 2 — x, столбец 3 — z).

Как решить в Python

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

from itertools import product, permutations

# Функция F(x, y, z) по условию задачи
def F(x, y, z):
    return (x and not y) or (x and z)

# Строим множество всех "истинных" троек (x, y, z), при которых F = 1
true_triples = set()
for x, y, z in product([0, 1], repeat=3):
    if F(x, y, z):
        true_triples.add((x, y, z))

# Фрагмент таблицы истинности из условия: все строки, где F = 1
given_fragment = {(0, 1, 0), (0, 1, 1), (1, 1, 1)}

# Перебираем все варианты, какая переменная стоит в каком столбце
names = ['x', 'y', 'z']
for perm in permutations(names):
    # perm[0], perm[1], perm[2] — имена переменных в столбцах 1, 2, 3
    mapping = dict(zip(names, perm))  # как переставить (x,y,z) -> (col1,col2,col3)
    reordered = set()
    for (x, y, z) in true_triples:
        values = {'x': x, 'y': y, 'z': z}
        # переставляем значения в порядке "какая переменная в каком столбце"
        row = (values[perm[0]], values[perm[1]], values[perm[2]])
        reordered.add(row)
    if reordered == given_fragment:
        print("Столбец 1:", perm[0], "| Столбец 2:", perm[1], "| Столбец 3:", perm[2])

Программа перебирает все 6 перестановок трёх переменных по столбцам и печатает единственную, при которой множество «истинных» строк совпадает с данным фрагментом. Результат — yxz, что подтверждает решение из спойлера.