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

(Алгоритм приведения формул булевых функций к ДНФ (КНФ)).

Шаг 1. Все подформулы A вида B  C (т.е. содержащие импликацию) заменяем на BVC или на (B&C).

Шаг 2. Все подформулы A вида B ~ C (т.е. содержащие эквивалентность) заменяем на (A&B) V (A&B) или на (AVB)&(AVB).

Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана.

Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).

Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ.

Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.

Совершенной дизъюнктивной нормальной формой (СДНФ) называет­ся ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъ­юнкции состоят из одного и того же набора переменных, в который каж­дая переменная входит только один раз (возможно, с отрицанием).

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