Эквивалентные преобразования Б.Ф. в СДНФ.

Опр. Преобразование которое дает равносильную формулу F₂

для исходной формулы F₁ дает эквивалентные формулы.

“склеивания” / ”расщепления” – правила.

10) склеивание

расщепление

Теорема. (Алгоритм последов-ти Э.П. для получения СДНФ).

Для любых двух равносильных формул f₁ и f₂ существует последовательность в виде равносильностей 1)-10)

1) Элиминация операций ( эквивалентный переход в базис Ø ,Ú , Ù). Пример: x yº Ú y

В исходной формуле или цепочки преобразований, какая-либо подформула реализована не в базисе, тогда пользуясь эквивалентностями 1) - 10) мы переходим к эквивалентной формуле в базисе.

2) Протаскивание отрицаний. С помощью инволютивности и привил Моргана значок опер. преобраз-ий протаскивается к идентификатору.

3) Раскрытие скобок: (скобки-операнды конъюнкции раскрываются по правилу дистрибутивности конъюнкции относительно дизъюнкции.

4) Приведение подобных: применяется идемпотентность. Идемпотентность конъюнкции – удаляет повторные члены, а затем идемпотентность

дизъюнкции удаляет повторные элементарные множественные ( т.е. элементарные) конъюнкции.

5) Расщепление переменных: когда в дизъюнктивной форме после n^a шагов какие-то множественные конъюнкции не содержат все переменные (не являются элементарными конъюнкциями) тогда и применяется правило расщепления.

6) Сортировка перем-ых: используем св-во коммутативности конъюнкции, а сортировка элементарных конъюнкций в ДНФ используя св-во коммутативности дизъюнкции позволяет получить СДНФ с учетом того, что элементарным конъюн-иям

должны предшествовать элементарные конъюнкции

у которых больше значков отрицания и с приоритетом их расположения над переменными с меньшими индексами.