Теорема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

х	У	z	основные	f(x,y,z)
			конъюнкции
			┐х┐y┐z
			┐х┐y z
			┐х у┐z
			┐х у z
			х ┐y┐z
			х ┐y z
			x у┐z
			xуz

Основные конъюнкции (или конституенты_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 и, применяя второй закон дистрибутивности.

Дата добавления: 2014-01-04