С.В. Яблонский - Введение в дискретную математику (1060464), страница 44
Текст из файла (страница 44)
Переход от д. н. ф. И к д. н. ф. И' Ч К' — преобразование, осуа~ ществляемое путем удаления мноя<ителя х, . Данное преобразование определено тогда и только тогда, когда И'ЧК' И. Определение. Д. н. ф. И, которую нельзя упростить при помощи преобразований 1 и П (их применить нельэя), называется тупиковой д. и. ~д.
(т. д. и. у1.) (относительно преобразований 1 и П). Пример 2. Очевидно, д. н. ф. И л,ЧУ,х, будет тупиковой относительно данных преобрааований. На основе этих двух преобразований можно сформулировать алгоритм упрощения д. н. ф. (Этот алгоритм легко усматривается, и в силу того, что Ь(И') < .ь (И) п Ь(И'ЧК')~Ь(И), он является разновидностью алгоритма наискорейшего спуска. Легко видеть также, что среди тупиковых д. н. ф. функции Дко ..., х.) всегда содержатся и минимальные, может быть, правда, не все.) 1.
Выбирается какая-нибудь д. н. ф. для функции ~(ль ..., Е„) в качестве исходной. Таковой можно взять, например, совершенную д. н. ф., так как существует простой способ ее построения. Таблица 2. Осуществляется упорядочивание в исходной д. н. ф. слагаемых и в каждом слагаемом — множителей. Это упорядочение можно эадать записью д. к. ф.
П р н м е р 3. Рассмотрим функцию ((ко к„к,) (си. табл. 1). В качестве исходной д. н. ф. для пее возьмем 302 ч. т. некотогыв пгпложенпя к кивегнвтикв совершенную д. н. ф. в выберем два упорядочения: одно естественное и второе специальное: И У~УзУз Ч У~Узхз Ч х~хахз Ч х~х~Уз Ч х1хьтз Ч х~хзхн И вЂ” У,УчУ, Ч х,х,х, Ч х,х ~хз Ч х,х,х, Ч х,х,х, Ч х,х,У,.
3. Затем производится просмотр записи д. н. ф. (слева направо); длп очередного члена К, (1= 1, ..., з) сначала пробуют применить операцию удалении влемептэрпой конъюнкции Кб если это невозможно, то просматривают члены х;„" конъюнкции К, слева направо (т = 1, ..., г) вь ат К; х;,д, ...Ах~„ вч и применяют операцию удаления множителя х;„до тех пор, пока это удается.
После этого переходят к следующей элементарной конъюнкцни. Закончив обработку последней элементарной конъюнкции, еще рав просматривают полученную д. н. ф. слева направо и пробуют применять операцию удаления элементарной конъюнкции в). В реэультате втого мы получаем искомую д. в. ф. Очевидно (с учетом того, что будет иэлоягено в 3 4), имеет место следующий факт. Теорема 1. Д. и. ф., полученная в результате применения алзоритяа упрощения, является тупиковой д. и. ф.
(относительно преобразований 1 и 11). Пример 4. Для функции )(хе х„х,), заданной табл. 1, вовьмем в качестве исходной д. н. ф. совершенную д. н. ф, Рассмотрим ее упорядочение, задаваемое записью Я', и проследим работу алгоритма. 1. Конъюнкция х,х,У„ очевидно, не может быть удалена, Однако можно удалить множитель У„ так как У$У3 У УЗУ$ Ч х$УЗУВ В результате мы получаем конъюнкцию х,х„ иэ которой уже нельзя выбросить ни одного множвтеля. 2.
Конъюнкцию х,х,х, удалить также нельзя. Легко видеть, что иэ нее множитель х, удалить невозможно, в то время как операция удаления множителя У, применима. ') Нсобходпкость вторичного просмотра можно проиллюетрнровзть примером (см табл. В). гл. ь дкзъюнктпвные ЕОРмлльпые ФОРмы 303 Мы получаем конъюнкцию У,х„которую упростить путем удаления множителей невозможно. 3. Конъюнкция У,х,х, может быть удалена, так как Узхз Узхзхз Ч Узхзхз.
4. Конъюнкция хзУзУз также может быть удалена (см. п. 1). 5. Конъюнкцию х,х,У, удалить нельзя. Однако, возможно выбросить множитель х,. В результате мы получим конъюнкцию х,У„из которой уже нельзя выбросить ни одного множителя. 6. Конъюнкция х,х,х„очевидно, удалена не может быть. Из нее можно удалить множитель х,. Мы получаем конъюнкцию х,х„которую упростить путем удаления множителей невозможно. Мы получаем д. н. ф. У,У, Ч У,х, Ч ,Чх,х, Чхзх,.
Вторичный просмотр этой д. н. ф. с целью удаления конъюнкций упрощений не дает. Следовательно, д. н. ф. зз„где б(з - УзУз ЧУзхз Ч хзУз Ч хзхз, являетси результатом применения алгорима упрощения. Приведенные расчеты моншо сделать так, иак указано в табл. 2. Для той же функции возьмем другую упорядоченяость ее совершенной д. н.
фл В" УзУзУз Чх,У,Уз Ч хзУ,х, Ч х,х,хз ЧУ.хзхзЧ х УзУз. В табл. 3 приводятся основные этапы работы алгоритма для этого случая. Следовательно, в этом случае в качестве результата применения алгоритма упрощевня получаем д. н. ф. Вз УзУ,ЧУ,Е,Чх,х,. Из данного примера вытекает, что результат применения алгоритма упрощения зависит от выбора упорядочения исходной д. н. ф.; так, например, Ь®(ззз1 8, Ез(ззз) б, нлн Ез(РЦчь Ез(йз). Тупиковые д. н. ф. могут иметь различную сложность и, в частности, отличаться от минимальныл. В связи с этим возникает вопрос, возможно ли для любой функции ~(хз, ..., т„), исходя из некоторого упорядочивания, получать, примення алгоритм упрощения, минимальную д. н.
ф. Ответ па зто дает следующая теорема. Таблица 2 пссяеяте свя нпнь ~оннцся рв шага Д.м.ф. н рвссмвтриваеыып цорядон Вид операции хьхьхъЧ хьхвхаЧ хлхъхьЧ Чх,хь.тз У х,хехнУх,хвхз хзхвЧхьхтхзЧхьтььзЧ хтхьхзЧ Ч хьхьхьЧ хьхьтв хзхзЧ хтхзУ хьхьхт У хьхахвУ Ч хьхьхзЧхьхзха теЧхьхзУхь **ъЧ ЧхьхвхьЧхтхвха хьхз Ч хдхаЧ хьхьха Ч хьхвхз ~ьУ зтхъЧ хтхз Ч хьхеть хьхз У хгха Ч хе хе У хъхь Вторичный просмотр ничего не дает хтхвтв удвленпе х, удвленле х, хьхвхв хьхьхв удаление хьххха удаление хь.т тз хьхьхв * х,х удаление х, хьхьхв уделенпе х, Алгоритм окончен Таблица 3 Иссяедте- ыая нонь- вннция ьть шага Внд оцервцни Д.и.ф. и раасыатрцваеыыл порядон Верный просмотр д. н.
ф. ьх,хвЧ втьхъЧх ьхзУ Чхь лтзЧхзхтхзЧхьх* ь тз*з У хв*ьхвЧ хъхь тв Ч Ч хьхетв Ч хвхьхвЧ хгхвхв хъхаЧ хьхзУ хъхьхвУ Ч хьхвхъЧ хзхьхьЧ хьхтхь хтхзЧ хьх.Ч хьхзЧ хьхтхь Ч Ч хзхгтвЧ хтхвхз хьхьЧ хьхьЧ хьхвЧ хьхзЧ Чхвтьхв Ч хьхттз Ы*,~У'~.У ~Ч Ч., Ч... Второй просмотр д. н. ф. хтхзУ ьхеЧ ьхзЧ ттзУхьхь хтхдЧ хь5ЧхтхъУ хвхвЧ хтхь ~ч~рЧ хтхвЧ хьхзЧхтхь хьхвУхгхзУхьхвУхьхз хьхзЧ ьхъЧхт хтхъЧхьхвЧ хьхв хьхвхв удаление х, удвлеиве хз хв*ьхв удаление х, х,хзхв уделенне х, удаление х, удаление х,*,х, хзхьхв хьхттз ъьхв хтхз хьхв хзхв хьхв Алгор 7 8 9 10 11 12 неприменимы удаление х,х, непримевпььы удаление х,х, неприменимы птм окончен 884 Ч.
Ч, НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ Гл. ». Днзъюнктнвнь»е нОРИАльные ФОРмы 30$ Теорема 2. Пусть )(х„..., х ) — произвольная буле» ва функция () Ф 0) иВ ~/ К; — ее произвольная тупико»-» вая д. н. ф. (относительно операций 1 и 11); тоеда существует таков упорядочение совер»ивиной д. н.
ф., иг которого при помощи алгоритма упрощения получается тупиковая д. и. ф. В. Доказательство. Возьмем совершенную д. н. ф. для функции )(х„..., х„) с естественным порядком членов и множителей 9~ 1/ х»д" дх ° -о а» ап (а», „а„) »»о»,...,ап)» о» оп Пусть х, д»... д» х„— ее произвольный член. Так как )(о„..п о.) 1, то существует по крайней мере одна конъюнкция К», »» (о„..., о.), из тупиковой д. н.
ф. такая, что К,(о„..., о„) 1, а» а», откуда следует, что К»-х», 8» .., д»х» . В члене о» ап х, д»... д» х„выберем порядок множителей так, чтобы сначала следовали множители, не входящие в К», а затем — в произвольном порццке множители из К». Следовательно о» х, д»». д»хп Ко К»»о> (о (о„..., о,)). Мы получим некоторое упорядочение совершенной д. н. ф., характеризуемое записью В'. Легко видеть, что алгорптм упрощения в д. н.
ф. В' для каждой конъюнкции К, Кч,> приведет к одному иа исходов: либо ее удалит, либо преобразует в конъюнкцию Кчаи Отсюда д, н. ф. В» являющаяся результатом работы алгоритма, состоит только из злементарных конъюнкций, входящих в д. н. ф. В. С другой стороны, в силу тупиковости д.н.ф. В должно быть В» В, ' С лед с тв не. В силу того, что среди тупиковых д. и. ф. содержатся обязательно и минимальные относительно Ь (не обязательно все), алгоритм упрощения при 308 Ч.
Ч. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КНБЕРИЕТИКЕ надлежащем выборе упорядочения совершенной д. и. Ф. нозволяет находить и минимальную д. н. 1б. Замечание. Из доказательства теоремы видно, что для построения всех тупиковых д. и. ф. при помощи алгоритма упрощения из совершенной д. н. ф. достаточно прн естественном порядке конъюнкций варьировать только порядок множителей в конъюнкциях. Таким образом, для построения минимальной д. н. ф. следует перебрать все указанные упорядочения совершен- 3 ной д. н. ф. Р1' Ч К1 и для каждого из них произвести 11 вычисление на основе алгоритма упрощения. Это дает возможность оценить трудоемкость такой процедуры минимизации. Как видно из определения, однократное применение алгоритма упрощения достаточно просто и содержит Ь„(у1') проверок возможности удайения кокъюлкцни, ю Ьв(К1) проверок возможности удалепня множителя из К;(1 т, ..., в') и при вторичном просмотре не более ь„(в1') проверок возможности удаления конъюнкций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
