Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 57
Текст из файла (страница 57)
Сима>ег логических струк>пур а и>аналогических багисак 315 4) Присоединяем путь и(хб) < и(хв) ( и(хы), соответствую- щий четвертой простой импликанте. Имеем диаграмму Н» — (17», 57»), Ъ~ — — (х), хт, хз, х», хв, хв, х)о, хм), 7У» = ((хб>хэ), (хб,х)), (хв,хы), (хв, х»), (Х1> ХЮ)> (Х1> ХЗ)> (ХЗ, Х2), (Х2, Х»))'. 5) Построение следующего пути, реализующего простую,им- пликанту х)хтхв, приводит к противоречию в диаграмме, если не производить расщепление первичных термов Х1 и Х2, так как по- строение этого пути с включением в него вершин диаграммы Н», взвешенных х1 или х2, приводит к возникновению лишних путей.
Расщепление отмечаем штриховкой первичного терма. Аналогично строим всю диаграмму, реализуюшую заданную булеву функцию: ! Г! ! ! Н12 = (112> У12)> 712 = (х)> х1> х1> х2> хт> хз> хз> Х1> ха, хв> ! Ху> Ха, Хв, Х9, Хэ, Х10> Х11), с>12 = 1(х7> хэ)> (х7> х)), (х7> хз), (хв> хв)> (хв, хз)> (хб, хв), (хб, х))> (х), хв), (х1> хв)> (хв, хы), (хв х)1), (Х1> Х11)> (Х9> Х11)> (Х9> Х4)> (Х1> Х11)> (Х1> Х2)> (Х2> ХЗ)> (ХЗ> Х»)> (Х)> Х19)> (ХЗ> Х2)> (ХВ> Х2))> Ее сложность ЦН) равна 17 (было произведено шесть расщепле- ний .
акова близость полученной сложности к абсолютно мини- мальной? Чтобы ответить на этот вопрос, необхолимо породить все эквивалентные решения и сравнить их по сложности получен- ных структурных графов, что равно всевозможным способам упо- рядочения первичных термов в простых импликантах. В данном случае это числе равно 43535 646720, так как количество различ- ных упорядочений слов мографа равно П)г;)!, гле )г;! — число букв в 1'-м слове.
> Тем не менее можно ответить на поставленный вопрос без пе- ребора всех эквивалентных диаграмм Хассе, зная при этом се- мантику (смысл) проводимого преобразования мографа С~(у) в структурный граф Н(У), СГ)У(у) -+ Н(у) (см. теорему 3.47). Рассмотрим, например, синтез структурного графа Н(у), определяемого счетчиком чепюсгн: выкодной лапал принимает аначепне 1, вогла возбуилено четное величество вкодиых пеналов. Рассматриваемую булеву Вунвпию от трек переменных, аадающуго работу счетчива четности, мозно рассматривать вав мо- дель >Р >в (М, Яз), М >о (хц ЛГ/ 1 >в 1, 2, 3), >а.
Г*. > 1. 1! .. * >. 1* . > . * 1. >*,,*,а) > Я 1 2 з Ф и задавать ее в виде (рис. 4.33, а). «>Е Х>е К1 т) «1 1) «>а 2) 3) хц «ц «>а х, К, .22 К> хз б) кз 4) кц к)е ХЕ К1 кю .«з Х, Хт к) хз к,' х; Х7 «з б) 7) «1, гц Гз .ГЗ Кз «7 «7 а) 9) кц хе «7 к" 1 12) Рис. 4.34 316 Гл. 4. Теория формальных грамматик и аатоматоа Согласно теореме ЗА7 выделяем вапрешенные фигуры реввизуемаго преобравования С (у) -+ Н(1).
Дкя этого рассмотрим сочетания вершин по три из шести. Ив 20 сочетаний четыре удовлетворяют этой теореме. Они имеют вид (хп хз, хз), (х», Уз, хз) (хз, хп Уз) (хз, Уп Уз). Наврнмер, набор (хп хз, хз) обводим, тап кап ему соответствует цикл не. четной длины с пиквической перестановкой весов. Набор (хп хз, У») вычеркиваем, так пав вершины, соответствующие буквам набора, не образуют цикла.
4~ 1 ) 3» 1~ $ 1 21 Рнс. 4.3$ Набор (хп хг, Уз) такие вычерквваем, так как хотя соответствующие вершины и образуют цикл, на его веса не являются весами с циклической перестановкой. Сочетания вершин по пять яз шести не рассматриваем, так как число коньюнкций рассматриваемой функции (ранг функции) меньше пяти и, следовательно, сочетаниям зтага вида ааведамо не будут соответствовать искомые подмаграфы. Множество цивво в нечетной длины с циклической перестановкой весов имеет следующий зид: С, ш ((хп хз), (хз, хз), [хз, хг)), Щ = ((хп Уз), (Уз, Уз), (хз, хг)), »3з = ((Уп хз), (хз, хз), (хз, х»)), Ю» = ((хг, хз), (хз, хз), (хз, х»)).
Падмографов тнаа Б в маграфе См (рис, 4.35, а) не содерннтся. Строим таблицу, кзидаму столбцу которой вванмно однозначно сопоставляем водмограф типа А или Б, строке — букву с идентификаторами слов, в кото- Таблица 4нб Рьге ава входит при абравазангш юмма- графа типа А ипи полито подграфа пкот- 1»у настя 3 подмографа типа Б, и на пере- У сечении ьй строки с у-м столбцом ставим »»» Юз с»з»»» звездочку, если буква с соответствующими х»34 1 1 идентификаторами слов, сопоставленная ха 2,4 1 1 »-й строке, входит в падмодекь, соответствующую у-му подмагрвфу, в проптном случае клетка (», У) таблицы остается У» 1,2 незаполненной.
Построенную таким абрахе 1,3 1 1 зом семантическую таблицу будем назыУз 1,4 1 1 вать решетчатой. Использование тер- мина "решетчатая" будет ясен ю»ие. Решетчатая таблица имеет вид, приведенный в гзбл. 4.1б. В построевиай решетчатой таблице вравзваяим покрытие стокбпав стра. кеми. 34.7. Синтез логических структур а топологических базисах 317 Двя рассматриваемого примера имеем покрытия: первая, чгтертая строки; ,'вторая, пятая стропи; наконец, третья, шестая стропи. Буквы, саответствуюпгие строкам найденного покрытия решетчатой табпиВая, расшеяллютсл, т.
е. в одном вз слов зта буква переименовывается. При ' асшеппении буввы, соответствующей»-й строке, все подмадели вида фг (2, 1), О аторые соответствуют столбцам, на пересечении которых с»-й строкой нахо',дится 1 в решетчатой таблице, понижают свой порядок иа единицу, т. е. преобраз,уютсяя в подмодели нулевого порядка. Данное угверидение справедливо согласно фсновному свойству кваанповиых моделей. В результате расщепления всех букв, соответствующих строкам найденного накрытия решетчатой таблицы ТДНФ функции у преобразуется в решетчатую дизьюиктнвиую нормальную форму (РНДФ) функции у.
Дизъюнктивнан нормальная форма (ДНФ) функции У, длн которой существует такое взаимно однозначное соответствие между первичными термами и вершинами структурного графа, что выполняется взаимно однозначное соответствие между конъюнкция'ми и путями графа, причем вершинам каждого пути сопоставлены первичные термы, образующие соответствующую конъюнкцию, и пизъюнкция конъюнкций соответствует объединению соответствующих путей, называется решетчатой ДНФ (РДНФ) функции у. Слозкностпью РДНФ функции у называетсн число вершин соптветствующего структурного графа. Как будет видно, сложность у-ДНФ в основном определяет сложность искомого функциональЙого графа при структурном синтезе автомата.
У Минимальной РДНФ (МРДНФ) функции у называетсн РДНФ функции У, имеющая минимальную сложность из всех РДНФ, сортветствующих функции у. Для поиска МРДНФ функции у необходимо произвести перевор всех РДНФ для всех ТДНФ функции у и выбрать РДНФ с Йинимальной сложностью. Каждое покрытие решетчатой таблицы соответствуег РДНФ туйиковой ДНФ функции у. В рассматриваемом примере все три покрытия равносильны. йьаждому из них соответствует РДНФ сложности 8.
Для определенности выберем первое покрытие. После расщеплении первичных «ермил хг и У1 получаем РДНФ функции У вида у (х1) хг» хз, хз) = хгхзхз Ч хгхзхз Ч хгхзхз Ч хгхзхз. Эта РДНФ является минимальной, так как функция у имеет одну ТДНФ, для которой полученная РДНФ является мн,Нимальной. Полученному решению соответствует мограф (Р" (рис. 4.35, 6) Не строя структурного графа, можно говорить о его сложно,сти в силу взаимно однозначного соответствнн между первичными ,«ермами реализуемой РДНФ и вершинами синтезируемого графа. Сложность синтезируемого графа равна сложности реализуемой :азДНФ. Это свойство предлагаемого метода решетчатых таблиц поз- 318 Гл. 4. Теорие ббормальпв)х грамматик и ав)помотав валяет существенно снижать трудоемкость при синтезе минимальных булевых графов.
Синтезируемый абсолютно минимальный структурный граф, реализующий булеву функцию 7'(У), хз, хз) счетчика четное~и и соответствующий найденной МРДНФ, имеет вид, изображенный на рис. 4.36. Кз к) Рассмотрим еше один пример синтеза абсолютно минимальных структурных графов. т' Синтезировать абсолютно мнк, т, нимальный структурный граф, реализующий булеву функцию вида Кэ 22 У"(21, Х2, ХЗ, 24))1 —— Рис.
4.33 = Ч(0, 1, 2, 4, 9, 11, 13), и равную 0 на остальных наборах. Выделяем максимальные интервалы и строим импликантную таблицу (таблицу Квайна). Таблица Квайна для рассматриваемой функции имеет вид табл. 4.17. Твблилв 4.17 34 7. Сипи)еэ логических структур в топологипеских баэисак 319 Решетчатая таблица, соответствующая первой ТДНФ, имеет вид, приведенный в табл. 4.18. Решетчатая таблица имеет покры- ' 0.2) кв(1, 2) к((1, 2) кв(1, 2, 5) тз(1 3 5) тк(2, 4, 5) тэ(1, 3.
5) тк(2, 4, Э) т)(3, 4, 5) 24(3, 4) Х)(3, 4) Рис. 4.37 2„(З, 4) тия: вторая и третья строки (первое покрытие); третья и четвертая строки (второе покрытие); первая, шестая и седьмая строки третье покрытие). Этим покрытиям соответствуют РДНФ первой ДНФ функции у вида ! Уа(21, Х2, ХЗ, Х4, ХЗ) = = Х)хзхв Ч Х(УЗХ4 Ч У)хзхв Ч Х) ХЗХ4 Ч У)Х2хз, ! ЫХ1~ 22~ 23~ Хвт ХЗ)— = 212324 Ч 212224 Ч 212324 Ч Х)ХЗХ4 ЧУ)У223~ / / Ф Я21) 22) ХЗ, Х4, Х„24) = = Х)УЗ24 Ч Х)ХЗХ4 Ч 21УЗХ4 Ч У1Х2У4 Ч Х1У2ХЗ. Твблилв 4.13 Т вб лил в 4.19 Единицы, обведенные кружком, в таблице Квайна определяют элементы ядра покрытия (2, 3, 5, 6). Находим тупиковые ДНФ заданной функции, покрывая столбцы таблицы Квайна строками таблицы. Имеем два покрытия: первая, вторая, пятая, шестая строки и вторая, третья, четвертая, пятая, шестая строки.
Этим двум покрытиям соответствуют ТДНФ функции ~ вида ~ (21~ 22~ хз~ 21) = х)хзхв Ч х)хзх) Ч х)хзхв Ч У122У4 Ч У)22УЗ, (21~ Х2, ХЗ, Х4) = Х12ЗХ4 Ч 21ХЗХ,( Ч Х12ЗХ.( Ч У1Х2Х4 Ч ХЗХЗХ4. Первей ТДНФ соответствует мограф (рис. 4.37, а), в котором имеются циклы нечетной длины с циклической перестановкой весов вида Щ = (хз(4, 5), хз(5, 3), х4(3, 4) ), ЯЗ = (х)(1 2), х2(2 5), Уз(5 1)), (,)з = (хв(1, 2), хз(2, 5), хз(5 1) ). Сложности решетчатых ДНФ соответственно равны ЦД) = 7, ЦД) = 7, ЦУ,') = 9. Второй ТДНФ функции у соответствует мограф (см.
рис. 4.37), в котором имеются циклы нечетной длины с циклической перестановкой весов вида х)(1, 2), хз(2, 5), хз(5, 1) У)(З, 4), хз(4, 5), хз(5, 3) Яз —— У4(З, 4), УЗ(4, 5), хз(5, 3) Решетчатая таблица, соответствующая второй ТДНФ, имеет внд 320 Гл.4. Теорил формальных грамматик и агтоматог табл. 4.19.
Покрытиям этой таблицы соответствуют РДНФ второй ТДНФ функции у' вида и ~а (Х1> ХЗ) ХЗ) Х4> ХЗ) = = х1хзха Ч Х1хтха Ч х1хзх4 Ч х1хтх4 Ч хтхзхч, > Ь" (х1, х2, хз, хе, хз) = Х1ХЗХ4 Ч Х1Х2Х4 Ч Х1ХЗХ4 Ч к1Х2Х4 Ч ХЗХЗХ4 вп> » > 1с (Хм ХЗ, ХЗ Х4) Х1> Х41 = х> хзхг Ч хтхгха Ч хтхзха Ч х1х2х4 Ч хгхзх4 Сложности полученных РДНФ для второй ТДНФ соответственно рваны А(1ап) = 7, ЦЯ') = 7, Х(У,") = 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
