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

Пусть – логическая переменная, . Введем обозначение . Выражение

называется литерой. Литеры и называются контрарными.

Отметим, что тогда и только тогда, когда .

Теорема (о разложении функций по переменным): Каждую функцию алгебры логики при любом можно представить в следующей форме:

где дизъюнкция берется по всем возможным наборам .

Это представление называется разложением функции по переменным.

Следствие 1: Разложение функции по одной переменной, например имеет вид:

Следствие 2: Разложение функции по переменным имеет вид:

Элементарной конъюнкцией, или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией, или дизъюнктом называется дизъюнкция литер.

Например, формулы и – дизъюнкты, формулы и – конъюнкты, является одновременно и дизъюнктом, и конъюнктом, а формула не является ни элементарной дизъюнкцией, ни элементарной конъюнкцией.

Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).

Например, формула – ДНФ, формула – КНФ, а формула является одновременно КНФ и ДНФ.

Теорема: 1) Любая формула эквивалентна некоторой ДНФ. 2) Любая формула эквивалентна некоторой КНФ.

Опишем алгоритм приведения формулы к ДНФ (КНФ).

1. Выразить все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалентности и определения операций .

2. Используя законы де Моргана, перенести все отрицания к переменным и сократить двойные отрицания по правилу .

3. Используя закон дистрибутивности, преобразовать формулу так, чтобы все конъюнкции (дизъюнкций) выполнялись раньше дизъюнкций (конъюнкций).

В результате применения пп. 1 – 3 получается ДНФ (КНФ) данной формулы.

Например, для формулы имеем:

, то есть получено две ДНФ:

ДНФ ; ДНФ .

Для формулы можно получить (выполнить самостоятельно): КНФ , КНФ .

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

Пусть – набор логических переменных, – набор нулей и единиц. Конституентой единицы набора называется конъюнкт . Конституентой нуля набора называется дизъюнкт . Отметим, что (или ) тогда и только тогда, когда , , … , .

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

Например, формула есть конституента единицы , формула есть конституента нуля , формула – СДНФ, формула – СКНФ, а формула не является СДНФ.

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

Теорема (о функциональной полноте): Для любой булевой функции найдется формула , представляющая функцию . Если , то существует представляющая ее формула, находящаяся в СДНФ:

и такое представление единственно с точностью до порядка следования конституент единицы. Если , то существует представляющая ее формула, находящаяся в СКНФ:

и такое представление единственно с точностью до порядка следования конституент нуля.

Константа 0 может быть представлена только СКНФ ( ), а константа 1 – только СДНФ ( ).

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

Решение: Строим следующую таблицу.

				Конституенты единицы	Конституенты нуля

По пятому столбцу таблицы формируем:

СДНФ ,

а по шестому столбцу формируем:

СКНФ .

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

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

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

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

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