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

Теорема 3.2. (о функциональной полноте).

Для любой булевой функции f найдётся формула , представляющая функцию f. Если f ¹ 0, то существует представляющая её формула , находящаяся в СДНФ и такое представление единственно. Если f ¹ 1, то существует представляющая её формула , находящаяся в СКНФ и такое представление единственно.

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

Алгоритм построения СДНФ по таблице истинности

1. Отметить те строки таблицы, в последнем столбце которых стоят единицы.

2. Для каждой отмеченной строки выписать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму переменную или её отрицание, если значение переменной равно 0.

3. Все полученные конъюнкции связать знаком дизъюнкции.

Алгоритм построения СКНФ по таблице истинности

1. Отметить те строки таблицы, в последнем столбце которых стоят нули.

2. Для каждой отмеченной строки выписать дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включать саму переменную или её отрицание, если значение переменной равно 1.

3. Все полученные дизъюнкции связать знаком конъюнкции.

Пример 3.7. Найти СДНФ и СКНФ функции f(x,y,z), заданной таблицей истинности:

СДНФ: .

СКНФ:

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

1. Привести её к какой – нибудь ДНФ.

2. Удалить все члены дизъюнкции, содержащие переменную вместе с её отрицанием (если такие окажутся).

3. Из одинаковых членов дизъюнкции удалить все, кроме одного.

4. Из одинаковых членов каждой конъюнкции удалить все, кроме одного.

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

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

Полученная формула и является СДНФ данной функции.

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

Пример 3.8. Найти СДНФ для формулы .

Приведём к ДНФ:

Во второй конъюнкции не хватает или , поэтому добавим элемент :

Из одинаковых членов дизъюнкции удалить все, кроме одного:

Пример 3.9. Найти СКНФ для формулы .

Имеем: