С.В. Яблонский - Введение в дискретную математику (1060464), страница 47
Текст из файла (страница 47)
10 в среднем поясе. Такой перебор учитывает возможность продолжения этого фрагмента в пределах верхнего и нпжнего слоя. Особенно важно иметь в виду запреты граней (помечается минусом) н необходимость покрыть некоторые вершины (помечается жирной точной). Для каждого случая подсчитывается число вариантов по формуле а Ь с, где а — число вариантов в среднем поясе, Ь— в верхнем слое и с — в нпл»пем слое.
1) Нп одна грань пз среднего попса ке взята. Для покрытия помеченных точек (см. рпс. 16) необходимо взять целиком верхний и нижний слои: а Ь с=1 1 1 1. 2) В среднем поясе взята одна грань 4. Для покрытия помеченных точек (см.
рис. 11) необходимо взять грани 2,3 и 11, 12: а Ь с=б 1 1 6. 3) В среднем поясе взяты две грани рядо⻠— 4 и 5. Для покрытия помеченных точек (см. рпс. 12) необходпмо взять грани 3 и 11, 12: а Ь с 6 1 1 = 6. Рис. 13 Рис. 13 4) В среднем поясе ванты две грани череа одну— 4 и 6. Для покрытия помеченных точен (см. рис. 13) не' обходимо взять грани 3 и 12; а Ь с = 6 1 1 = 6, гл. 1.
дпзыонктпвпык погмлльнын догмы 525 б) В среднем повсе взнты две грани через две — 4 и 7. Для покрытия помеченных точек (см. рпс, 14) необходимо взять грани 2 в 12, Чтобы получить неприводп>юе покрытие, пз верхнего слоя можно взять только одну грань 1 нлн 3. Если выбирается грань 1, то вз нингпего слоя (грань 10 аапрешспа) однозначно добавляется грань 11. Наконец, в случае выбора грани 3 пз нпжнего слоя (грань 11 запрещена) однозначно добавляется грань 10: а Ь.с=3 2 1=6. Ф ~Я~ фбфВ Рве.
14 Рпс. 15 6) В среднем поясе ввяты трк грани через одну— 4, 6 и 8. Для покрытпя помеченных точек (см. рис. 15) необходимо взять пз верхнего слоя любую грань, например, 1. Тогда из нннгнего слоя можно взять любую из двух граней 11 и 12 (грань 10 запрещена): а Ь.с= =2 3 2 12. 7 — 8) В среднем поясе взяты трп грани, из которых две распело>пены рядом, а третья идет через одну грань (см.
рнс. 16 и 17). (Оба варианта симметричны, поэтому достаточно разобрать одын пз них.) Рпс. 17 Рнс. 16 Для покрытия помеченной точки (см. рпс. 16) необходпмо взять грань 12. г1тобы получить неприводимое покрытие, можно взять еще только одну грань нз верхнего слоя, а именно 1: а Ь с = 6 1 1 = 6. 324 ч. ч. ПекотоРыи ПРнложиния к кивжРпитики 9) В среднем поясе взяты четыре грани (никакие три из нвх ве идут подряд) — 4,5 и 7,8 (см. рпс. 18). Для получения ненрпзоднмого покрытия нуигпо добавить одну произвольную грань из верхнего слоя, напримор 1.
Тогда из нижнего слоя однозначно возьмется еще одна Рис. 18 грань 11 (10 и 12 аапрещепы): а Ь с=331 9. Всего мы получаем 58 неприводимых покрытий и, следовательно, 58 тупиковых д. н. ф. и из них б — минимальных. 9 6. Некоторые однозначно получаемые д.
н.ф. Процесс построения минимальных. д.н.ф., исходя из совершенной д. н.ф., может быть охарактеризован следующей схемой (см. рпс. 19). 77НПУГР к кф. > ПонИНЮлЬНЫЕ лиф. Ряс. 19 Сначала получа7от сокращенную д. н.ф. (при зтои на данном п7аге возможно усложнение д. и. ф.). Далее однозначный процесс переходит в ветвящийся — процесс построения всех тупиковых д, н.ф.
и, наконец, из тупико- гл ь дмзъюнктивнык ногыАльпыв Фогыы $25 вых д. н. ф. выделяются минимальные д. н. ф. Весьма трудоемким авеном етого процесса является построение тупиковых д.н.ф. (ветвящаяся часть). Его можно пытаться упростять за счет двух обстоятельств. а) Заранее удалить часть членов сокращенной д. н.
ф., не участвующих в построении тупиковых д. н.ф., и тем самым сократить перебор (просматривая подмножества оставшейся части сокращенной д. н. ф.). б) Произвести удаление части членов сокращенной д. н. ф. так, чтобы оставшаяся часть позволяла построить хоть одну минимальную д. н.ф. Желательно при етом, чтобы данный шаг осуществлялся однозначным образом. В данном параграфе будут приведены построения двух таких однозначно определяемых д.
н. ф. О п р е д е л е н и е. Максимальная грань 67з относительно множества У~ называется ядровой, если существует такая точка и из Уь что ажйз и сс не принадлежит никакой другой максимальной (относительно Ф~) грани. Пример гб. Рассмотрим функцию )(хь иь л,) (см. табл. 8).
На рнс. 20 изобран<ено множество Ур и максимальные грани — ребра Уь У, и Уь Легко видеть, что У, и У, являются ядровыми гранямн, так как точка (0,0,0) покРыта только )Уо а (1,1,1)- только Уе Таблица 8 и, Рвс. Ю О п реда л е н и е. Множество всех ядровых граней для У, называется аВром.
Очевидно, что в предыдущем примере (Уь У,) является ядром. Легко видеть, что ядро входит в каждое неприводимое покрытие. Отсюда следует, что грани, покрываемые ядром, не принадлежат нн одному из неприводимых ° покрытий. 326 ч у неКОтОРые пгпложенпя к кпвегнетпке Определение. Д. н.ф. Иав, получающаяся пз сокращенной путем выбрасывания всех простых имплпкант, соответствующих максимальным граням, которые покрываются ядром, называется д. и.
сд. Квайна. Теорема 4 (Квайн [42[). Для каждой сдунк!!ии !(хь ..., х„) (~ФО), существует единственная д.нф. Квайна. Определение д.н.ф. Квайна фактически дает основу для формулировки алгоритма, позволяющего строить д н.ф. Квайна. Пример 17. Для функции, заданной табл. 8, имеем сокращенну!о д. н. ф.
Ис =х,х,Чх,х,Ч х,х,. Ядро (№, №) (см. с. 325) покрывает грань №, которой соответствует простая импликанта х,х,. Таким образом, д. н. ф. Квайна имеет внд Икв х,х! Ч х,х,. Итак, от сокращенной д. н. ф. путем выбрасывания некоторых импликант возможно перейти к однозначно определенной д. н. ф. — д. н. ф. Квайна, которая реализует ту >ке функцию и содержит все ее тупиковые д. н. ф. Следующий шаг в направлении продления однозначной части процесса минимизации связан с определением д.
н. ф. типа ХТ. Определение. Д. н. ф., соответствующая покрытию множества № совокупностью всех таких максимальных граней (относительно №), которые входят по крайней мере в одно из неприводимых покрытий, называется д. и. у). тина ХТ и обозначается Ист Очевидно, д. н. ф. Ивт получается логическим суммированием (т. е. дизъюнкцией) всех тупиковых д. н.ф. функции г' и последующим приведением подобных членов. Как вытекает кз определения, для каждой функции !(х„..., х„) существует единственная д. н. ф.
типа УТ, ее реализующая. Она получается из сокращенной д.н.ф. удалением некоторых членов. О пределе н ие. Пусть сеж Уо тогда совокупность П„- всех максимальных граней (относительно №), содеожащих точку сс, называется нучкол!, нроходящивв через а. Определение. Пусть а!и№ и Л'лв некоторая максимальная грань такая, что с! ви !тлв. Точка и называется гл. г.
дизъюнктивныв новмлльнык Фовмы 221 регулярной точкой (относительно йгко и стс), если существует точка Р ен № ' 1икг " Пв ~ П . Првмер 18. Для функции 1(хохг,х,) (см. табл. 8 и рис. 20) возьмем 'в качестве точки а вершину (0,0, 1) и максимальную грань №. Очевидно, сею№. Покажем, что точка а является регулярной точкой (относптельно № я №). Пусть р=(0,0,0). Мы имеем: Л„- (гт'„сгг)с П- (сгсг) и П- ы П-. з а' Определение. Максимальная грань сук~ для № называется регулярной, если каждая ее точка является регулярной (относптельно гт'к.
и сгсс). В нашем примере, очевидно, № будет регулярной гранью, а сгсс и № ве являются регулярными гравямн. Теорема 5 (1О. И. Журавлев (5)). Для того чтобы простая импликанта К' Яункуии 1 пе сгринадлежала д. н, уг. типа ХТ необходимо и достаточно, чтобы соответствусоисая лсаксилсальная грань Л~л была регу- Рвс. 21 ларкой. Доказательство. Необходимость. Пусть К'— простая пмплпканта функции (, К' не принадлежит д.н.ф. типа ХТ, а сг'л вопреки утверждению теоремы, не является регулярной гранью. В таком случае существует точка се, се ен Улч, которая не регулярна. Обозначим через р„..., рг точки пз множества сгст ~ ггткь (см, рис.
21): ~т "сук.- А, ",(.) По условию П ~тп-, ..., П„- С~П-, позтому найдутся грани Икг ° " Л'ке соответственно г г принадлежащие пучкам П-й, ..., П, такие, что Йф йслг, ..., се Ф )оиг 328 ч. ч. некОтОРые ПРнложення к кпвеРнетнке Очевидно, о () )и о 0 ° ° ° 0 ~~' о= )у( к к~ кз Это покрытие позволяет построить непрпводпмое покрытие множества Кь При зтоы могут выброситься некоторые из граней У ю ..., У ю в то же время грань Укз обяза- л,' ''' к' тально войдет в неприводимое покрытие, так как только она одна покрывает точку а. Мы получаем, что К' входит в некоторую тупиковую д. п.
ф. и, следовательно, в д. п. ф. типа ХТ. Полученное противоречие доказывает, что грань У , †регуляр. Д о с т а т о ч н о с т ь. Пусть Ук,— регулярная грань, покажем, что К' не принадлежит д. н. ф. типа ХТ. Обозначим через аь..., а, точки из множества Ж „.„, т. е. — я„..., а,). В силу регулярности Уя, найдутся точки ~о ..., р, пз У~ ~У з такие, что П- ып;, ..., Пе,~п„-,. Воаьмем произвольную тупиковую д.н.ф. И функции 1 и соответствующее ей иеприводпиое покрытие.
Это покрытие л', =)у, и... а)у, очевидно, покрывает точки рь ..., ), соответственно граиямн А, ° Кй (см. рис. 22). В сплу включеннй (»), зги же грани покрывают точки Рвс. 22 ао...,и~,т. е. д'й () ... 0 Ай ~)уно. Поэтому грань Уя, не прпнадлел1ит данному неприьодкмому покрытию, а простая имплнканта К' — д.н.ф. И. Теорема полностью доказана. Данная теорема дает основу для формулировки алгоритма, позволшощсго строить д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
