Преобразование ДНФ в СДНФ

Шаг 3.

Если в ДНФ есть несколько одинаковых элементарных конъюнкций, то оставляем только одну - это преобразование приводит к равносильной формуле, т.к. xVx=x.

Шаг 4.

Делаем все элементарные конъюнкции правильными с помощью следующих двух преобразований:

- если в элементарной конъюнкции переменная входит со своим отрицанием, то удаляем эту конъюнкцию из ДНФ.

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

Шаг 5.

Преобразуем правильные конъюнкции в полные. Пусть в некоторую элементарную конъюнкцию не входит переменная x, тогда рассмотрим выражение (x )и повторить шаг 2 и 3. Если недостающих переменных несколько, то проделать аналогичные преобразования со всеми недостающими переменными.