Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
1 АдАд^д V хдх2х3 У^д^з V _ удаление х2
V ХдХ2Хд V ХдХдХзУ ХдХ2х3
2 х2хаV АдХаХз V Ж1аг2ягя V Ад хгх3 V удаление ха
V ХуХ^С5
3 х^сь У ХдХ3 V ХдХйХд V АдХаХау ХдХ2Хд удаление х^хд
V ХдХ2х3У Х\ЧЧ
4 Х3Ха V АдХ3 V АдА^Ха V _ АдХа^з удаление Хд,т2ха
V А [ Х2Хд У Хд х2ха
5 Аа^зУ Агх3У ХдХ2х3У ХдХ2ха ХдХгХз удаление ха
6 хгг3\/ хдХаУ ХдХ3У хдх2хй ХдХвАд удаление х1
7 Х3Х3 V АдХа У X] Х3 V х2х3
Вторичный просмотр ничего не дает Алгоритм окончен
Таблица 3
м шага Д.н.ф. и рассматриваемый порядок Исследуемая конъюнкция Вид операции
1 Первый просмотр д. н. ф. ХдХдХдУ ХдХдХдУ Х2ХдХдУ Х1Х2Х;з удаление Хд
2 _ _ У а1ж2х3У Х3Х1Х2У Х1Х2Хд Л’кАдУ АдХ^аУ Х2Хд.Г3У_ ХдХдХд удаление х3
3 Ух1Х2х3Ух3х1хаУх1хвх3 хахау х1х2\/ а2х1х3У _ Х2Х^Хз удаление х2
4 V Х1Х2ЖдУ Х3Х1Х2У А1хйх3 х2х8У х1х2У хДх3У х5 х2х3 V АдА2Хз удаление Хд
5 V ХдХ1Х2У а1х2х3 Х2Ха V Х1Х2 У Х1Х3У Х2Хд V ХдХдХа удаление х3
б ух3х1х2ух1х2х3 Х2ХаУ ХдХаУ ХлХзУ АаХ3 V Х1Х2Х3 удаление Адх^Ад
7 V ХдХ2У Х1Х2ХЭ Второй просмотр Д. и. ф. «2ХВУХ1Х2У ХдХ8 V хахаУ х1хй 3?з неприменим
8 ХйХзУхдХаУх^дУ х2хзу ХдХа А1ха удаление ХдХ2
9 х^ГзУ ХдХд V Х2Хд у ХдХа Ад Ад ненримееимьг
10 ХаХдУх^гД/ ХдХдУ ХдХа ХдХа удаление х^в
11 _х^3УхдХ3У Х]Х2 ХдХ2 неприменимы
12 х2х3 V Агх3 V ХдХ2 Алгоритм окончен
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 305
Теорема 2. Пусть /(^1, ..хп) — произвольная буле-
в
ва функция (/^0) к91 = \/ К^—ее произвольная тупико-
1=-1
вая д. н. ф. (относительно операций I и II); тогда существует такое упорядочение совершенной д. н. физ которого при помощи алгоритма упрощения получается тупиковая д. н. ф. 91.
Доказательство. Возьмем совершенную д. н. ф. для функции /(#!, .,ж„) с естественным порядком членов и множителей
Г - V *?&...&
(стг,...,оГ1)
Ц(Г1,...,ст,|)=1
Пусть а?! & ... & ха —ее произвольный член. Так как /(о,, оп) = 1, то существует по крайней мере одна
конъюнкция /<ч, (щ, ..., сг„), из тупиковой д. н. ф.
такая, что
К|(о„ о„) = 1,
^ аЧ Т,
откуда следует, что /ц = & ? * • &^г * Я члене
* ?
°1 ап
^1 & « • * & ?п выберем порядок множителей так, чтобы сначала следовали множители, ее входящие в К(, а затем — в произвольном порядке множители из Ки Следовательно,
%1 & ш * ? & %п == -&сг'^Ч(с) " (01, ? ? О,,)).
Мы получим некоторое упорядочение совершенной д. н. ф., характеризуемое записью й'. Легко видеть, что алгоритм упрощения в д. и. ф. 91' для каждой конъюнкции Ка * Кца) приведет к одному из исходов: либо ее удалит, либо преобразует в конъюнкцию Кч<п. Отсюда д. н. ф. 9*1 являющаяся результатом работы алгоритма, состоит только из элементарных конъюнкций, входящих в д. и. ф. 91. С другой стороны, в силу тупиковости д. н. ф. 91 должно быть
011-91.
Следствие. В силу того, что среди тупиковых д. к. ф. содержатся обязательно и минимальные относительно Ь {не обязательно все), алгоритм упрощения при
20 с, В. Яблонский
506 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЙ К КИБЕРНЕТИКЕ
надлежащем выборе упорядочения совершенной д. п. ф. позволяет находить и минимальную д. н. ф.
Замечание. Из доказательства теоремы видно, что для построения всех тупиковых д. н. ф. при помощи алгоритма упрощения из совершенной д. н. ф. достаточно при естественном порядке конъюнкций варьировать только порядок множителей в конъюнкциях.
Таким образом, для построения минимальной д. н. ф. следует перебрать все указанные упорядочения совершен-* ,
ной д. н. ф. ЭР = \/ Кщ для каждого из них произвести .—1
вычисление на основе алгоритма упрощения. Это дает возможность оценить трудоемкость такой процедуры минимизации.
Как видно из определения, однократное применение алгоритма упрощения достаточно просто и содержит ?К(ЭР) проверок возможности удаления конъюнкции, ?б(/?|) проверок возможности удаления множителя из Я* (г = 1, ..,, в') и при вторичном просмотре не более Ьк(%1') проверок возможности удаления конъюнкций. Следовательно, число проверок не более
2 ?в («1) + 2?„ (Г) < (п + 2) 2".
г--1
Общее число вариантов упорядочения, как это следует из замечания, равно (и!)л и
(п1)‘ < (П1)г" < («")г” - г*"'11®".
Таким образом, число проверок для всех вариантов не более, чем
1од л / X
что значительно меньше, чем 2зЛ, т. е. этот алгоритм лучше, чем алгоритм перебора всех д. и. ф. В то же время трудоемкость алгоритма с использованием процедуры упрощений остается весьма значительной.
Остается обсудить еще одну возможность, влияющую на эффективность алгоритма — случайность выбора упорядочения, играющую роль при решении серии задач на минимизацию булевых функций. Разобьем все вышеуказанные упорядочения на «благоприятные» и «неблагоприятные», смотря по тому, дает или нет алгоритм упро-
ГЛ. і. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
307
щения минимальную д. н. ф. Тогда отношение ыисла благоприятных упорядочений к числу всех рассматриваемых упорядочений равна вероятности построения минимальной д. н. ф. при случайном выборе порядка. Можно было бы попытаться оцепить это отношение. Однако мы не будем этого делать ввиду того, что данная величина связана с конкретным алгоритмом, и ее оценка мало что будет говорить о трудоемкости других алгоритмов. Вместо этого мы возьмем в качестве меры трудоемкости алгоритма родственную характеристику — отношение числа р(/) минимальных д. п. ф. функции / к числу т (/) ее тупиковых д. и. ф., т. е. величину р{/)/т(/). Оказывается» что существуют функции с большим числом тупиковых д. н. ф. при относительно малом числе минимальных д. н. ф. Можно показать, что существует последовательность функций {/„}, для которой [2]
