Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 82
Текст из файла (страница 82)
Аналогично, рассматривая остальные сцепленные пары внутренних состояний, получаем граф Ср (рис. 5.38, а), показывающий условия соцветности сцепленных состояний. В этом гра- 14 31 П 31 13 5» фе каждая вершина взаимно однозначно соответствует паре О. 41 4. 51 сцепленных состояний, кото- 14 5» (3, 41 рая играет роль веса соответствующей вершины, дуги графа О, г» (1, 41 показывают условия соцветнос- (2, 3] ти сцепленных пар. Отношение соцветности обладает свойством 42, 51 транзитивности. Расширим снгнатуру этого графа добавлением транзитивно замыкающих дуг.
Согласно свойству транзитивностн полученный граф в дальнейшем будем называть графом расцеплекия. Условия, при которых сцепленные вершины могут быть окрашены в один цвет, определяются следующим утверждением. Утверждение. Если вершина о(Я;, 5 ) графа расцепления соединена путном с полным подграфац ооъедикение весов вершин которого равно носителю графа сцепления, тпо длл вершин 50 Я не существует условия, при котпором эти вершины соцветпкы. В рассматриваемом случае ии одна пара сцепленных вершин не может быть соцветна, так как каждая вершина графа расцепления соединена путем с вершинами (оз, и4, об, ов), которые после добавления транзитивно замыкаюших дуг образуют полный подграф, объединение весов вершин которого равно носителю графа сцепления.
Производим расцепление сцепленных состояний (Яь Яз) и (Яз, Яб) расширением входных векторов а и с. В результате заданная таблица переходов автомата эквивалентируется табл. 5.28. Матрица смежности (см. табл. 5.22) преобразуется в матрицу смежности, представленную в табл. 5.29. Табяииа 5.25 Таблииа 5.29 452 Гл. 5. Прикладиал и>сорил алгоритмов 3 5.6. Семаитииеское ослабление функциокальиоб свлзкости 453 После удаления ребер (51, Яз) и (5з, 53) хроматическое число графа сцепления равно 2: Ко = (51> Яз Яв)> К1 = (52, 54). Соединяя соцветные вершины ребром, получаем граф сцепления для определения значений второго разряда кодов внутренних состояний.
Граф сцепления для второго разряда представляет собой полный граф на пяти вершинах (51, 52, 53, 54, 55). Этот граф содержит зацрешенные фигуры 9; — циклы нечетной длины: С1 = ЦЯь 52) (Яг, 5з), (Яз 54) (54, 53), (51, 55)), С2 Ц51> 53)> (53> 55)> (52> 55)> (52> 54)> (51> 54))> Сз = ЦЯм 52)> (52, Яз), (51> Яз))> С4 = Ц52, Яз), (Яз, 54), (52, 54) ), Св = ЦЯз 54) (54 55) (Яз 55)) Св = Ц51> 54)> (51> Яв)> (54> 55))> Сг = Ц51, Яг) (51> 55) (Яг 55)) Св = Ц51 > 52) > (51> 54) > (52> 54) ) > Сз = ЦЯг, 5з) (52> 53)> (Яз 55))> Сго = Ц51> 53)> (51> 54)> (53 54)) Сы = ЦЯг, Я4), (Яг, 55) > (54> Яв)) > С = Ц51, Яз), (51, 55), (53, Яв)) Семантическая таблица — табл.
5.30. Таблица 5.30 Очевидно, что граф расцепления, соответствуюший второму разряду, получается из графа расцепления первого разряда путем удаления вершин, взвешенных расцепленными состояниями, и инцидентных им дуг. После удаления вершин и1 и иг получаем, что ни одна пара сцепленных вершин не может быть соцветна. Поэтому расцепление пар (51, Яг), (52> 55)> (53, 54), вошедших в минимальное покрытие ЦЯ1, 52), (51, 55), (52, 55), (Яз, 54) ) табл.
5.30, производим расширением входных векторов а 6, с. После удаления ребер (Я1, 52)> (51, Яб), (Яг, 55), ~53> 54), вошедших в покрытие, раскрашиваем граф сцепления в две краски: Ко = (Ям 52, 55) К1 = (Яз, 54). В результате расширения входных векторов таблица переходов (см. табл.
5.28) зквивалентируется табл. 5.31. Таблица 5.31 Таблица 5.32 Матрица смежности (см. табл. 5,29) преобразуется в матрицу смежности, представленную в табл. 5.32. После двухкомпонентной раскраски вершины 51 и 53 соцветны — им соответствует краска 00. Соединяя зги вершины ребром, получаем, что граф сцепления, соответствуюший третьему разряду кодов, представляет собой треугольник с носителем (51, 54, 55) и двуугольник на вершинах (52, Яз).
Граф расцепления для зтого разряда представлен на рис. 5.38,б. Согласно атому графу если Вершины (Яз, 54) соцветны, то вершины (51, 54) или вершины (54> 55) > (Яг, Яз) могут быть соцветны. Вершины (51, Яв) не могут быть соцветны из-за однозначной идентификации внутренних состояний кодами. Отсюда получаем две раскраски графа сцепления: Ко = (51> Яз> 54), Кг = (52> 55) или Ко (52> 53> 54> 55)> К1 (51)' Для определенности выбираем первую раскраску. Окончательно получаем следуюшие коды внутренних состояний: Я1 — 000, Яг — 101, Яз — 010, 54 — 110, Яб — 001. О 1 2 3 4 5 5 7 О яэя)яя 1 2 3 Я1 ЯЬ Гл. 5.
Прикладная теория алгоришмов После замены штрихов у входных векторов а, 5, с соответствующим расширением этих векхоров внутренними переменными получаем условия переходов элементов памяти, представленные в хабл, 5.33. Тазлпив 5.33 Функционал (р(С), как и в предыдущем решении, равен 4.
9 5.1. Решение проблемы повторной функциональной декомпозиции в булевой логике В гл. 2 (32.2) было введено понятие функциональной декомпозиции. Рассмотрим проблему синхеза функциональной декомпозиции для общего случая, когда переменные, соотвехствующие строкам и столбцам, в матрице Вейча пересекаются. Представим заданное булеза пространство Р(Х) в виде декартова произведения Р(Х,) х Р(Хь) пространств Р(Х,), Р(Хь), (Х,1(.1 (Хь) = (Х1, (Х.М(Хь) = а. Каждой хочке просхранства Р(Х,) взаимо однозначно сопоставим вершину о, 6 У, графа С, = (У„к)), а точке просхранства Р(Хь) — вершину оь 6 1"ь графа (яь = (Уь о).
Тогда граф С = (Ув (1 УЬ) ()1! Ц1)) г=' = Г='а + Г='Ь! определит исходное пространство Р(Х). При эхом если булева функция у(Х) в этом пространстве принимает единичное значение в точке Х;, то вершины о,, б У, и иьь 6 Уь, соохветствуюшие зхой точке, соединены неинверсным ребром (иш, иьин 6 У1, 'если у(Х) принимает нулевое значение, то вершины и,, н оь, соединены инверсным ребром (и... иь,у 6 ()О, если же функция ДХ) в хочке Х( = Хеи Хь,, (вектор Х; есть результах конкатенации векхоров Х,, и Хь)) не определена, хо (о„, иь,.у ф ((1, Уо.
Полученный граф К(у) являехся графом Кенига и имеет два сорха ребер: неинверсные и инверсные. Очевидно, что каждая вершина и,, б У, взаимно однозначно соответствуех осхахочной булевой функции Де)„, а„, ..., н„, Хь), а вершина оь) 6 Уь — остахочной функции Дх„аь(. )1 ) ць,+,, ..., аь„) в разложении Шеннона по строчным 55.7. Решение пробяемы повшориоа декомпогииии 455 и столбцевым переменным соответсхвенно: 1(х„хь) = ч Й х 1(Ег,хь), Еу 44 а„а„...ааь, '% е)ЕХ) 1(х Хь) = „~ 65 х ДХ„Е1), Е ++ аь,аь„,...аь„. ЧП) ведХь Рассмотрим, например, булеву функцию (1 на О, 1, 4, 17, 18, 26, 30, '(0 на 2, 3, 11, 19, 29.
В качестве Х, выберем переменные х1, хт, в качесхве Хь — пе- ременные хз, хв, хь. Тогда граф Кенига К(у), определяющий зту функцию, имеех вид, представленный на рис. 5.39,а. При этом я) яь Ф)тя О 1 2 3 О 1 2 3 (О, 1, 4, 51(2. 51 (31 а 5 Рис. 5.39 вершине верхнего яруса, которая взвешена вектором Х, = О, соответствуех осхаточная функция вида (1 на 0,1,4, ДО хз хв хз) ~ О ца ! ! вершине нижнего яруса, взвешенной векхором 2, соохветсхвует осхаточная функция (1 на 2,3, У(х1, хт, 2) = (О нз 0 Очевидно, чхо поиск декомпозиции функции ДХ1, хт,..., Х5) можно свесхи к нахождению склеивания вершин внутри яруса, при кохором не образуехся цикл длины 2, состоящий из инверсного и неинверсного ребер.
В данном случае в нижнем ярусе склеиваются вершины (О, 1, 4, 5) и (3, 6) (рис. 5.39, 6). Закодировав полученные множесхва (О, 1, 4, 5), (3, 61 и (2) в просхранстве Р()р1, )рз) значениями О, 1 и 2 соотвехственно, получаем декомпозицию исходной функции ДХ1, хх, ..., Хь) в виде ~(Х1! Х2, ...) Х5) = Р(Х1, Х2! )р1(ХЗ) Х4) Хь), )рх(ХЗ! Х4) Хь))) 15.7. Решение проблемы повторной декомпозиции 457 456 Гл.5.
Приклоднол тео ил алгори>пмов где 11 на О, 8, 10, 13, 14, 10 на 1 2 5 9 12 11 на 2, '!О на013456 !1 на 3,6, )рз(хз х4, хь) = 10 на 0 1 2 4 Для поиска обьективных причин, определяющих декомпозицию булевых функций в общем случае, предложим теоретико-графовую интерпретацию атой задачи. Для построения декомпозиции функции у (Х) определим понятие графа кротиворечивости. С»прочным графом противоречивости Снр(Х,) = (ьз) У„р)) называется граф, каждая вершина о; которого взаимно однозначно соответствует вектору Х,,: (Х,,) и У~ 77 С 'г",~, (о;„о)л) Е 0;,р н (ЛХь,) фХ' Хь,) уЕ ~(Х;л, Хь )), С>полбцевым графом противоречивости С„р(Хь) = (Уь> Унр) называется граф, каждая вершина о которого взаимно однозначйо соответствует вектору Хь,: (хь!) н ц,, У„~ с ~',2, (!аул) иу>) Е жуир и (ЗХ>н) (у(Ха;) Хзе) уЕ У(Ха>) Хзл)) Названия графов цротиворечивости Сир(Х,) и слнр(Хь) соответственно »строчной» и»столбцевой» указйвают на возможность задания графа Кенига К(у) = (1', 0 ь>ь; (уь, Ц!), определяющего булеву функцию у(хь, хз,..., х„), в виде соответствующей двумерной таблицы Вейча, в которой каждая строка (столбец) задает соответствующую остаточную функцию в разложении Шеннона.
Теорема 5.7 (А.В. Горбатов). Булава функция у'(Х) декомпоэируема в виде Р(>рь(Х,), )р2(Х,), ...,>Рь(Х,), Хь) тогда и только тогда, когда ближайшее большее целое двоичного логарифма хроматического числа >з(Сир(Х,)) графа противоречивости ).'„р(Х,) = (Ъ~„У р) меньше !Х,~: у(Х) = Р( р (Х,), !о (Х,), ..., р (Х,), Хь) н (1Одз й(0 р(Х»))1 ( ~Х ~, (5 3) где ь — ~1об уз(цир(Х ))], (] — знак ближайшего большого це- лого. Рассмотрим функцию 1 1 на 1,4,9,11,13,14,17,19,20,28, 1О на 0>6,12,15,16,18,22,23,24,26,29 Граф Кенига, соответствующий разложению заданного пространства Р(хз, хз, ..., хь) = Р(хз, хз, хз) х Р(х4, хь), имеет вид, представленный на рис. 5.40. Построим граф противоречивости для строчных остаточных функций Снр(Х,) (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
