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

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

• в ней нет одинаковых слагаемых (элементарных конъюнкций);
• в каждом слагаемом нет повторяющихся переменных;
• каждое слагаемое содержит все переменные, от которых зависит булева функция (каждая переменная может входить в слагаемое либо в прямой, либо в инверсной форме).

Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причём единственным образом, то есть для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная.

Краткая теория

ДНФ представляет собой «сумму произведений», причём в качестве операции «умножения» выступает операция И (конъюнкция), а в качестве операции «сложения» — операция ИЛИ (дизъюнкция). Сомножителями являются различные переменные, причём они могут входить в произведение как в прямом, так и в инверсном виде.

Ниже приведён пример ДНФ:

[math]\displaystyle{ F(A,B,C,D,E) = \bar{A}B + A\bar{B}E + B\bar{C}D. }[/math]

В составе ДНФ, вообще говоря, могут присутствовать повторяющиеся слагаемые, а в составе каждого слагаемого — повторяющиеся сомножители, например:

[math]\displaystyle{ F(A,B,C,D,E) = \bar{A}B\bar{B} + A\bar{B}EA + B\bar{C}D + B\bar{C}D. }[/math]

С математической точки зрения такое клонирование бессмысленно, так как в булевой алгебре умножение любого выражения на само себя и сложение выражения с самим собой не меняет результата ([math]\displaystyle{ x+x=x; x\cdot x=x }[/math]), а сложение выражения с собственной инверсией и умножение на собственную инверсию даёт константы ([math]\displaystyle{ x+\bar{x}=1; x\cdot \bar{x}=0 }[/math]). В последнем выражении можно удалить повторяющиеся слагаемые и сомножители следующим образом:

[math]\displaystyle{ F(A,B,C,D,E) = \bar{A}B\bar{B} + A\bar{B}EA + B\bar{C}D + B\bar{C}D = \bar{A}\cdot(B\bar{B}) + (AA)\cdot\bar{B}E + B\bar{C}D = \bar{A}\cdot 0 + A\bar{B}E + B\bar{C}D = A\bar{B}E + B\bar{C}D. }[/math]

По этой причине ДНФ с повторяющимися слагаемыми и сомножителями используются обычно только со вспомогательными целями, например, при аналитическом преобразовании выражений.

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

Ниже приведён пример СДНФ:

[math]\displaystyle{ F(A,B,C,D,E) = \bar{A}BCDE + A\bar{B}C\bar{D}E + AB\bar{C}D\bar{E}. }[/math]

Значение СДНФ состоит в том, что

• для каждой конкретной функции её СДНФ единственна и однозначна;
• СДНФ имеет однозначное соответствие с таблицей истинности функции. Каждое слагаемое СДНФ соответствует одной строке в таблице истинности, где функция равна единице. Таким образом, число слагаемых в СДНФ равно числу единичных значений, которые принимает булева функция в своей области определения;
• СДНФ элементарно получается из таблицы истинноcти функции;
• СДНФ удобна в качестве базового выражения для минимизации функции, в ней особенно просто находятся слагаемые, пригодные для «склейки».

Пример нахождения СДНФ

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

[math]\displaystyle{ x_1 }[/math]	[math]\displaystyle{ x_2 }[/math]	[math]\displaystyle{ x_3 }[/math]	[math]\displaystyle{ f(x_1, x_2, x_3) }[/math]
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

В ячейках результата [math]\displaystyle{ f(x_1, x_2, x_3) }[/math] отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных, при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:

• [math]\displaystyle{ x_1 = 0 }[/math]
• [math]\displaystyle{ x_2 = 0 }[/math]
• [math]\displaystyle{ x_3 = 0 }[/math]

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: [math]\displaystyle{ \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} }[/math]

Переменные второго члена:

• [math]\displaystyle{ x_1 = 0 }[/math]
• [math]\displaystyle{ x_2 = 0 }[/math]
• [math]\displaystyle{ x_3 = 1 }[/math]

[math]\displaystyle{ x_3 }[/math] в этом случае будет представлен без инверсии: [math]\displaystyle{ \overline{x_1} \cdot \overline{x_2} \cdot x_3 }[/math]

Таким образом анализируются все ячейки [math]\displaystyle{ f(x_1, x_2, x_3) }[/math]. Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

Совершенная ДНФ этой функции:

[math]\displaystyle{ f(x_1, x_2, x_3) = (\overline{x_1} \land \overline{x_2} \land \overline{x_3}) \vee (\overline{x_1} \land \overline{x_2} \land x_3) \vee (\overline{x_1} \land x_2 \land \overline{x_3}) \vee (x_1 \land x_2 \land \overline{x_3}) }[/math]

См. также

• Дизъюнктивная нормальная форма
• Конъюнктивная нормальная форма
• Совершенная конъюнктивная нормальная форма