Алгоритм нахождения СДНФ

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

а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то нужно удалить этот конъюнкт из ДНФ;

б) если в конъюнкт одна и та же литера х^δ входит несколько раз, то удалить все литеры х^δ, кроме одной;

в) если в некоторый конъюнкт не входит переменная y, то этот конъюнкт заменить на эквивалентную формулу применяя закон дистрибутивности, привести полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляется соответствующую формулу вида ;

г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставить только одну из них. В результате получается СДНФ.

Пример. Найдем СДНФ для ДНФ .

Решение. Имеем φ ~ ~

~ ~

~ ~

~ ~

~ ~

~ .

Алгоритм приведения КНФ к СКНФ аналогичен вышеизложенному описанию алгоритма приведенияДНФк СДНФ.