Алгоритм нахождения СДНФ путем тождественных преобразований

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

2. Конъюнкты ДНФ преобразовываем в конституенты единицы по следующим правилам:

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

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

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

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

Пример 1-10. Найти СДНФ для ДНФ .

Имеем

.

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

Совершенно полиноминальная нормальная форма (СПНФ).

Существует еще и третья форма представления ФАЛ – совершенная поли номинальная нормальная форма (СПНФ).

Алгоритм построения СПНФ.

1. Исходную ФАЛ  представить в СДНФ.

2. В конституентах единицы СДНФ произвести замену .

3 Знак  между конституентами единицы в СДНФ заменить на знак .

4. Окончательно упростить выражение для в СПНФ путем раскрытия скобок, сокращения одинаковых слагаемых при использовании эквивалентностей: .