Разборы · ЕГЭ, задание 2

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

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

Дана логическая функция F от четырёх переменных и фрагмент её таблицы истинности: несколько строк, часть клеток пустая, а над столбцами не подписано, какая где переменная. Нужно определить, какому столбцу соответствует каждая переменная, и записать буквы в порядке столбцов. 1 балл.

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

• Операции: ¬ (НЕ), ∧ (И), ∨ (ИЛИ), → (импликация: ложна только 1 → 0), ≡ (эквивалентность: истинна, когда значения равны).
• В Python для значений 0 и 1: not, and, or; импликация a → b записывается как a <= b, эквивалентность — как a == b.
• Строки фрагмента различны — это важная подсказка, если в них есть пустые клетки.

Как решать

1. Программой выведите все наборы (w, x, y, z), при которых F принимает то же значение, что в столбце F фрагмента.
2. Посмотрите на столбцы этих наборов: какая переменная всегда равна 1, где больше нулей, какие переменные всегда различны.
3. Сопоставьте с фрагментом. Если вариантов несколько, проверьте каждый подстановкой.

Пример из демоверсии 2027

Функция F = ((x ≡ ¬y) → ¬(w → x)) ∨ ¬z. Фрагмент (пустые клетки — точки), во всех строках F = 0:

. 0 1 0
0 . . 0
. 1 1 .

from itertools import product

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

Программа выводит три набора (w, x, y, z): (0, 0, 1, 1), (0, 1, 0, 1), (1, 1, 0, 1). Везде z = 1 — а без нулей во фрагменте только третий столбец, значит, это z. В четвёртом столбце два нуля: это w или y. Если бы это был y, то в строках 1 и 2 фрагмента x = 1, но x не может стоять ни во втором столбце (в строке 1 там 0), ни в первом (в строке 2 там 0). Значит, четвёртый столбец — w. Строка 3 фрагмента — набор с w = 1, то есть (1, 1, 0, 1): во втором столбце единица, это x. Остаётся y в первом столбце. Ответ: yxzw.

Рассуждение можно целиком переложить на программу: перебрать все способы заполнить пустые клетки и все перестановки букв.

from itertools import permutations, product

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

rows = [(None, 0, 1, 0), (0, None, None, 0), (None, 1, 1, None)]   # None — пусто
answers = set()
for fill in product([0, 1], repeat=5):             # пустых клеток пять
    it = iter(fill)
    t = [tuple(next(it) if v is None else v for v in r) for r in rows]
    if len(set(t)) < 3:                            # строки должны быть различны
        continue
    for order in permutations("wxyz"):
        if all(not F(**dict(zip(order, r))) for r in t):
            answers.add("".join(order))
print(answers)                                     # {'yxzw'}

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

• Забывают скобки. В Python x == y <= z — это цепочка сравнений (x == y и y ≤ z), а не импликация, и not слабее сравнений. Каждую операцию берите в скобки.
• Выводят строки с F = 1, хотя во фрагменте F = 0.
• Пишут ответ через запятую или пробел — буквы нужно писать подряд.

Потренироваться: задание 2 новые варианты с проверкой ответа