Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама, либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ).
Примеры: Пусть задана функция трех переменных f(X,Y,Z).
1. ¬XYZ v X¬Y¬Z v ¬X¬Y¬Z — это совершенная ДНФ.
2. (XvYvZ)(Xv¬YvZ)(¬Xv¬YvZ) — это совершенная КНФ.
3. (XvY)(XvZ) — это не совершенная КНФ, т.к. например, в первую сумму не входит переменная Z.
4. XYZ — это совершенная ДНФ.
Теорема
1. Любая булева функция, не являющаяся тождественным нулем, имеет только одну СДНФ, с точностью до расположения членов.
2. Любая булева функция, не являющаяся тождественной 1, имеет только одну СКНФ, с точностью до расположения членов.
Доказательство теоремы проведем конструктивно, как решение следующей задачи: по данной таблице истинности построить СДНФ.
Решение рассмотрим на примере функции f(X,Y,Z) заданной таблично при n=3.
Пример. По данной таблице истинности построить СДНФ.
Решение.
| X | Y | Z | Основные конъюнкции | f(X,Y,Z) |
| 0 | 0 | 0 | ¬X¬Y¬Z | 0 |
| 0 | 0 | 1 | ¬X¬YZ | 1 |
| 0 | 1 | 0 | ¬XY¬Z | 1 |
| 0 | 1 | 1 | ¬XYZ | 0 |
| 1 | 0 | 0 | X¬Y¬Z | 0 |
| 1 | 0 | 1 | X¬YZ | 1 |
| 1 | 1 | 0 | XY¬Z | 1 |
| 1 | 1 | 1 | XYZ | 1 |
Основные конъюнкции (или конституенты_1), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные X,Y,Z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные X,Y принимают значение 0 и поэтому в произведение входят их отрицания, а переменная Z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равна ¬X¬YZ.
Очевидно, что конъюнкция ¬X¬Y¬Z равна 1 только на наборе (0,0,0), а ¬X¬YZ равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция ¬X¬Y¬Z v ¬X¬YZ равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д.
Т.е. получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так, для нашего примера, имеем
¬X¬YZ v ¬XY¬Z v X¬YZ v XY¬Z v XYZ
Задача. По данной таблице истинности построить СКНФ.
Конституента_0 для набора нулей и единиц (которые принимают переменные X,Y,Z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случае в произведение входит ее отрицание.
Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем:
f=(XvYvZ)(Xv¬Yv¬Z)(¬XvYvZ)
Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции ¬f , а затем использовать f=¬(¬f) и законы де Моргана.
Построим СКНФ для нашего примера на основании замечания.
1. Строим СДНФ для отрицания.
¬X¬Y¬Z v ¬XYZ v X¬Y¬Z
2. Используем законы де Моргана
f=¬(¬f) = ¬(¬X¬Y¬Z v ¬XYZ v X¬Y¬Z) = ¬(¬X¬Y¬Z)&¬(¬XYZ)&¬(X¬Y¬Z) = (XvYvZ)(Xv¬Yv¬Z)(¬XvYvZ)
Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.
1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ.
2. Если в некоторый конъюнкт К (т.е. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная Y, то этот конъюнкт заменяем на эквивалентную формулу K&(Yv¬Y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида (Yv¬Y).
3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.
Замечание: Для построения СКНФ в дизъюнкт не содержащий скажем переменную Y добавляем формулу вида Y¬Y, т.е. этот дизъюнкт заменяем на эквивалентную формулу D v Y¬Y и, применяя 2-й закон дистрибутивности.
Пример. Построить СДНФ для функции f при помощи эквивалентных преобразований.
f = XvYZ = X(Yv¬Y)(Zv¬Z)vYZ(Xv¬X) = XYZvXY¬ZvX¬YZvX¬Y¬ZvYZXvYZ¬X =
=XYZvXY¬ZvX¬YZvX¬Y¬ZvYZ¬X