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

Определение. Совершенной дизъюнктивной формулой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой:

1. различны все члены дизъюнкции;

1. различны все члены каждой конъюнкции;
2. ни одна конъюнкция не содержит одновременно переменную и отрицание этой переменной;
3. каждая конъюнкция содержит все переменные, входящие в формулу, т. е. имеет вид

,

где дизъюнкция берется по всем наборам с =(с₁, с₂, …, с_n) из 0 и 1, для которых F( c )=1.

Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x₁, x₂, …, x_n) существует такая формула F₁, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F₁ выражает собой формулу F. Формула F₁ определена однозначно с точностью до перестановки дизъюнктивных членов.

Определение. Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:

1. различны все члены конъюнкции;
2. различны все члены каждой дизъюнкции;
3. ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной;
4. каждая дизъюнкция содержит все переменные, входящие в исходную формулу, т. е. имеет вид

,

где конъюнкция берется по всем наборам с =(с₁, с₂, …, с_n) из 0 и 1, для которых F( c )=0.

Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x₁, x₂, …, x_n) существует такая формула F₁, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F₁ выражает собой формулу F. Формула F₁ определена однозначно с точностью до перестановки конъюнктивных членов.

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

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

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

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

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

Пример 27.

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

1. ;

2. ;

3. .

Решение.

1. .

2.

3.