Как строить таблицы истинности и восстанавливать формулу по фрагменту?

Таблица истинности перечисляет наборы значений переменных и результат логической функции. Для n независимых переменных полная таблица содержит 2ⁿ строк. В демонстрационных заданиях МФТИ встречается обратная постановка: дан лишь фрагмент таблицы, а среди формул нужно найти совместимую.

Порядок вычисления

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

Работа с неполной таблицей

Не нужно строить 2ⁿ строк, если условие даёт три конкретных набора. Подставьте каждый набор в варианты и отбрасывайте формулу при первом противоречии. Особенно полезно замечать конъюнкцию многих литералов: она истинна лишь на одном совместимом наборе, тогда как большая дизъюнкция ложна лишь при одновременной ложности всех частей.

Неизвестный порядок столбцов

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

СДНФ и СКНФ

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

Контрольная стратегия

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

Таблица как набор строк, а не рисунок

Число строк для n независимых переменных равно 2ⁿ. Перебор удобно строить в лексикографическом порядке, но при сопоставлении с фрагментом из задания порядок столбцов нельзя предполагать. Нужно перебрать допустимые перестановки имён и оставить только те, которые воспроизводят все известные значения функции.

from itertools import product

def implication(a: bool, b: bool) -> bool:
    return (not a) or b

print("A B A->B")
for a, b in product((False, True), repeat=2):
    value = implication(a, b)
    print(int(a), int(b), int(value))

Для построения СДНФ берут строки с единицей: истинная переменная входит без отрицания, ложная — с отрицанием. Для СКНФ используют строки с нулём и противоположное правило внутри дизъюнкции. После построения формулу снова прогоняют по полной таблице.

Практика: восстановление потерянных подписей

Постройте таблицу функции (A xor B) and C. Удалите заголовки трёх входных столбцов и оставьте четыре разные строки. Напишите перебор всех шести перестановок имён, который найдёт совместимые варианты. Затем добавляйте строки по одной и наблюдайте, когда решение становится единственным. Вручную выпишите СДНФ и проверьте её тем же перебором, отделяя задачу идентификации столбцов от задачи вычисления функции.