Задание 2 ЕГЭ: таблицы истинности на Python

Что нужно найти в таблице истинности

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

0 означает ложь, 1 — истину. Столбец F содержит результат вычисления формулы. В ответе нужны буквы переменных слева направо, например xwzy.

Как переводить логические знаки на Python

Проверочная таблица для двух переменных

Замена импликации сравнением A <= B работает для логических значений 0 и 1. Смысл самой импликации также передаёт выражение (not A) or B.

Как читать порядок столбцов

Пусть F = ¬x ∨ y, а единственная строка фрагмента имеет вид:

Чтобы ИЛИ давало 0, обе части должны равняться 0. Значит ¬x = 0, то есть x = 1; y = 0. В первом столбце стоит y, во втором — x. Ответ: yx.

В более объёмном примере ниже тот же поиск выполнит программа, проверяя сразу все данные строки.

Три строки, четыре переменные и четыре пропуска

В исходной таблице клетки a1, a2, a3, a4 пустые. Каждой пустой клетке дали отдельное имя: это четыре независимых значения 0 или 1.

Шаг 1. Переносим формулу

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

def создаёт функцию, return возвращает её результат. Первая часть проверяет x И НЕ y, вторая — совпадают ли y и z, третья — НЕ w. Между частями стоит ИЛИ.

Шаг 2. Перебираем пропуски

for a1, a2, a3, a4 in product([0, 1], repeat=4):
    tab = [(0, a1, a2, 0), (0, 1, 0, 1), (a3, 1, 0, a4)]

product проверит все 2⁴ = 16 заполнений. В tab входят только четыре столбца переменных: столбец F переносится отдельно. Числа и порядок строк сохраняем точно как в условии.

Шаг 3. Проверяем, что строки различны

if len(tab) == len(set(tab)):

len(tab) — число строк; set(tab) убирает повторы. Если все три строки разные, обе длины равны 3. Если две строки совпали, длина множества меньше и такое заполнение пропускаем.

Например, нельзя принять заполнение, в котором вторая и третья строки стали (0, 1, 0, 1): условие требует различные строки, даже если формула даёт на них нужный результат.

Шаг 4. Перебираем порядок переменных

for p in permutations('xyzw'):

Для четырёх разных букв есть 4! = 24 перестановки. Каждая перестановка задаёт один порядок заголовков сразу для всех строк. Менять заголовки отдельно для каждой строки нельзя.

Шаг 5. Связываем буквы со значениями

p = ('x', 'w', 'z', 'y')
row = (0, 1, 0, 1)
print(dict(zip(p, row)))
# {'x': 0, 'w': 1, 'z': 0, 'y': 1}

zip соединяет элементы попарно: первую букву с первым числом и так далее. dict собирает словарь. Две звёздочки в f(**dict(zip(p, row))) передают его значения в функцию по именам аргументов. Поэтому порядок аргументов в def f(x, y, z, w) не определяет ответ.

Шаг 6. Сравниваем значения F

values = [int(f(**dict(zip(p, row)))) for row in tab]
if values == [0, 0, 0]:
    answers.add(''.join(p))

Для каждой строки вычисляем формулу и переводим результат в 0 или 1 через int. Полученный список должен совпасть со столбцом F по порядку строк. Здесь справа [0, 0, 0], потому что все три значения F в условии нулевые.

''.join(p) соединяет буквы без разделителей. Множество answers сохраняет каждый подходящий порядок один раз.

Полный код для примера на Python

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

from itertools import product, permutations

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

answers = set()
for a1, a2, a3, a4 in product([0, 1], repeat=4):
    tab = [(0, a1, a2, 0), (0, 1, 0, 1), (a3, 1, 0, a4)]
    if len(tab) == len(set(tab)):
        for p in permutations('xyzw'):
            values = [int(f(**dict(zip(p, row)))) for row in tab]
            if values == [0, 0, 0]:
                answers.add(''.join(p))

for answer in sorted(answers):
    print(answer)

Вывод программы

xwzy

В варианте шаблона с print(p) вывод имеет вид ('x', 'w', 'z', 'y'). Это тот же порядок столбцов, но в ответ нужны только буквы.

Почему xwzy подходит ко всем строкам

Найденное заполнение: a1 = a2 = a3 = a4 = 1. Подпишем столбцы и проверим каждую строку.

Во всех строках три части формулы равны нулю, поэтому их ИЛИ тоже даёт 0. Все три набора различны. Перебор остальных заполнений и перестановок другого порядка столбцов не находит.

Как формула получает 0 или 1

Выбери значения переменных: увидишь результат каждой части и итог всей формулы. В этой учебной таблице заголовки известны и идут в порядке x, y, z, w.

Если w = 0, часть ¬w равна 1, поэтому вся формула уже равна 1. Чтобы F была равна 0, все три части с ИЛИ должны равняться 0.

Что менять в шаблоне задания 2

Проверку различных строк сохраняем для такого же условия, как в примере. Если программа ничего не вывела или нашла несколько порядков, проверь формулу, перенос клеток, значения F и условие о различии строк. Не выбирай первую напечатанную строку наугад.

В архиве ниже есть дополнительный шаблон: пропуски в нём отмечаются как None, а их количество определяется автоматически. Это метка пустой клетки, а не логическое значение.

Практика по заданию 2 ЕГЭ

После ошибки можно изменить ответ и попробовать снова. Для ответов с буквами используй английскую раскладку.

Решено: 0 из 8

Скачать код для задания 2 ЕГЭ

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

• Потерять отрицание, скобки или перепутать И с ИЛИ.
• Записать присваивание = вместо сравнения ==.
• Использовать одну переменную a1 для нескольких независимых пропусков.
• Неверно указать repeat или забыть одно из имён пропусков.
• Включить столбец F в строки tab.
• Сравнивать со списком нулей, хотя в условии есть единицы.
• Пропустить проверку различных строк.
• Проверить разные строки с разными перестановками заголовков.
• Переписать ответ в порядке аргументов функции вместо порядка столбцов.
• Добавить в экзаменационный ответ скобки, пробелы, кавычки или запятые.

Вопросы о таблицах истинности