Совершенные нормальные формы

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

Примеры: Пусть задана функция трех переменных 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