Теорема1.3.1.
Совершенные нормальные формы
Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ).
Примеры: Пусть задана функция трех переменных f(x,y,z).
1.┐xyzVx┐y┐zV┐x┐y┐z - это совершенная ДНФ.
2.(х Vy Vz)(x V┐y Vz)(┐x V┐y Vz) - это совершенная КНФ.
3.(x V у) (x V z) - это не совершенная КНФ, т.к. например, в первую сумму не входит переменная z.
4.x y z - это совершенная ДНФ.
1. Любая булева функция, не являющаяся тождественным нулем, имеет только одну СДНФ, с точностью до расположения членов.
2. Любая булева функция, не являющаяся тождественной 1, имеет только одну СКНФ, с точностью до расположения членов.
Доказательство теоремы проведем конструктивно, как решение следующей задачи:по данной таблице истинности построить СДНФ.
Решение рассмотрим на примере функции f(x,y,z) заданной таблично (таб.1) при п=3.
Пример. По данной таблице истинности (таб.1) построить СДНФ.
Решение.
Таблица 1
|
Основные конъюнкции (иликонституенты_1), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные x,y,z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные х,у принимают значение 0 и поэтому в произведение входят их отрицания, а переменная z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равна ┐x┐yz.
Очевидно, что конъюнкция ┐x┐ y ┐z равна 1 только на наборе (0,0,0), a ┐x ┐y z равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция ┐x ┐y ┐zV┐x ┐y z равна 1 только на двух наборах - (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д.
Т.о. получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так для нашего примера, имеем
┐x┐yzV┐xy┐zVxy┐zVxy┐zVxyz .
Задача. По данной таблице истинности построить СКНФ.
Конституента_0 для набора нулей и единиц (которые принимают переменные x,y,z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случае в произведение входит ее отрицание.
Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем
f = (х V у V z) (х V┐у V┐z) (┐х Vу V z)
Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции f, а затем использовать f = ┐┐f и законы де Моргана.
Построим СКНФ для нашего примера на основании замечания.
1. Строим СДНФ для отрицания.
┐x┐y┐zV┐xyzVx┐y┐z
2. Используем законы де Моргана
f =┐┐ f = ┐x┐y┐zV┐xyzVx┐y┐z= ┐x┐y┐z &┐xyz& x┐y┐z =(х V у V z) (х V┐у V┐z) (┐х Vу V z)
Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.
1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ.
2. Если в некоторый конъюнкт К (т.е. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная у, то этот конъюнкт заменяем на эквивалентную формулу K&(yV┐y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида
(y V┐ у).
3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.
Замечание: Для построения СКНФ в дизъюнкт не содержащий скажем переменную у добавляем формулу вида y ┐ у, т.е. этот дизъюнкт заменяем на эквивалентную формулу DVy┐y и, применяя второй закон дистрибутивности.