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

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

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

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

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

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

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

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

[math]\displaystyle{ x_1 }[/math]	[math]\displaystyle{ x_2 }[/math]	[math]\displaystyle{ x_3 }[/math]	[math]\displaystyle{ x_4 }[/math]	[math]\displaystyle{ f(x_1, x_2, x_3, x_4) }[/math]
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

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

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

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

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: [math]\displaystyle{ x_1 \vee x_2 \vee \overline{x_3} \vee \overline{x_4} }[/math]

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

[math]\displaystyle{ ({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 }[/math]

[math]\displaystyle{ (\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 }[/math]

[math]\displaystyle{ (\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}) }[/math]

См. также

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