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

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

·       в ней нет одинаковых множителей (элементарных дизъюнкций);

·       в каждом множителе нет повторяющихся переменных;

·       каждый множитель содержит все переменные, от которых зависит булева функция (каждая переменная может входить в множитель либо в прямой, либо в инверсной форме).

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

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

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

$x_1$$x_{1}$	$x_2$$x_{2}$	$x_3$$x_{3}$	$x_4$$x_{4}$	$f(x_1,x_2,x_3,x_4)$$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

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

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

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

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: $x_1\vee <!--\; \vee \; -->x_2\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$x_{1}\vee x_{2}\vee {\overline {x_{3}}}\vee {\overline {x_{4}}}$ 

Остальные члены СКНФ составляются по аналогии:

$(x_1\vee <!--\; \vee \; -->x_2\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_4})\wedge <!--\; \wedge \; -->(x_1\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\vee <!--\; \vee \; -->x_3\vee <!--\; \vee \; -->x_4)\wedge <!--\; \wedge \; -->(x_1\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\vee <!--\; \vee \; -->x_3\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_4})\wedge <!--\; \wedge \; -->(x_1\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_4})\wedge <!--\; \wedge \; -->$$({x_{1}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land$ 

$(\stackrel{¯<!--\; ¯\; -->}{x_1}\vee <!--\; \vee \; -->x_2\vee <!--\; \vee \; -->x_3\vee <!--\; \vee \; -->x_4)\wedge <!--\; \wedge \; -->(\stackrel{¯<!--\; ¯\; -->}{x_1}\vee <!--\; \vee \; -->x_2\vee <!--\; \vee \; -->x_3\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_4})\wedge <!--\; \wedge \; -->(\stackrel{¯<!--\; ¯\; -->}{x_1}\vee <!--\; \vee \; -->x_2\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_4)\wedge <!--\; \wedge \; -->(\stackrel{¯<!--\; ¯\; -->}{x_1}\vee <!--\; \vee \; -->x_2\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_4})\wedge <!--\; \wedge \; -->$$({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land$ 

$(\stackrel{¯<!--\; ¯\; -->}{x_1}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\vee <!--\; \vee \; -->x_3\vee <!--\; \vee \; -->x_4)\wedge <!--\; \wedge \; -->(\stackrel{¯<!--\; ¯\; -->}{x_1}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\vee <!--\; \vee \; -->x_3\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_4})$$({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})$ 

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

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