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

Во втором задании дана логическая функция от трёх или четырёх переменных и фрагмент её таблицы истинности: несколько строк, в которых часть клеток не заполнена, а над столбцами вместо имён переменных стоят «Переменная 1», «Переменная 2» и так далее. Нужно выяснить, какой переменной соответствует каждый столбец. Ответ — буквы переменных в порядке столбцов, например ywxz.

Задание базового уровня, но в нём легко потерять балл из-за невнимательности. Хорошая новость: на компьютерном ЕГЭ его надёжно проверяет короткая программа полного перебора.

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

• знание логических операций: конъюнкция (И, ∧), дизъюнкция (ИЛИ, ∨), отрицание (НЕ, ¬), импликация (→), эквиваленция (≡);
• умение быстро понять, при каких наборах значений функция ложна или истинна;
• умение рассуждать «от противного» и учитывать все условия задачи, включая то, что строки фрагмента различны.

Напомним полезные факты. Импликация a → b ложна только при a = 1, b = 0. Эквиваленция a ≡ b истинна, когда значения совпадают. Дизъюнкция ложна, только если ложны все её слагаемые, а конъюнкция истинна, только если истинны все сомножители.

Типичные формулировки

1. Дан фрагмент таблицы, в котором во всех строках F = 0 (или во всех F = 1); часть клеток пуста. Определите, какому столбцу соответствует каждая переменная.
2. То же, но в столбце F стоят разные значения — тогда учитываются и «нулевые», и «единичные» строки.
3. Функция записана в виде, удобном для Python: (x and not y) or (y == z) or (not w).

Во всех вариантах в условии оговаривается, что строки фрагмента различны и что каждой переменной соответствует ровно один столбец.

Пошаговый метод

1. Упростите условие. Если во всех строках F = 0, а F — дизъюнкция, то каждое слагаемое должно быть ложно. Выпишите эти требования отдельно.
2. Найдите переменную с жёстким значением. Часто одна переменная во всех нужных строках обязана быть равна 0 или 1. Столбец, где встречается противоположное значение, ей точно не подходит.
3. Используйте пары. Условия вида y ≡ z = 0 означают, что y и z в каждой строке различны; значит, столбцы, где в одной строке стоят две одинаковые цифры, не могут быть одновременно y и z.
4. Разберите оставшиеся случаи. Для каждого варианта попробуйте заполнить пустые клетки так, чтобы все строки подходили. Не забудьте проверить, что строки получаются различными.
5. Запишите ответ — имена переменных в порядке столбцов, без пробелов.

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

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

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

Шаг 1. Когда F = 0? Дизъюнкция ложна, когда ложны все три слагаемых: w = 1; y и z различны; не выполняется «x = 1 и y = 0».

Шаг 2. Где w? Переменная w во всех строках равна 1. В столбце 4 во второй строке стоит 0, в столбцах 1 и 3 тоже есть нули. Значит, w — столбец 2 (он пустой, и это допустимо).

Шаг 3. Где y и z? В третьей строке в столбцах 1 и 3 стоят одинаковые нули, поэтому y и z не могут занимать оба этих столбца. Следовательно, один из них — столбец 4.

Шаг 4. Перебираем случаи.

• y — столбец 4. Тогда во второй строке y = 0, а z и x стоят в столбцах 1 и 3. Если x — столбец 1, то x = 1 и y = 0, и слагаемое x ∧ ¬y истинно, F = 1 — противоречие. Если z — столбец 1, x — столбец 3, то во второй строке x должен быть 0, а первая строка обязана совпасть со второй или третьей — строки перестают быть различными. Не подходит.
• z — столбец 4, y — столбец 3, x — столбец 1. Во второй строке x = 1, значит y = 1, z = 0 — подходит. Но тогда в первой строке y = 0, z = 1, x = 0, и она совпадает с третьей строкой. Не подходит.
• z — столбец 4, y — столбец 1, x — столбец 3. Вторая строка: y = 1, z = 0 — подходит при любом x. Третья: y = 0, z = 1, x = 0 — подходит. Первую строку можно заполнить так, чтобы она отличалась от остальных (например, y = 1, x = 0, z = 0). Всё согласовано.

Ответ: ywxz.

Код на Python

Ручной разбор полезен для понимания, но на экзамене надёжнее проверить ответ перебором. Перебираем все перестановки переменных и все способы заполнить пустые клетки:

from itertools import permutations, product

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

frag = [(None, None, 0, None), (1, None, None, 0), (0, None, 0, 1)]  # None — пустая клетка
for p in permutations('xyzw'):
    blanks = sum(v is None for r in frag for v in r)
    for fill in product([0, 1], repeat=blanks):
        it = iter(fill)
        rows = [tuple(v if v is not None else next(it) for v in r) for r in frag]
        if len(set(rows)) == len(rows) and all(F(**dict(zip(p, r))) == 0 for r in rows):
            print(''.join(p))
            break

Программа печатает единственную строку ywxz. Если строк несколько — проверьте, не забыли ли вы условие различности строк (len(set(rows)) == len(rows)) или значение F в каком-то ряду. Если в фрагменте F принимает разные значения, храните его вместе со строками и сравнивайте F(...) == значение.

Обратите внимание на запись операций в Python: импликацию a → b удобно писать как a <= b (для 0 и 1 это работает), эквиваленцию — как a == b, отрицание — not a.

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

• Забывают про различность строк. Именно она часто отсекает «лишние» варианты, как в разобранном примере.
• Путают импликацию. a → b ложна только при a = 1 и b = 0; запись a <= b в Python верна лишь для логических значений 0/1.
• Неправильно расставляют скобки при переносе формулы в программу: not x or y и not (x or y) — разные функции.
• Записывают ответ не в том порядке. Нужны имена переменных по порядку столбцов слева направо, а не столбцы по порядку переменных.
• Пишут ответ заглавными буквами или через запятую — ответ записывается так, как требует условие, обычно строчными латинскими буквами подряд.

Потренируйтесь

Решите несколько заданий подряд и проверяйте себя программой: задания № 2 в банке. Если хотите отработать сам код перебора, возьмите задачи с проверкой кода. Повторить логические операции поможет статья «Логические операции, таблицы истинности и отрезки», а следующее задание — задание 3: базы данных.