Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 58
Текст из файла (страница 58)
Отсюла, сравнивая сложность полученных РДНФ для двух ТДНФ, получаем МРДНФ функции у, например л (х1) х2) хз) х4) х2) = х1хзхе Ч х1хгхе Ч х1хзхе Ч Х1хтха Ч х1хтхз со сложностью 7. Соответствующий ей абсолютно минимальный структурный граф изображен на рис. 4.38. Перебор при определении минимальной сложности структурного графа оценивается числом РДНФ, соответствующих заданной булевой функции 7(х1, х2, ..., х„). Трудоемкость этого перебора равна трудоемкости обхода дерева поиска МРДНФ функции у'(х1, х2, ..., х„) (рис.
4.39). К сожалению, пока нет оценок числа РДНФ, соответствующих функции у(х1, хг, ..., х„), поэтому этот перебор оценим числом ТДНФ, соответствующих функции ~(Х1, х2, ..., х„). Известно, что число 1Чтдн р ТДНФ, х, соответствующих булевой функции от и переменных, "наихудшей" в смысле ее Рис. 4.38 сложности в классе ДНФ, асимптотически соизмеримо с числом всех различных функций от этого числа переменных: 1нп 7ЧтднФ (22 ) = 1. Следовательно, получаемый перебор становится практически неприемлемым даже с использованием современных ЦВМ для произвольных булевых функций, зависящих более чем от 20 переменных. Распределение подмоделей, гомеоморфных квазилолным полмоделям, в модели ф, задающей булеву функцию у(х1, х2, ..., х„), определяет согласно критерию решетчатости минимальность структурных графов.
Будем говорить, что это распределение опргдглхет теоретико-структурные сгайстеа модели ф. $4.7. Сииптсз логических стпрукп>ур г п>аналогических базисах 321 На практике при синтезе автоматов управления реализуемый автоматный оператор характеризуется большим числом переменНых и сравнительно небольшим числом обобщенных состояний 'увтомата, определяемых значениями вектора ХЕ+В'-У.
Например, автомат управления может иметь 100 элементов из М и М, и ршеннаа ДНФ Секра шенин а ДН Ф покрытие инплнкантней таблицы пикоаые ДНФ решетчатой с~- Ь Решетчатые ДНФ Рис) 4.39 'только лишь на 500 наборах определен. Но 500 намного меньше, чем число всевозможных двоичных наборов длины 100, равное 21оо: 500 4. 21оо.
Используя это положение, можно снизить трудоемкость синтеза автоматов управления путем разбиения большого числа переменных автоматного оператора на группы с последующей заменой переменных каждой группы на одну "новую" переменную. Предложим метод такого объединения переменных. Введем несколько понятий. Множество букв, взвешивающих только вершины двухинциндентного подграфа структурного графа, называется обоби4гннай букаай первого рода.
При структурном синтезе двухинцендентный подграф булем называть к-структурой (к-диаграммой). о-стпруктпурай (ст-диагральной) называется подграф структурного графа, произвольная пара вершин о; и и которого коинцилентна только соответственно входящим дугам и+, и+, ..., и+ и и > и,+, ..., и+, имеющим соответственно одно и то же начало, и которая коинцидентна только исходящим дугам и... и,, ..., и,, и и, и,..., и, имеющим соответственно один и тот же конец 11' ут> ''' Уьл (рис. 4.40).
Множество вершин (и;), каждая из которых покрывается одними и теми же вершинами (Го1), при этом ни одна из вершин 11 а. К Гвтба>вв 322 Гл.4. Теория формальнмх грамматик и аетоматоа о, о б (ГиД, не покрывает вершины ид, ид К 101/, и это множество вершин (о;) покрывает одни н те же вершины 1Г 10Д, при этом нн одна нз вершин и, и к 1Г Ьтч), не покрывается вершиной оь, иб р (о;), называется о'-поддиагральной. Множество букв аь, ат, ..., а„, г ' '" ' ) каждая нз которых взаимноодно- значно соответствует вершине а-диану граммы, называется обобщенной буквой второго рода. гь На рнс.4.40 обобшенная буква вте- к/ рого рода взвешивает срелннй ярус.
к/, Т е о р е м а 4.2. Мно же с гав о букв ку к) кь а1, ат,..., а„образует обобщенную букву первого рода тогда и только ))з, тогда, когда собственные частоты зтих букв ровны между собой и равны взаимным частотам: Л=А=Л/, ь,у= мат,",а Рнс. 4.40 (4.10) Теорема 4.3.
Множество буке а1, ат,..., а„образует обобщенную букву второго рода тогда и только тогда, когда /'=//, /1/=О, Л =//, тфу, ь,/зсаг,аэ,...,а„, щ б М '1 1а1, аэ, ..., а„). (4.11) В выражениях (4.10) и (4.11) /О // — собственные частоты, /1/ (ь 75 у') — взаимная частота, определяемая частотной матрицей отношений Г = [Д/], Р=а ха, Я вЂ” матрица ннцидентностн, определяющая соответствующий мограф. В матрице Я = [йь/] каждой букве взаимно однозначно сопоставлен столбец, слову — строка н 1, если у-я буква содержится в ь-м слове, т'/ 0 в противном случае. =(' Метод выделения обобщенных букв заключается в следуюшнх преобразованиях.
1. С помошью частотной матрицы отношений, соответствуюшей мографу, согласно (4.10) выделяем обобщенные буквы первого рода. 2. Согласно (4.11) выделяем обобшенные буквы второго рода. 3. Если были выделены обобщенные буквы второго рода, то переходим к и. 1, в противном случае — к п. 4. 4. Конец. 54.7. Синтез логических структур е щояолоеических базисах 323 Пронллюстрируем предлагаемый метод уменьшения числа переменных на следующем примере. Пусть задана булеза функция /, катарая задается мзтрнцей ннцндентностн вида а Ь с Ы з / У Ь ю О 1 О 0 1 0 0 О 0 1 0 0 О 1 О о, о оо о о о 1 1 0 о о 1 0 1 1 0 1 0 0 1 о соответствующая функции /, имеет слелуюз / У Ь зз Частатная матрица етнащеннй, щнй внд: а Ь с 6 6 2 2 1 1 6 6 2 2 1 1 2 2 6 3 2 2 2 2 3 6 2 2 1 1 2 2 5 0 1 1 2 2 0 5 2 2 4 4 5 5 2 2 3 0 2 2 2 2 0 3 2 2 2 2 2 2 2 2 4 3 0 О 3 5 2 2 5 2 2 10 4 4 4 6 3 4 3 6 Согласно (4.10) буквы а н Ь являются сбабщеннымн буквами первого репа.
Заменим нх буквой Ь'. Согласно (4.11) буквы с н т являются сбебщеннымн буквами втераго реда; буквы а' н Ь, е н / газне являются ебебщеннымн буквамн втарога рода.,звме. няем их соответственна на т, д, / . Ф Ф После замены букв матрица ницидентностн имеет внд ь'/'у ь' Частотная матрица стнещений Г' (Г' = (Я') х Ьг') имеет слелующнй внд: Ь' /' у Ь' ю' 2 1 1 1 1 1 2 2 1 1 1 2 2 1 1 1 1 1 2 2 1 1 1 2 2 ь' У Ь' га' Согласно (4.10) буквы д' = (/', д) н та = (Ь', щ') являются сбсбщеннымн буквами первого рада. Обсбщенны.г букв втерего рада нет, следовательно, выделение сбебщенных букв акенчене.
Окончательна имеем матрицу ннцндентнасзн, о о о о 111 1 1 1 0 0 1 о о о о о о о 1 1 0 О О 0 о о 0 0 1 о о о 1 0 0 1 1 1 О 1 О о о о 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 о 1 0 0 1 1 0 о а ь с Ы з ' / У Ь ю 324 Гл.4. Теория формальных грамматпик и авлтаматов 24.7. Сикшсз логических стлруктпур в тпопалогических базисах 325 ввдвюшую в виде булеву функшао в виде 0 1 1 Тввее снетне ннфармецнн вевваляет суШественне уменьшить трудоемкость лрн сннтеве минимальных автоматов уврввлення. После снетка лрн врнведеннн функцвн к ред. шетчвтому виду неебхеднме учитывать ревультаты снвтня крн покрытии решетчатых таблиц.
Для рвссметрнввемога лрнмерв ввметнм, чта маграф, ввдвюшнй снетую функцию, дредстввляег Ь е у собой цнял нечетной длины с цнвлнческай перестановкой весав,н, следовательно, длн лрнвелення втой функции к решетчатому виду монне рвсшекнть лнба Ь', либо д', либо пт". Взвесим кендую букву в слетай теблнке числом букв, которые оне лредстввляет.
Прн минимальном рвсшекленли выберем букву Ь', тек кек ее вгс равен 2. В ревультете синтезе имеем структурный граф С(у) (рнс. 4.41), реелнвуюший функшаа у. Рнс. 4.41 Логическая структура в первом тоно- логическом базисе задается диаграммой Хассе Н, и ее синтез состоит из следующих преобразований. 1. В мографе, задающим реализуемую булеку функцию, выделяем запрещенные фигуры типов А и Б (рпс. 3.53). 2. Находим пары внешне неустойчивых вершин относительно носителя каждой запрещенной фигуры. 3.
Строим семантическую таблицу, сжимаем ее и определяем покрытия. 4. Выбираем минимальное покрытие семантической таблицы, которое порождает мограф (('"', эквивалентный заданному, имеющий минимальное расширение носителя п пнтерцретнруемый а категориях синтезнруемого структурного графа Н. 5. Производим фактическое построение струитурнаго графа по интерпретируемому мографу С~. Синтезированный структурный граф является абсолютно минимальным по числу вершин пз всех эквивалентных графов и построенным без перебора всех эквивалентных графов.
Рассмотрим каждое нз этих цреобразованнй, иллюстрируя пх цроектнроввнием логичесиой схемы, реализующей ДНФ булевой функции (см. рис. 3.54, а) У(х), хт, ..., хб) = = х)хзхб Ч х)хе Ч хтхз Ч х)хзхб Ч хзхехб Ч хтх4хб. 1 2 3 4 б 6 Эту фиксацию будем производить, например, следующим алго- ритмом.
Рассматриваем по очереди строки (начнная с первой) и отмечаем ближайшую от диагонали единицу. Если число отмечен- ных единиц равно н — 1 (и — число вершин мографа), то остов най- хт(3, б) ден. В противном случае, начиная х5(5, б) с последнего столбца, отмечаем в х,(2 б) х,«5 4 3) этом столбце ближайшую единппу, переходим к столбцу на один номер меньше да тех пор, пока не будет отмечено и — 1 единиц. От- . 2) Гт (1 меченные элементы матрицы задают остов. В результате работы этого алгоритма получаем остов мографа, изображенный на рис.
4.42. Отмеченные около диагональные элементы набраны по- лужирным шрифтом н матрице смежности. Неотмеченные элементы соответствуют хордам мографа отно- сительно выделенного остова. Число хорд равно цикломотпичс- скому числу мографа тт(((ЬУ) = Нр() ~ — )М~+ К, где )М! — мощность носителя мографа, ~(р() ~ — количество ребер мографе, К вЂ” число компонент связности мографа. В нашем примере тт(Сьт) = 8 — 6+ 1 = 3. 2. Формируем базисную матрицу циклов (базискую циклома- п)ическую мотприцу) присоединением хорды к выделенному осто- ву. В результате получаем базисную цикломатичесиую матрицу относительно остова В (рис. 4.42). 4) х (1 Рнс.
4.42 Выделение запрещенных фигур типов А и Б сводится к выделению циклов нечетной длины в мографе с последующей проверкой распределения идентификаторов на пх вершинах. Выделение циклов нечетной длины будем производить фиксацией остова мографа, добавлением хорд с формированием базисных циклов п генерацией остальных циклов применением операции сложения циклов па модулю 2. Для такого выделения предложим следующий алгоритм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
