Алгоритм приведения формулы к ДНФ

1) Выражаем все логические операции, участвующие в по­строении формулы, через дизъюнкции, конъюнкции и отрица­ния, используя эквивалентности и определения операций .

2) Используя законы де Моргана, переносим все отрица­ния к переменным и сокращаем двойные отрицания по правилу .

3) Используя закон дистрибутивности , преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

В результате применения получается ДНФ данной формулы.

Приведение формулы к КНФ производится аналогично приведению ее к ДНФ, только вместо п. 3 применяется 3'. Используя закон дистрибутивности преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.

Пример: Приведем к ДНФ формулу .

Выразим логические операции через .

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания: .Используя закон дистрибутивности, приводим формулу к ДНФ: .