2.2.5. Совершенные конъюнктивные нормальные формы (СКНФ)
Пусть 
, тогда 
. Представим 
в виде СДНФ: 
Переходя к двойственным функциям в обеих частях равенства, используя при этом принцип двойственности и учитывая, что 
, получим
Поскольку 
, то последнее равенство можно переписать в виде:
Наконец, переобозначив везде в формуле 
,окончательно получим
(**)
Правая часть равенства (**)называется Совершенной конъюнктивной нормальной формой (СКНФ) функции 
.
Таким образом, выше доказано, что всякая булева функция, отличная от константы 1, представима в виде СКНФ.
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных (возможно, с отрицаниями). Конъюнкция нескольких элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).
Пример. Пусть дана таблица значений функции 
.
|
|
|
|
|
Просматривая все “единичные” наборы переменных (при которых функция принимает значение 1), получим представление А просматривая все “нулевые наборы”, получим СКНФ: | |
|
0 |
0 |
0 |
1 | ||
|
0 |
0 |
1 |
0 | ||
|
0 |
1 |
0 |
0 | ||
|
0 |
1 |
1 |
1 | ||
|
1 |
0 |
0 |
1 | ||
|
1 |
0 |
1 |
0 | ||
|
1 |
1 |
0 |
1 | ||
|
1 |
1 |
1 |
0 |
.
.| < Предыдущая | Следующая > |
|---|
