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

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

Определение 1. Совершенной ДНФ называется ДНФ, в которой в каждый конъюнкт каждая переменная из набора { }входит ровно один раз, причем входит либо сама , либо ее отрицание .

Определение 2. Совершенной КНФ называется КНФ, в которой в каждый дизъюнкт каждая переменная из набора { }входит ровно один раз, причем входит либо сама , либо ее отрицание .

Для нахождения СДНФ и СКНФ исходной формулы составляется ее таблица истинности, а затем по ней строится требуемая совершенная нормальная форма. Так, для нахождения СДНФ:

1. Из таблицы истинности выбираем наборы переменных, на которых функция принимает значение 1, и соединяем их конъюнкцией. При этом если переменная принимает значение равное 1, то она входит без отрицания.

2. Все конъюнкции соединяем дизъюнкциями.

Для нахождения СКНФ:

1. Из таблицы истинности выбираем наборы переменных, на которых функция принимает значение 0, и соединяем их дизъюнкцией. При этом если переменная принимает значение равное 0, то она входит без отрицания.

2. Все дизъюнкции соединяем конъюнкциями.

Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким, чем ал­горитм, основанный на эквивалентных преобразованиях. Для нахождения СДНФ данную формулу приводим сначала к ДНФ, а затем преобразовываем ее конъюнкты в конституанты единицы с помощью следующих действий:

1. Если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ.

2. Если в конъюнкт одна и та же переменнаявходит несколько раз, то удаляем все такие переменные, кроме одной.

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

4. Если в полученной ДНФ имеется несколько одинаковых конъюнктов, то оставляем только один из них.

Описание алгоритма приведения КНФ к СКНФ путем тождественных преобразований аналогично вышеизложенному описанию алгоритма приведения ДНФ к СДНФ. Однако в п.3 введение недостающей переменной осуществляется с помощью закона исключенного третьего путем прибавления нуля.

Кроме того, СКНФ можно получить по найденной СДНФ. Для этого:

1. Получаем отрицание исходной формулы за счет выписывания недостающих конъюнкций через операцию дизъюнкции ().

2. Выполняем отрицание полученной формулы (.

Аналогично можно получить СДНФ по найденной ДНФ.

Пример.

Дана функция f(x, y, z) = (x ® y) ¯ . Получить СДНФ и СКНФ.

В п. 4.3 получили для f(x, y, z) = (x ® y) ¯ ДНФ: и КНФ: .

Используя преобразование, получим СДНФ:

= =

= = .

Используя преобразование, получим СКНФ:

=

.

Полученные совершенные формы соответствуют таблице истинности (см. п. 4.1).