Алгоритм приведения к СДНФ c помощью равносильных преобразований

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

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

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

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

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

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

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

Пример.

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

1. ;

2. ;

Решение.

1. .

2.