Дискретная математика

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

• Часть 1
• | 2
• | 3
• | 4

Опишем два способа приведения к совершенным нормальным формам.

1-й способ – аналитический.

Приведение к СДНФ. Алгоритм приведения.

1. привести формулу с помощью равносильных преобразований  к ДНФ.
2. удалить члены дизъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);
3. из одинаковых членов дизъюнкции (если такие окажутся) удалить все, кроме одного;
4. из одинаковых членов каждой конъюнкции (если такие окажутся) удалить все, кроме одного;
5. если в какой-нибудь конъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой конъюнкции член    и применить закон дистрибутивности конъюнкции относительно дизъюнкции;
6. если в полученной дизъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

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

Пример 27.

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

1. ;

2. ;

3. .

Решение.

1. .

2.

3.

Приведение к СКНФ. Алгоритм приведения.

1. привести формулу с помощью равносильных преобразований  к КНФ.
2. удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);
3. из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;
4. из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного;
5. если в какой-нибудь дизъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член    и применить закон дистрибутивности дизъюнкции относительно конъюнкции;
6. если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

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

предыдущаяследующая