СДНФ и СКНФ

Урок о том, как любую логическую функцию записать в одном из двух «стандартных» видов — через ИЛИ-сумму или через И-произведение.

Нормальная форма — это запись логической функции по строгому шаблону: либо как дизъюнкция (ИЛИ) элементарных конъюнкций, либо как конъюнкция (И) элементарных дизъюнкций.

Когда вы упрощаете выражение по законам логики, ответ может выглядеть как угодно: $A \land (B \lor \neg C)$, $\neg(A \lor B)$, что-то ещё. Это удобно для человека, но неудобно для машины и для сравнения двух функций между собой. Нормальные формы решают эту проблему: они приводят выражение к единому каноническому виду, по которому функции можно сравнивать, программно обрабатывать и строить из таблицы истинности.

Зачем это нужно

Представьте, что вам дали две громоздкие формулы и спросили: задают ли они одну и ту же функцию? Упрощать каждую вручную долго и легко ошибиться. Но если привести обе к совершенной нормальной форме, то одинаковые функции дадут буквально одинаковую запись (с точностью до порядка слагаемых). Это и есть главная ценность: канонический вид — это «отпечаток пальца» функции. На ЕГЭ нормальные формы нужны для обратной задачи — восстановить формулу по готовой таблице истинности, и для проектирования логических схем из элементов И, ИЛИ, НЕ.

Два вида нормальных форм

Введём два кирпичика. Элементарная конъюнкция — это И нескольких переменных, каждая со знаком «есть» или «нет»: например $A \land \neg B \land C$. Элементарная дизъюнкция — это ИЛИ нескольких переменных: например $\neg A \lor B \lor C$.

Дизъюнктивная нормальная форма (ДНФ)

ДНФ — это ИЛИ нескольких элементарных конъюнкций. Идея: «функция истинна, если выполнен первый набор условий, ИЛИ второй, ИЛИ третий». Пример:

$$ F = (A \land \neg B) \lor (\neg A \land C) \lor B $$

Здесь три слагаемых-конъюнкции, соединённых ИЛИ. Это уже ДНФ, но ещё не совершенная: в слагаемые входят не все переменные.

Конъюнктивная нормальная форма (КНФ)

КНФ — это И нескольких элементарных дизъюнкций. Идея: «чтобы функция была истинна, должно выполняться первое условие, И второе, И третье». Пример:

$$ F = (A \lor B) \land (\neg A \lor C) \land (B \lor \neg C) $$

Совершенные формы: СДНФ и СКНФ

Слово «совершенная» означает важное ограничение: в каждое слагаемое (или множитель) входят ВСЕ переменные функции ровно по одному разу — каждая либо с отрицанием, либо без.

СДНФ (совершенная ДНФ) — дизъюнкция конъюнкций, где каждая конъюнкция содержит все переменные. СКНФ (совершенная КНФ) — конъюнкция дизъюнкций, где каждая дизъюнкция содержит все переменные.

Возьмём функцию двух переменных, заданную таблицей истинности:

$A$	$B$	$F$
0	0	0
0	1	1
1	0	1
1	1	0

Это функция «исключающее ИЛИ» ($A \oplus B$). Соберём её СДНФ. Берём строки, где $F = 1$ (вторая и третья), и для каждой пишем конъюнкцию всех переменных: если переменная равна 1 — пишем её саму, если 0 — с отрицанием.

Строка $A=0, B=1$: переменная $A$ равна 0 → пишем $\neg A$, переменная $B$ равна 1 → пишем $B$. Конъюнкция: $\neg A \land B$.
Строка $A=1, B=0$: получаем $A \land \neg B$.

Соединяем найденные конъюнкции через ИЛИ:

$$ F_{\text{СДНФ}} = (\neg A \land B) \lor (A \land \neg B) $$

Теперь СКНФ. Берём строки, где $F = 0$ (первая и четвёртая), и для каждой пишем дизъюнкцию всех переменных по «зеркальному» правилу: если переменная равна 0 — пишем её саму, если 1 — с отрицанием.

Строка $A=0, B=0$: обе переменные равны 0 → пишем их без отрицания. Дизъюнкция: $A \lor B$.
Строка $A=1, B=1$: обе равны 1 → пишем с отрицанием: $\neg A \lor \neg B$.

Соединяем найденные дизъюнкции через И:

$$ F_{\text{СКНФ}} = (A \lor B) \land (\neg A \lor \neg B) $$

Обе формулы задают одну и ту же функцию $A \oplus B$ — можете проверить по таблице. Заметьте симметрию правил: для СДНФ смотрим на единицы и «0 даёт отрицание», для СКНФ смотрим на нули и «1 даёт отрицание». Это зеркальные процедуры.

Как это работает

Почему конъюнкция из строки с единицей «попадает» именно в эту строку? Конъюнкция $\neg A \land B$ истинна тогда и только тогда, когда $A=0$ и $B=1$ одновременно — то есть ровно на одной строке таблицы. Такую конъюнкцию называют минтермом: она «загорается» на единственном наборе. СДНФ — это ИЛИ минтермов всех единичных строк, поэтому функция истинна точно там, где нужно. Аналогично дизъюнкция $A \lor B$ ложна только при $A=0, B=0$ — это макстерм, он «гасит» одну строку, и СКНФ перемножает макстермы всех нулевых строк.

Проверим СДНФ исключающего ИЛИ кодом — переберём все наборы и сравним нашу формулу с эталоном:

def sdnf(a, b):
    return (not a and b) or (a and not b)

for a in (0, 1):
    for b in (0, 1):
        print(a, b, '->', int(sdnf(a, b)), '| xor =', a ^ b)

Вывод:

0 0 -> 0 | xor = 0
0 1 -> 1 | xor = 1
1 0 -> 1 | xor = 1
1 1 -> 0 | xor = 0

Колонка СДНФ совпала с колонкой XOR на всех четырёх наборах — формула верна.

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

Путают, на что смотреть. СДНФ строится по единицам, СКНФ — по нулям. Если перепутать, получите отрицание функции.
Путают знак переменной. Для СДНФ: 0 → с отрицанием, 1 → без. Для СКНФ — наоборот. Самая частая описка.
Соединяют не тем оператором. В СДНФ конъюнкции соединяются через ИЛИ, в СКНФ дизъюнкции — через И. Внутри скобок оператор другой, чем снаружи.
Забывают переменную. В совершенной форме в каждое слагаемое входят все переменные. Пропустил одну — форма уже не совершенная.

Итоги

ДНФ — ИЛИ конъюнкций; КНФ — И дизъюнкций.
В совершенной форме каждое слагаемое содержит все переменные ровно по разу.
СДНФ собирают по строкам с $F=1$ (0 → отрицание), соединяя конъюнкции через ИЛИ.
СКНФ собирают по строкам с $F=0$ (1 → отрицание), соединяя дизъюнкции через И.
Совершенная форма единственна — это канонический «отпечаток» функции.