Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 76
Текст из файла (страница 76)
Структурный граф Н(Г(х)) представим в виде модели Фь= (Мь~ < Ч) где 1 , если нз р(т;) > р(т ) следует т; > т, О в противном случае. При исследовании вопроса преобразования модели Ф в модель Фь и построения многовыходного структурного графа следует рассматривать модели со следующими ограничениями: 1) если в модели Ф, найдутся два слова, р и )ьр, такие, что р С Фд, то эти слова заменяют одним словом р; 2) если в слове имеются хотя бы две одинаковые буквы, то и пьь (гпа — — ть), то одну нз них заменяют другой; 3) если в модели Ф, найдутся хотя бы два слова,,и и рд, такие, что Иа = ггтг~ И~3 = ггты где р(т„) = р(тг) = 1, а состоит из букв т;, р(гп;) = О, то одно из этих слов заменяют другим. Очевидно, для того, чтобы было можно частично упорядочить буквы модели Ф„необходимо, чтобы мограф См не содержал запрещенных фигур Яд, Яв (см.
рис. 3.52). В этом случае возможно частичное упорядочение букв модели Ял, Яп без учета предиката д в модели Фь. Найдем запрещенные фигуры в мографе Сдг(г (х)), характеризующие фиксирование максимальных (минимальных) элементов в соответствующем структурном графе Н(г'(х)) при преобразовании Сдг(Г(х)) -+ Н(г (х)). для определенности будем фиксировать максимальные элементы, которые соответствуют выходным каналам проектируемой логической схемы.
Условие частичного упорядочения букв модели Ф„в котором учитываются заданные максимальные элементы, устанавливает следующая теорема. Теорема 5.3. Между буквами модели Ф, = (М„р, ог, 52, ..., 5„), маграф См которой нс садержит,мографов Яд, Ян, существует отношение частичной упорядоченности тогда и гполько тогда, когда мограф Сьг не содсржигп модельных подграфав Як (рнс.
5.24). Сложность логических схем в основном определяется сложностью соответствующего структурного графа Н. Следовательно, структурная минимизация булевой функции у' определяется распределением запрещенных фигур Ял, Ян в мографе См(У), а системы булевых функций (Д) — распределением запрещенных и+д ать+о ~ьь югпр т~ньу Рис.
5.24 фигур ЯА, ЯБ, Яе в мографе С (1Я). Таким образом, минимальной логической схеме будут соответствовать те ДНФ булевых функций, в которых необходимо произвести минимальное количество расщеплений первичных термов для того, чтобы абразовавщийся мограф был интерпретируем в категориях структурных графов, Рассмотрим точную структурную минимизацию булевой функции у, которая сводится к покрытию семантической таблицы глуКнгервалы Первичные рабочеа области термы ) Запрещенные фигуры Максимальные интервалы Рис.
5.25 М в. ь гьааь ьь бины 2 (рис. 5.25) н, если необходимо, к раскраске графов, соответствующих покрытиям второй таблицы. Первая таблица формируется на основе покрытия таблицы различий для практических булевых функций. Покрытие первой таблицы порождает тупиковую ДНФ, которой соответствует мограф См. Преобразование его в частично упорядоченный, т. е. в интерпретируемый структурным графом Н, выполняется с помощью покрытия второй таблицы. Рассмотрим пример.
П риме р 5.1. Определим сложность абсолютно минимального струвтурного графа (диаграммы), реаливуютего булеву фунппюо У(к~, кт, к., к,) ~,= и(О, 1, 2, 4, Э, Ы, ГЗ) и равного нулю на остальных наборах. 418 Таблица 5.7 (3 4,5) l б Рнс. 5.26 следующего вида: Олз = Уз(4, 5), Уэ(5, 3), хз(3, 4) Ялз = хз(1, 2), Уз(2, 5), Уэ(5, 1) 5)лэ = (Уэ(1, 2), Уз(2, 5), хэ(5, 1)). Гл.б. Прикладная теория алгоритмов Выделим максимальные интервалы и построим для рассматриваемой функции таблицу Квайна (табл. 5.6). Таблица 5,6 Подчеркнутая единяпа в таблице Кзайна соответствует обязательному максимальному интервалу. (Максимальный интервал является обязательным, если найдется единичная точка, принадлежащая этому и только этому интервалу.) Множество обязателышх макснмальныт интервалов образует ядро покрытия.
Находим тупиковые ПНФ заданной фуиквнн, покрывая столбцы Кзайяа странами таблицы. Имеем два покрытия: дерзая, вторая, третья, пятая, шестая строки и вторая, третья, четвертая, пятая, шестая строки. Этим двум покрытиям сответствуют ТКИ функции у вида з У (хы хз, хэ, хэ) = хзпэхзи хзпзхэ ихзпзхз ипзпзхз иУзУзхз, 1 з э з 3 оз ) (хз, хз~ хз~ хз) = хгйэхз )(хзпзхз ипзпэпз ЧУзпзпз )(Узпзхз. Первой ТПНФ соответствует мограф, изображенный на рнс. 5.26, и. В этом графе имеются пнклы нечетной длины с циклической керестановкой весов (1, 3, 5) (1, 3,5) Первой ТПНФ соответствует семантическая таблица — табл.
5.7. 38.3. Характсризация выходной связности структу 419 Одним иа минимальных зюкрытвй является з = (Уз(4, 5), Уз(2, 5)). По. скольку преобразования, вхоляшне в него, рзсшекляют лексикографически одинаковые буквы, строим граф на словах (2, 4, 5) (рис. 5.26,6). Этот граф раскрашивается в два цвета: (2, 4) и (5). Следовательно, достигзгуто минимальное расшелление букв. После штриховки буквы Уз в пятом слове получаем ПНФ, янтерпрсгируемую в категорият диаграммы Хассе со сложностью 7 (рис.
5.26, е): у (хы хз, хз, хз, хз) = хзпзхз Ч хгпзхз Ч хзхэхз Чпзпзхз ЧУгхзпэ. Рассматривая аналогично остальные покрытия и раскределеняе запрешенных фигур в могрвфе второй тувивовой ПНФ, получаем, что найденная укоряЛочнзаемая ПНФ является абсолютно минимальной. Следовательно, сложность диаграммы, реалиауюшей эту функцию, также равна 7 (рис.
5.26,а). Приведем точное решение задачи структурной минимизации системы булевых функций, основанное на использовании запрещенных фигур преобразования мографа в диаграмму с фиксированными максимальными элементами. Оно заключается в выполнении следующих этапов. 1. С помощью одного из известных методов формируют множество многовыходных простых импликант (МПИ) (многовыходных максимальных интервалов).
Множество точек пространства, входящих в единичные области булевых функций у), ут, ..., У» н образующих гиперкуб, называется многавыходным ()с-выходным) интервалам функций у), уз, ..., Ь». Многовыходной интервал булевых функций у), уз,..., у» назы- 3)ается мнагавыхадным максимальным интервалом, если не найдется многовыходного интервала этих функций, включающего его. Йонъюнкция, соответствующая многовыходному интервалу булеВых функций у), ут, ..., ~», называется мнагавыхаднаб простой импяиканта(1.
2. Строят импликантную таблицу Пвайна, в которой каждой строке соответствуют МПИ, столбцу — конституенты единицы (или импликанты) исходных булевых функций у((Х) Е Г(Х). При этом конституента единицы (импликанта) столько раз входит в таблицу, сколько функций принимают на ней значение единица. 3. Находят покрытия столбцов строками импликантной таблиПы. Таким образом определяются ТДНФ системы булевых функций. 4. Для каждой ТДНФ системы булевых функций, которой соответствует модель ф„строят решетчатую ДНФ (РДНФ) системы булевых функций минимальной сложности, т. е. осуществляют Преобразование ф, -ь ч)ь. Гл.б. Прикладнал тяеорил алеориятмов 420 б . Из всех РДНФ системы булевых функций выбирают РДНФ минимальной сложности. Далее строят многовыходной структурный граф Н.
Для того чтобы удалить все запрещенные фигуры, построим семантическую таблицу В, каждой строке которой взаимно однозначно соответствует буква (в скобках указываются идентификаторы двух слов, в которые эта буква входит при образовании запрещенной фигуры), а столбцу — одна из запрещенных фигур ЮА~ Юнт ЯБт г; = 1, если буква, соответствующая з-й строке, входит в 2'-ю запрещенную фигуру, О в противном случае. Строкам соответствуют буквы модели тп» С М„для которых р(тпг) = О. Тогда покрытие столбцов строками в матрице В соответствует множеству букв, которые необходимо расщепить при преобразовании тр, -4 тра.
Проиллюстрируем точный метод минимизации системы булевых функций с учетом их теоретико-структурных свойств. Пример 5.2. Пусть валена сястема булевых функцкй г(Х) = (Ут(Х), уг(Х) 1з(Х) у»(Х)), завтюятцая от пяти переменных (табл. 5.8). Выделим все МПИ, затем строим таблицу Квайиа н в результате получаем две ТПНФ Таблица 5.8 Рис.
5.27 0 0 1 1 1 1 1 1 1 0 '0 0 0 0 1 1 1 1 0 0 0 О 1 1 1 1 1 0 1 0 1 О 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 '0 1 0 1 55.3. Характце иэацил выходной свлэностяи стяруктяур 421 данией системы: гс(Х) = х»хьус ч хгхьус ч хьх»тг ч хьхьуз чхсхгУ» ч хсхгт» ч хгхзт», гз(Х) = х»хаус Ч хзхьут Ч хзх»уз ч хзхьуз Ч хтхгт» Ч хсдзу» Ч хтхзтз». Рассмотрим первую нз ТЛНФ, представляя ее в аиде модели ф 1 1, Мою(Х1, Хт, Хг, ХЗ, Хь, Х», ХЬ, УЫ ттг тть, тт»), р(хс) = р(хт) =р(хз) = р(нз) = р(хз) = р(х») = р(хь) = О, р(тт) = р(тг) ю р(ть)б р(У») = 1. Слова модели ф', соответствуют конъюнкциям функции гс(Х). Построим моделъный граф ст (рнс.
5.2Т,а). Перечислим вапрепюнные фигуры, содеризюиеся в ст буль ю (хь(1, 4),х»(1, 3), хз(3, 4)), »аль = (хь(2, 4),хз(4, Т), хз(2, 7)), »вез Э (хь(1, 4),х»(1, 3)), »2л» Э (хь(1, 4), хз(3, 4)), Яль 3 (хз(2, 4), хз(3, 4)), 1)пь Э (хз(1, 4), хз(4, Т)), 4)лт Э (хь(2, 4), хз(4, 7)), Ялз Э (хь(2, 4), хз(2, 5)), Япь 3 (хь(2, 4), хг(2, 7) ), »2пте ~ (х»(1, 3), хз(3, 4)), Яхы Э (х»(1, 3), хз(3, 7)), Цлтг Э (хз(2, 7), хз(3, 7)), »Охсз ..т (хз(2, 7), хз(4, Т)). Покрытиями сементиче свой таблицы (табл. 5.9) являлися иноке ства строк» (1, 2, 3, В), (1, 2,3, 5, В), (1, 2, 4,5, б), (1,2,4, 5, В), (3, 4, б, Т, В), Построим для лексявографнческн одинаковых букв графы нв миоиестве апов, в которые юсодят зги буквы. Расврасва юс определяет необходимое расширекие (»5М,) носителя М, в каидом конкретном случае.
422 Таблива 5.10 Таблида 5.8 18, 4, 7> Рнс, 5.28 Гл. б, Прокладках теорив алгоритмов Мощность расшнренив носители (ь5М ( для намного нв воврыгнй соответственно равна 3, 3, 3, 3, 3, 4. Следовательно, мвннмавьиан сдонносгь Ь струнгурного графа Н равна 14 (рис. 5 27 б): г, = (Мь(+ )гзМь) = 14. Рассмотрим модель Ф~~~, соогвегствующую второй ТДНФ: Ме = (хг, хг, хг, хг, хз, хь хь ггг ггг, ггз, Я~ р(хг) р(хг) — р(хг) — р(хг) р(хз) р(хь) р(хь) зе О~ р(Уг) =р(Уг) =р(уз) =р(уь) = 1.
Мограф С~ (рис. 5 28, а), овредедюощнй зту модель, содериит ввврещенные фигуры следующего вида; ьь)лг = (хь(1г 4), хь(1, 3), хз(3, 4)), 'ьщ Э (хь(1, 4)~ хг(1~ 3), хз(3, 4)), с)вз Э (хь(1 4), хз(3 4)) 4ьгвь Э (хь(2, 4), хз(3, 4)), аль ~ (хь(1 4) хз(4, 7)), ьувз Э (хь(1, 3) хз(3, 7)), ь4вз Э (хь(2, 4), хг(2, 5)), Подрывая семангнчесвую габвиву (табл. 5.10), залучаем, что минимальное расширение носители (гьМ( разно 2. Оно н вороидаег минимальный сгрунгур- 8 3.4. Теорегнико-структурном микимивацил булевых функций 423 иый граф (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
