С.В. Яблонский - Введение в дискретную математику (1060464), страница 46
Текст из файла (страница 46)
Очевидно, что все остальные конъюнкции, которые будут при атом получены, соответствуют ве максимальным граням и, следовательно, поглощаются простыми имплнкантами. Пример 10. Возьмем фупкци»о ~(хо х,, х,), аадапную табл. 1. Для нее имеем совершенную к.
н. ф. )(х„хм х»)=(х, Чх, Чх,) (х, Чх» Чх,), ГЛ. ь диз'ьюпитивпыи иОРМАЛьиыи ФОРМЫ оА5 Производим раскрытие скобок и упрощеиия1 (х, о' х, Ч х,) (х, Ч х, Ъ' х,) = х,х, ~/ х,х, '/ х,х, Ч ~/Х,ХА Чх,х, ~/ХАХА '~/х,хА ЧХАХА А/хАхА- х,хАЧ х,х, Ч х,х, Аl х,х, Аl х,х, Ч х,х,. Сокращенная д. п. ф. имеет вид Яо = Х,х, Ч х,х, Ч х х, А~ х х, Ч х х А Ч х,х,. й' Ь,х, йг Х 1 / Уз огиз Рис. 6 Ее совершенная д. н.
ф. есть, очевидпо, ОА ОА Я= )/ х, д,....,с хо А ООА+... +ОА ОЗ и имеет сложность Еи(И)= 25, Каждой грани, содерн<ащейся в Уо соответствует элементарная конъюнкция, имеющая не менее двух множителей с отрицаниями и не менее одного множителя без отрицаний. В то же время каждой конъюнкции вида хх;х„, где ать/, $ФЙ и /чь Й, соответствует грань, принадлежащая множеству У,. Отсюда вытекает, что все копъюикции вида х~х;хА (1чь/, (оь Й, у ть Й) являются простыми импликаитами функцви / и ОА О ~/ (ХАТХА 1/ Х1Х~ХА ~/ Х1Х~ХА) Р, ьА) <ооъиоА,МА — сокращеннаяд.н.ф.
для /. Очевидно,ЬА(йс)=3 ~ ) 30. Г5А Даииый пример показывает, что сокращенная д.н.ф. для функции / может иьгеть большее число членов, чем совершепная д. и. ф. Она легко усматривается и из геометрических соображений и соответствует циклу из ребер (см. рис.
6). П р и м е р 11. Рассмотрим функцию /(хо х„х,, х„х,): /(а„..., ао) т... 1 при 1~~ аА+ ... +ао(~3, ~Дат О в остальных случаях, у З1З ч. т. нккотовыи пвиложвния к киви нвтикн $5. Тупиковость на основе геометрических представлений. Методы построения тупиковых д. н.ф. Определение. Покрытие множества №, состоящее из максимальных (относительно №) граней, называется неприводимым, если совокупность граней, получающаяся из исходной путем выбрасывания любой грани, не будет покрытием №.
Определение. Д. н.ф., соответствующая неприводимому покрытию множества №, называется тупиковой (в геометрическом смысле). Пример 12. Для функции 1(хи х„х,), заданной табл. 1, как видно из рис. 6, йГ, - Л-- () )ух () )у «в«з « г«з «,«з является неприводимым покрытием, а И-х,х,Чх,х,7х,х, — тупиковой д. н.ф. (в геометрическом смысле).
Теорема 3. Понятия тупиковой д.н. у1. относительно преобразований 1 и 11 и тупиковой д. и, 1б. в веометрическом смысле эквивалентны. В дальнейшем мы будем говорвть просто о тупиковых д. н. ф., не указывая определения, из которого мы исходим. Заметим, что определенные нами д.н.ф.— сокращенная, тупиковая и минимальная находятся в следующем соотношении.
Тупиковая д. н. ф. получается из сокращенной путем отбрасывания (удаления) некоторых членов. Минимальная (относительно Ьв) д.н.ф. является тупиковой. Среди тупиковых д. н, ф. найдется минимальная (относительно Ь) д.н ф. Рассмотрим теперь более сложный пример на построение тупиковых д. н. ф., используя геометрические соображения. Пример 13. Пусть 1(хи хь хн х,) задана табл. 5. На рис. 7 изображено множество №. В № вмеются следующие максимальные грани: №, №, № — ребра, №, №, Ф„№ — грани (двухмерные). Таким образом, покрытию №() № 0№() № 0№0 №Ц 0 № соответствует сокращенная д. н. ф. гл. $.
днньюнктивные ЕОРИАльные ФОРмы 317 Таблпка Б Две грани № и № входят в любое покрытие, так как только онн покрывают соответственно точки (ОИ1) и (10И). Для покрытия точки (0000) нужно взять либо грань №, либо грань №. а) Взята грань №. Остается покрыть две точки (ИОО) и (И01), '"г что осуществляется дву- 7 ф мя способами: либо взя- 7МУ тием ребер № и №, лн- аа 4 бо взятием ребра №. Следовательно, получаем два неприводимых «~ покрытия: № ц № ц № ц № ц №, № ц № ц № ц №. Озарю> (дада б) Взята грань №. Рис. 7 Остается покрыть три точки (1000), (ИОО) и (И01) — что монано сделать двумя способами: либо взяв ребра № и №, либо взяв ребра № и №.
Здесь мы имеем еще два неприводимых покрытия: )бац)уац)уац)рац№, )уацЖац)уацд~а0№. Для построения тупиковых д.н.ф. нужно заметить, что максимальным граням №, ..., № соответствуют простые импликанты Ка УаУ„К, х Р„ Ка = У,Х„Ка У,х„ Ка ~ хвтахаа Ка хахаУа> Ка ~ хаУаУа.
$1$ ч. ч. некОтОРые пРплол(ения к кивеРнетнки Мы имеем: Чх,х, Ч х,х, Чх,х,х, Ч х,х,х„ Ч УзХа Ч ХзХз Ч ХзхгХ за Чх,х, Чх,х, Чх,х,х, Ч Х,У,х„ Ч Х зХ4 Ч хзхз Ч ХзхзХ з Ч ХзХзх а~ з в(заа) 1 в(заз) = з ь(заа) 12. Раз Х,Х, Йз = Х,Х, Ра, - У,Уз зза = УзХз Ея(раз) = 9, Зз з~ з к,' ''' Пусть ззз=(Рз, ..., Ра) и Р,— любая точка*) такая, что РзФаз', (мы считаем, что 1за1). Составим таблицу (см. табл. 6), в которой О, если Р, фдг„, (1 1, ...,и), а 1, если Р, ен з"з' „(у - О, 1, ...з Х). Очевидно, что первый столбец — нулевой, так как Р, Фзз'О а в каждом столбце, отличном от первого, содержится хотя бы одна единица. Значит, первый столбец отличается от всех остальных. Для каждого 1 (0~! <Х) найдем множество Е, всех номеров строк, в которых столбец Р, содержит 1 (отличается от столбца Р,). Пусть К,= (ея, ..., евпз).
Составим выражение 8 (янЧ" Чезвп) з 1 и произведем преобразование 81 Ч- Чбз, рассматривая символы е как булевы величины. После этого в полученном выражении ликвидируем поглощаемые или дублирующие члены, т. е. совершаем преобразованпя з) Точка Рз вводится для того, чтобы бьзла видна связь задачи о покрытии с задачей расповяававия, Теперь перейдем к построению алгоритма для нахождения всех тупиковых д.
н. ф. с пспользозанием геометрических идей. Алгоритм построения тупиковых д. н. ф. Мы исходим из покрытия множества зз', системой всех его максимальных грапей гл. 1. дизъюнктиВные ногмальные ФОРмы 319 вида А В~/А А, АЧА А. Мы получим выражение Ч81', являющееся частью выражения Ч 81. Каждое слагаемое в Ч 8~' будет определять неприводимое покрытие. Таблица Е Действительно, будем рассматривать номера строк как булевы переменные, а каждое подмножество максимальных граней функции 1 — как набор значений этих переменных: если грань входит в подмножество, то соответствующая ей переменная равна единице, а если нет, то равна нулю.
Тогда выражение е» Ч...Ъ'е1мв равно единице тогда и только тогда, когда в подмножество входит максимальная грань, покрывающая точку Рь а выраженно 8, (е;1 ~/ ... ~/е;лц1) 3 1 равно единице тогда и только тогда, когда подмножество максимальных граней покрывает №, Поэтому подмножество из максимальных граней, соответствующих переменным из одного слагаемого выражения ~/Ь', является покрытием Ж1. Более того, поскольку выражение ~/81' 320 Ч. Ч. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ содержит в качестве слагаемых в точности все свои простые емплнканты (ср. со с.
314), а им (как нетрудко ваметить) соответствуют неприводнмые покрытия ачо все иеприводнмые покрытия (и только они) строятся таким способом. Таблица 7 П р и м е р 14, Рассмотрим функцию Яхь х„х,) (см. табл. 1). Для нее множество ача состоит иа 6 вершин, которые можно занумеровать числами 1, 11, ..., У1. Максимальными гранями (см. рис. 6) являются ребра, которые аанумеровапы арабскими цифрами. Составим таблицу (см. табл. 7). Мы имеем Е,=(1, 6), Еаа (1, 2), Еап=(2, 3), Еач (3, 4), Еч (4, 5), Ечз (5, 6). Тогда Чса (1Ч6)(1Ч2)(2ЧЗ)(ЗЧ4)(4Ч5)(5Ч6) (1Ч2 6) (3Ч2 4) (5Ч4 6) (1 ЗЧ2 3 6Ч1 2 4Ч2.4 6) (5Ч4 6) 1 3 5Ч2 3 5 6Ч12 4 5Ч2 4 5 6Ч Ч1 3 4 6Ч2 3 4 6Ч1.2 4 6Ч2 4 6 1 3.5Ч2.3 5 6Ч1.2 4 5Ч1 3 4 6Ч2 4 6.
Мы получаем пять непрпводимых покрытий или пять тупиковых д. н. ф.: И, хахаЧхахзЧхзх„ И, ° хахзЧх,х,Чх,х, Чхзх„ Иа хаха ЧУаха Ч хахз Ч хзхаа Иа х,хз Ч хзхз Ч х,хз ЧУах„ И,=У,х, Чх,х, Чх,х,. Две ил ннх И, и Из являютсл мпппмальнымп, ГЛ. 1. ДПЗЪЮНКТНВНЫЕ НОРВ1АЛЬНЫЕ ФОРМЫ 321 Данный алгоритм оказывается эффективным и для примера, рассмотренного нами на стр. 316. Однако уязе данса для функций, зависящих от небольшого числа переменных, алгоритм может оказаться весьма трудоемким п практически непригодным.
Это связано с рядом обстоятельств: громоздкостью таблицы, сложностью преобразоВаиня сус 'Зс - вес бс Н, В КОНЕ ПЮМ СЧЕТЕ, бОЛЬШИМ ЧИСЛОВ1 тупиковых д. н. ф. В заключение приведем пример функции от четырех переменных, имеющей много тупиковых д.
н. ф. Пример 15. Рассмотрпм функцию 1(х„х„хох,), где вс(хс, Хв, Хв, Хс) = ХсхсХвхс ХсХсХсХс. Очевидно, данная функция является симметрической и ее копыонктнвпая нормальная форма имеет впд 1(ХСс Хвс Хес Хе) = (Х, 1К' Х, 1/ Х, Ъ' Х,) (Х, Ч Х, Ч Х, Ч Х,), что позволяет сразу выписать ее сокращеннуво д.н.ф. х,х, Ч хсхчв Ъ' х,х, ~/ х,х, ~/ х,х, Ч х,х, Ву 1к хсхв Ч хсхв сс хвхс и хсхс с1 хвхс Ч хвхс Отсюда видно, что ввпожестсо Ук имеет 12 максимальных граней, как<два нз которых двумерная. На рис. 8 изобрае 11М жено расположение грат неп. Мы имеем сферу, образованную максимальными гранями. Занумеруем Рис.
8 Рнс. 9 грани так, как это указано на том же рисунке. Для анализа непрнводнмых покрытий удобнее использовать развертку сферы на плоскости (см. рнс. 9), прн этом нужно 1~ Внесение в вискисснию меюмвсик» 323 ч ч некотоРые пРилОжения к к»»веРнетикн иметь в виду, что левый и правый край (помечены штриховкой) должны быть склеены, и вертикальные отрезки сходятся (показано штриховой линией). На развертке грани делятся на верхний слой 1 — 3, средний пояс 4 — 9 п нижний слой 10 — 12. Далее идет перебор непрпводпмых покрытий в зависимости от фрагмента этого покрытия Рис. 1! Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
