СДНФ: совершенная дизъюнктивная нормальная форма

Любую булеву функцию, которая не равна тождественно нулю, можно записать в единственном каноническом виде - совершенной дизъюнктивной нормальной форме (СДНФ). Эта форма нужна не только в курсе дискретной математики: на ней строятся минимизация логических схем, синтез комбинационных устройств и проверка эквивалентности двух разных записей одной и той же функции. Разберём, как по таблице истинности выделить нужные строки, превратить каждую в элементарную конъюнкцию и собрать из них СДНФ, а заодно - какие ошибки при этом чаще всего допускают. Ниже интерактивный калькулятор: переключай функцию или отдельные строки таблицы и сразу смотри, как меняется формула.

Что такое СДНФ и чем она отличается от обычной ДНФ

Дизъюнктивная нормальная форма (ДНФ) - это просто дизъюнкция каких-то конъюнкций, без жёстких требований к их составу: в одной конъюнкции переменной может не быть вовсе, в другой - быть с отрицанием, в третьей - без. Такую запись легко подобрать вручную, но у неё нет единственности: одну и ту же функцию можно записать разными ДНФ.

Совершенная ДНФ жёстче: каждая конъюнкция обязана быть полной - содержать все $n$ переменных функции ровно по одному разу, либо саму переменную, либо её отрицание, и ни разу не повторяться среди других конъюнкций. Такую элементарную конъюнкцию ранга $n$ называют минтермом. Именно требование «каждая переменная присутствует всегда» и даёт совершенной форме единственность: для функции, не равной тождественно нулю, СДНФ ровно одна с точностью до порядка минтермов и порядка литералов внутри минтерма.

Как построить СДНФ по таблице истинности

Алгоритм не требует никаких преобразований формулы - только чтение таблицы истинности:

Рассчитать для своей задачи

1. Найти в таблице истинности все строки, где функция $F$ равна единице.
2. Для каждой такой строки построить минтерм - конъюнкцию всех переменных, где переменная берётся без отрицания, если в этой строке она равна 1, и с отрицанием $\neg$, если равна 0.
3. Соединить все построенные минтермы знаком дизъюнкции $\vee$.

Возьмём мажоритарную функцию трёх переменных: $F(A,B,C)=1$, если хотя бы две из трёх переменных равны единице. Таблица истинности даёт единицу на наборах $011$, $101$, $110$ и $111$ - ровно четыре строки из восьми. Переводим каждую в минтерм и собираем дизъюнкцию:

$F = (\neg A \wedge B \wedge C) \vee (A \wedge \neg B \wedge C) \vee (A \wedge B \wedge \neg C) \vee (A \wedge B \wedge C).$

Обратите внимание на закономерность: в наборе $011$ переменная $A$ равна 0, поэтому в минтерм она входит с отрицанием, а $B$ и $C$ равны 1 - входят без отрицания. Это правило работает одинаково для любого числа переменных и для любой строки.

Правило одной строки: откуда берётся отрицание

Частая путаница - забыть, что отрицание ставится именно там, где в строке стоит 0, а не там, где «кажется логичнее». Правило строго механическое и не зависит от смысла функции:

Рассчитать для своей задачи

Для набора $101$ (то есть $A=1$, $B=0$, $C=1$) минтерм - это $A \wedge \neg B \wedge C$: единственная переменная с нулём в строке ($B$) получает отрицание, обе единичные переменные входят как есть. Если перепутать правило и ставить отрицание на переменных со значением 1, минтерм окажется равен нулю ровно на своём же наборе - и вся формула перестанет описывать исходную функцию.

Общая формула СДНФ для n переменных

Для функции $n$ переменных $x_1,\dots,x_n$, не равной тождественно нулю, СДНФ записывается как дизъюнкция по всем наборам, на которых функция равна единице:

$F(x_1,\dots,x_n) = \bigvee_{\substack{(\sigma_1,\dots,\sigma_n):\ F(\sigma_1,\dots,\sigma_n)=1}} x_1^{\sigma_1} \wedge x_2^{\sigma_2} \wedge \dots \wedge x_n^{\sigma_n},$

где $x^{1}=x$, а $x^{0}=\neg x$. Число минтермов в СДНФ равно числу единиц в столбце значений функции - это называют весом функции. У функции трёх переменных всего $2^3=8$ строк, поэтому минтермов не больше восьми; у функции $n$ переменных строк $2^n$, а различных булевых функций от $n$ переменных существует $2^{2^n}$ - для трёх переменных это 256 разных функций, и у каждой (кроме тождественного нуля) есть своя, единственная СДНФ.

Если функция задана формулой, а не таблицей

Если исходное выражение уже дано формулой, например $F = A \to (B \wedge C)$, самый надёжный путь - построить таблицу истинности подстановкой всех наборов переменных, а затем применить тот же алгоритм. Это работает всегда и не требует эквивалентных преобразований. Есть и альтернативный путь: раскрыть импликации и отрицания по законам де Моргана, распределить конъюнкции по дизъюнкциям, а затем довести каждую неполную конъюнкцию до полной, домножив на тождественно истинное выражение вида $(x \vee \neg x)$ для каждой отсутствующей переменной и раскрыв скобки. Оба способа дают один и тот же результат - таблица истинности проще считается вручную, а метод с $(x \vee \neg x)$ показывает, откуда СДНФ берётся алгебраически, если функция уже дана в виде ДНФ без части переменных.

СДНФ и СКНФ: зеркальное правило

У СДНФ есть парная конструкция для строк, где функция равна нулю, - совершенная конъюнктивная нормальная форма (СКНФ). Правило построения там зеркальное:

Рассчитать для своей задачи

Для СКНФ берутся строки, где $F=0$, из каждой строится макстерм - дизъюнкция переменных, а не конъюнкция, - причём отрицание ставится там, где в строке стоит 1, а не 0. Для мажоритарной функции нулевые строки - это $000$, $001$, $010$, $100$, значит СКНФ:

$F = (A \vee B \vee C) \wedge (A \vee B \vee \neg C) \wedge (A \vee \neg B \vee C) \wedge (\neg A \vee B \vee C).$

Обе формы описывают одну и ту же функцию: если строк с единицей меньше половины, обычно короче СДНФ, если меньше половины строк с нулём - короче СКНФ.

Единственность и минимизация

СДНФ функции всегда одна и та же с точностью до порядка минтермов - это удобно для проверки: если два студента получили разные по числу минтермов СДНФ для одной и той же функции, у одного из них ошибка в таблице истинности. Но сама СДНФ почти никогда не минимальна: соседние минтермы, отличающиеся ровно одной переменной, можно склеить по закону $(\neg X \wedge Y) \vee (X \wedge Y) = Y$, убрав лишнюю переменную. Такое склеивание - основа метода Квайна-Мак-Класки и карт Карно, и его результат называют минимальной ДНФ. Она уже не обязана быть совершенной: часть минтермов в ней объединена в более короткие конъюнкции, где не все переменные присутствуют.

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

• Отрицание ставится не на той переменной. В минтерме отрицание должно стоять там, где в строке 0, а не там, где переменная «кажется» ложной по смыслу задачи.
• Пропущена строка с единицей. Особенно на функциях от 4 и более переменных легко просмотреть одну строку в таблице из 16 или больше - тогда итоговая СДНФ не совпадает с исходной функцией на этом наборе.
• СДНФ путают с произвольной ДНФ. Не каждая дизъюнкция конъюнкций - совершенная форма; проверяйте, что в каждой конъюнкции ровно $n$ литералов, по одному на переменную.
• Забывают про тождественно ложную функцию. Если столбец значений весь состоит из нулей, СДНФ не существует - дизъюнкция минтермов была бы пустой.
• Путают правило СДНФ и СКНФ. Для минтерма отрицание ставится на нулях строки, для макстерма СКНФ - наоборот, на единицах.

FAQ

Может ли СДНФ функции содержать все возможные минтермы сразу? Да, если функция тождественно истинна - тогда в СДНФ войдут все $2^n$ минтермов. Формально это допустимо, хотя такая запись избыточна: тождественно истинную функцию проще обозначить константой 1.

Что делать, если в таблице истинности функция равна единице на всех строках, кроме одной? Строить СДНФ по тому же алгоритму - минтермов будет $2^n-1$, просто пропущена одна строка с нулём. Никакого особого случая тут нет, кроме тождественно ложной функции.

Обязательно ли СДНФ - самая короткая запись функции? Нет, наоборот: СДНФ обычно избыточна, потому что каждая конъюнкция содержит все переменные. Минимальная ДНФ, полученная склеиванием минтермов, как правило короче и удобнее для построения логической схемы.

Как проверить, что две разные формулы задают одну и ту же функцию? Построить СДНФ для каждой (через таблицу истинности) и сравнить наборы минтермов - благодаря единственности СДНФ они совпадут тогда и только тогда, когда функции равны.

Коротко

СДНФ - единственная каноническая запись булевой функции в виде дизъюнкции полных конъюнкций (минтермов), по одной на каждую строку таблицы истинности, где функция равна единице. Литерал переменной входит в минтерм без отрицания, если в строке 1, и с отрицанием, если 0. Формула $F = \bigvee x_1^{\sigma_1}\wedge\dots\wedge x_n^{\sigma_n}$ по всем наборам с $F=1$ работает для любого числа переменных, а зеркальное правило с макстермами даёт парную СКНФ по нулевым строкам. Сама СДНФ почти никогда не минимальна - для компактной схемы её ещё нужно упростить склеиванием соседних минтермов.