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

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

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

Нормальные формы

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

Иногда будем допускать в элементарной конъюнкции наличие повторов элементов.

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

Иногда будем допускать в ДНФ наличие повторов элементов.

Пример 25.

Следующие формулы находятся в ДНФ:.

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

Иногда будем допускать в элементарной дизъюнкции наличие повторов элементов.

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

Иногда будем допускать в КНФ наличие повторов элементов.

Пример 26.

Следующие формулы находятся в КНФ:

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

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.