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

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

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

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

Краткая теорияПравить

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

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

$F(A,B,C,D,E)=\stackrel{¯<!--\; ¯\; -->}{A}B+A\stackrel{¯<!--\; ¯\; -->}{B}E+B\stackrel{¯<!--\; ¯\; -->}{C}D.$$F(A,B,C,D,E)={\bar {A}}B+A{\bar {B}}E+B{\bar {C}}D.$ 

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

$F(A,B,C,D,E)=\stackrel{¯<!--\; ¯\; -->}{A}B\stackrel{¯<!--\; ¯\; -->}{B}+A\stackrel{¯<!--\; ¯\; -->}{B}EA+B\stackrel{¯<!--\; ¯\; -->}{C}D+B\stackrel{¯<!--\; ¯\; -->}{C}D.$$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}}D+B{\bar {C}}D.$ 

С математической точки зрения такое клонирование бессмысленно, так как в булевой алгебре умножение любого выражения на само себя и сложение выражения с самим собой не меняет результата ($x+x=x;x\cdot <!--\; \cdot \; -->x=x$$x+x=x;x\cdot x=x$ ), а сложение выражения с собственной инверсией и умножение на собственную инверсию даёт константы ($x+\stackrel{¯<!--\; ¯\; -->}{x}=1;x\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x}=0$$x+{\bar {x}}=1;x\cdot {\bar {x}}=0$ ). В последнем выражении можно удалить повторяющиеся слагаемые и сомножители следующим образом:

$F(A,B,C,D,E)=\stackrel{¯<!--\; ¯\; -->}{A}B\stackrel{¯<!--\; ¯\; -->}{B}+A\stackrel{¯<!--\; ¯\; -->}{B}EA+B\stackrel{¯<!--\; ¯\; -->}{C}D+B\stackrel{¯<!--\; ¯\; -->}{C}D=\stackrel{¯<!--\; ¯\; -->}{A}\cdot <!--\; \cdot \; -->(B\stackrel{¯<!--\; ¯\; -->}{B})+(AA)\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{B}E+B\stackrel{¯<!--\; ¯\; -->}{C}D=\stackrel{¯<!--\; ¯\; -->}{A}\cdot <!--\; \cdot \; -->0+A\stackrel{¯<!--\; ¯\; -->}{B}E+B\stackrel{¯<!--\; ¯\; -->}{C}D=A\stackrel{¯<!--\; ¯\; -->}{B}E+B\stackrel{¯<!--\; ¯\; -->}{C}D.$$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.$ 

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

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

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

$F(A,B,C,D,E)=\stackrel{¯<!--\; ¯\; -->}{A}BCDE+A\stackrel{¯<!--\; ¯\; -->}{B}C\stackrel{¯<!--\; ¯\; -->}{D}E+AB\stackrel{¯<!--\; ¯\; -->}{C}D\stackrel{¯<!--\; ¯\; -->}{E}.$$F(A,B,C,D,E)={\bar {A}}BCDE+A{\bar {B}}C{\bar {D}}E+AB{\bar {C}}D{\bar {E}}.$ 

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

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

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

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

$x_1$$x_{1}$	$x_2$$x_{2}$	$x_3$$x_{3}$	$f(x_1,x_2,x_3)$$f(x_{1},x_{2},x_{3})$
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

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

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

• $x_1=0$$x_{1}=0$ 
• $x_2=0$$x_{2}=0$ 
• $x_3=0$$x_{3}=0$ 

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$ 

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

• $x_1=0$$x_{1}=0$ 
• $x_2=0$$x_{2}=0$ 
• $x_3=1$$x_{3}=1$ 

$x_3$$x_{3}$  в этом случае будет представлен без инверсии: $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->x_3$${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}$ 

Таким образом анализируются все ячейки $f(x_1,x_2,x_3)$$f(x_{1},x_{2},x_{3})$ . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

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

$f(x_1,x_2,x_3)=(\stackrel{¯<!--\; ¯\; -->}{x_1}\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{x_3})\vee <!--\; \vee \; -->(\stackrel{¯<!--\; ¯\; -->}{x_1}\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\wedge <!--\; \wedge \; -->x_3)\vee <!--\; \vee \; -->(\stackrel{¯<!--\; ¯\; -->}{x_1}\wedge <!--\; \wedge \; -->x_2\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{x_3})\vee <!--\; \vee \; -->(x_1\wedge <!--\; \wedge \; -->x_2\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{x_3})$$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}}})$ 

См. такжеПравить

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