Построение тупиковых ДНФ методом упрощения совершенной ДНФ

Рассмотрим алгоритм упрощения ДНФ, приводящий к тупиковой ДНФ Отметим, что среди тупиковых ДНФ всегда содержатся и минимальные, но не все.

1°. Для функции выбирается в качестве исходной какая-нибудь ДНФ Таковой можно взять, например, совершенную ДНФ, так как существует простой способ ее построения.

2°. Осуществляется упорядочивание в исходной ДНФ слагаемых и в каждом слагаемом – множителей. Это упорядочение можно задать записью ДНФ.

3°. Производится просмотр записи ДНФ слева направо. Для очередного члена сначала пробуют применить операцию удаления элементарной конъюнкции . Если это невозможно, то просматривают члены конъюнкции слева направо и применяют операцию удаления множителя до тех пор, пока это удается.

Затем переходят к следующей элементарной конъюнкции. После обработки последней элементарной конъюнкции еще раз просматривают полученную ДНФ слева направо и пробуют применить операцию удаления элементарной конъюнкции. В результате получаем ТДНФ.

Пример1. Рассмотрим функцию . В табличной форме:

Таблица 1

В качестве исходной ДНФ выберем совершенную ДНФ

,

рассмотрим ее упорядочение и проследим работу алгоритма.

1°. Конъюнкция не может быть удалена, но можно удалить множитель :

.

2°. Конъюнкция не может быть удалена, но можно удалить множитель :

.

3°. Конъюнкция , может быть удалена так как

.

4°. Конъюнкция также может быть удалена (см. п. 1°).

5°. Конъюнкцию удалить нельзя, но можно удалить множитель :

.

6°. Конъюнкцию удалить нельзя, но можно удалить множитель :

.

В результате получаем тупиковую ДНФ:

.

Если для той же функции взять другую упорядоченность ее совершенной ДНФ, например,

,

то в результате работы алгоритма упрощения получим другую тупиковую ДНФ:

.

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

Таким образом, тупиковые ДНФ могут имеют различную сложность и, в частности, могут отличаться от минимальных. В связи с этим возникает вопрос: возможно ли для любой функции , исходя из некоторого упорядочения, получить, применяя алгоритм упрощения, минимальную ДНФ? Ответ на этот вопрос дает следующая теорема.

Теорема. Пусть – произвольная булева функция () и – ее произвольная тупиковая ДНФ Тогда существует такое упорядочение совершенной ДНФ, из которого при помощи алгоритма упрощения получается тупиковая ДНФ .

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

Замечание. Из доказательства этой теоремы, которое мы опускаем, следует, что для построения всех тупиковых ДНФ при помощи алгоритма упрощения из совершенной ДНФ достаточно при естественном порядке конъюнкций варьировать только порядок множителей в конъюнкциях.

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

Выполним оценку трудоемкости такой процедуры минимизации.

Однократное применение алгоритма упрощения содержит проверок возможности удаления конъюнкции, проверок возможности удаления множителя из и при вторичном просмотре не более проверок возможности удаления конъюнкций, то есть

.

Общее число упорядочения с учетом замечания, равно , причем

.

Это число меньше, чем , то есть этот алгоритм лучше, чем алгоритм перебора всех ДНФ, но все же он остается весьма трудоемким.