Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 62
Текст из файла (страница 62)
Например, результат операции разложения структурного графа Н (см. рис. 4.46, 6) по направлениям (хз1 и (хз, хз) представлен на рис. 4.52. Повторные буквы отмечаем штрихами с целью идентификации вершин графа. Хч Рис. 4.52 Если вершины К, определяющие направления, такие, что для всех о, Е (о / у' = 1, ..., Ц выполняется о, > оь, иь б Ъ;, то полученный подграф Н; будем называть синдромом Я(ус») вершин К. Если же для всех вершин о, б (и / у = 1, ..., Ц выполняется о, < иь, оь б Ъ;, то подграф Н» будем называть ан»писиндромом У(У;) вершин К. Операция инверсии )( графов.
Структурный граф, представленный в виде суперпозиции структур типов и и а, называется графом типа ка (»го-графом). Операция инверсии»( (Н) структурного графа Н вЂ” это приведение данного графа с помощью его разложения к графу типа ка, замена каждого подграфа типа а подграфом типа к и каждого подграфа типа к подграфом типа а; при этом каждый вес х,.' первоначального графа заменяется весом х(сч+») ов 2 на соответствующих вершинах полученного графа. Утверждение.
Запрещенными фигурами свойства структурных графов быть ка-графами являются графы, гомгоморфные графам Ян и Я,у (рис. 4.53, а), т. е. графы, представленные на рис. 4.53, б. 54.8. Синтез логических структур в несвязных базисах 345 Следовательно, минимальное расщепление структурного графа Нри приведении его графу типа ка определяется минимальным покрытием семантической таблицы, в которой столбцам взаимно однозначно соответствуют запрещенные фигуры, строкам — пути между вершинами и;„и о(в+(о) = 2) и между о(в (о) = 2) и и „, где о(в+(и) = 2) — вершина с положительной полустепенью, т, е.
с числом исходящих дуг, равным 2; о(в (о) = 2) — вершина с йтрицательной полустепенью, Таблица 4.20 т. е. с числом входящих дуг, равным 2; окпз и ошах минимальный и максимальный элементы соответствующих путей. При устранении запрешенНой фигуры рассматриваемого свойства один из этих путей расщепляется. В нашем случае семантическая таблица согласно рис. 4.49, би рис. 4.49, в имеет вид табл. 4.20. Имеем шесть покрьпий атой таблицы: (а ЧЬ)(сч»»)(е Ч у)(сЧ у) = все ч Ьесч бс~Чао1 чЫу Чаус.
Для определенности выбираем покрытие (Ь, с, у). Тогла рассматриваемый структурный граф Н представим детмпозицией подграфов к, с: Н = с(з(хз, с(з'(хп хз), к(ды а(хз, уз)))), 1г(хз,х,,хз),к(а(хз,хз), х(, Нз)). В атом случае инверсия графа Х (Н) = Н (рис. 4.54) представляет собой Х Рис.
4.55 346 Гл.4. Теория формальных грамматик и автоматов выраиеиие вила Н = к(е(хз, >г(а(ни хз),а(хг, л(хз,хз)))), гг(вз,хз> хз), гг(>г(хз,хз), х>, хз)). При синтезе логических схем в функциональном базисе В необходимо определять резулыаты коопераций вида Х~ь> (6; Е В), т. е.
хуь (Н) = (Н1, Нэ, ..., Нь.„1, (4.21) где йв„— входной коэффициент элемента 6;. Результат кооперации Хгь можно получить, применяя соответственно ряд коопераций вида Х'г и Х в порядке, обратном порядку следования операций Ч и в разложении операции уьг на Ч и Например, резулыаты кооперации Шеффера Х'(Н) определяем с помощью коалгебры графов следующим образом.
Пусть необходимо найти резулыат (Н1, Н21 кооперации х'(Н), т. е. х (Н) = (Н1 Н2). (4.22) Графы Н1, Нэ являются результатом Хг(Н), если и только если соответствующие им функции у1(Н1) и ЯН2) связаны (согласно определению кооперации) соотношением У(Н) = У1 ~Н,УЬ(Н2). но, с другой стороны, У(н) = Л(н1) ч уэ(нэ). Отсюда согласно определению кооперации и приведенным выше уравнениям лолу- чаем х (н) (н1> н21~ х (н1) н1 х (н2) нэ т.
е. в случае базиса Шеффера уравнение (4.22) можно свести к Нэ = Х (Нэ Е Х"(Н)). В дальнейшем будем обозначать у-ю компоненту результата кооперации Хгь> (Н) = (Н1, Н2, ..., Н, ..., Нь,„) как Хуь> (Н) ~з, т. е. Н, =,~к(Н)(у В рассматриваемом случае уравнение (4.22) сведено к системе Н1 = Х (Х (Н)>1) Н вЂ” Х- (Х>г (Н) ~ ) . При сведении задачи определения результата (Н1, Нэ, ... ..., Нь„) кооперации Х~ь>(Н) к задаче определения результатов коопераций Х" и Х в сущности сводят структурное уравнение (4.21), разрешенное относительно (Н1, Нт..., Нь,„), к системе, 54.8.
Синигеэ логических структур в несвлэных баэисах 347 состоящей из )св„структурных уравнений, причем каждое у-е (у = 1,..., )с,„) структурное уравнение системы разрешено относительно Н,: Н = х "(х " ° (х '"'(Н)). ° ) Н, = Х-*> (Х«з*...(Х.з-з (Н))...)', (4.23) Н, =Х >г(х"з" (Х '"'(Н)).") Нь,. = Х " "'(Х " **" (Х " *"" (Н)). "), гДе Ха'> Е (Х")„, Х 1; з = 1,..., >свк, У' = 1, ..., и,; ЯУ вЂ” целое число, определяемое базисным элементом 6 для любого у. Система (4.23) представляет собой гс „независимых друг от друга структурных уравнений. Не для каждого базисного элемента 6; Е В можно свести решение структурного уравнения (4.21) к решению системы уравнений вида (4.23).
Для определения вида базисного элемента, для которого решение (4.21) сводится к решению (4.23), разобъем все множество функциональных базисов на два класса: несвязных и связных базисов. Предварительно сопоставим каждому базисному элементу 6; Е Е В граф Нь,.> построенный следующим образом. Выразим булеву функцию ~ь,, реализуемую элементом 6;, через связки Ч и Полученное выражение, в котором имеются только операции дизьюнкции и отрицания, представим в виде графа Нь,, согласно геометрической интерпретации (-местной операции дизъюнкции и операции отрицани>я (рис. 4.55). Х~Н> (Н> Нз -"Н>) Х>Н> и а1Ь,ге1,>1)~д и аьсл Н, и, и, Рис.
4.55 Рис. 4.55 Базис В = (6;/ з = 1, ..., и) называется несвязным, если ни один из графов ЙЬ., которые соответствуют функциям уь,, реализуемым элементами базиса, не содержит цикла. Несвязными являются, например, базисы Вебба, Шеффера, импликативные, коимпликативные. Базис В = (6;/ з = 1,..., пу называется связным, если хотя бы один граф Нь, (з Е (1, 2, ..., и)), который соответствует функции 348 Гл.4.
Теория формольнык ероммотик и автоматов (4.24) Д, (г Е (1, 2, ..., гь)), реализуемой одним из элементов базиса. содержит цикл. Например, решение уравнения Хгг(Н) = (Н„Нь, Н„Нв), соответствующего основному элементу УСЭППА (рис. 4.56), сводится к решению системы вида Н.=Х (Х'(Х (Х'(Н)~,))~,), Нь = Х'(Х (Х"(Х (Х"(Н)1,))!,))1, Нв = Х (Х (Х (Х (Х (Х (Н) 1т)) 1г)) !т) г Нв = Х (Х"(Х (Х"(Н)1,))!,) Х (Х'(Х (Х"(Н)$,))$т) = Х (Х"(Х (Х"(Н)$,))$,). Здесь А — знак операции, реализуемой основным элементом УСЭППА (универсальная система элементов промышленной пневмо-автоматики).
Число связанных уравнений в системе вида (4.24) равно цикломатическому числу графа Нь, Здесь возникает задача минимизации связности системы структурных уравнений, которая сводится к эквивалентным преобразованиям соответствующих булевых выражений. Действительно, ДНФ, соответствующая булевой функции УСЗППА, имеет вид г5(а, Ь, с, З) = аЬЧ асЧ ЬсИ, а после применения закона де Моргана— о Ь с в' вид Ркс 4дт г5(а, Ь, с, Ы) = а Ч 6 Ч а Ч с Ч 6 Ч с Ч Й. Полученное выражение определяет граф Нь,, представленный на рис. 4.57. Цикломатическое число и(НЬ,) этого графа равно 3: и(Ньг) = ~Ц вЂ” ~Ъ'~+1 = 10 — 8+1 = 3, и система структурных уравнений имеет вид Н.
=Х (Х"(Х (Х"(Н)1,))1,), Нь=Х (Х"(Х (Х"(Н)!,))1,), Н =Х"(Х (Х"(Н)1,))~„ Нв=Х (Х"(Х (Х"(Н)!з))1з), (4.25) Х (Х"(Х (Х"(Н)3,))1,) =Х (Х"(Х (Х'(Н)3,))1,), Х (Х'(Х (Х"(Н)1;))1,) = Х'(Х (Х"(Н)1,))1„ Х"(Х (Х"(Н)1,))!т =Х (Х'(Х (Х'(Н)~з))!т). 14.8. Сингиев леваческие струкгнур в несвяэнык бовисок 349 Используя законы булеза анализа, систему (4.25) упрощаем до системы (4.24). Минимизация цикломатического числа графа Вь,. осуществляется с помощью функциональной декомпозиции путем раиска эквивалентных булевых выражений. В общем случае определение результатов кооперации в связных базисах сводится к решению системы связных структурных уравнений вида Н вЂ” гс гг(гс " (гс ои(Н)) ) Н гсогг (геогг (гсогнг (Н)) ) Н = гс гг (ге"гг...
(х г"г (Н))...), Нь,„= гс " *'(гс "'*' ... (к "*""* (Н)) ), (4.26) Ры(мдм (гсвг .г(Н))...) = х "г'(гс'"гг... (хтг"г (Н))...), говгг (гсдгг (гсвг г(Н))...) = гсггг (гсггг .. (гс™г (Н)) ... ), гсвы (гсдгг... (гвгтг г(Н))...) = ге в (ге~ г... (гс гг (Н)) ° ° ) Где млг~ага гг~'вгя гсьггг Е (гс ~г~ ге )~ го = 11 .. ) гсвк~ уа = .
п,у, =1, ..., пг„,у' =1, ...,6,,;здесьп;,пг,я,кг, определяются элементом 6; соответственно для любого г', гя, у„; гд, 1 = 1,..., р (р — число линейно независимых циклов в графе Н(6;), равное его цикломатическому числу и(Н(Ьь)). При синтезе логических схем в функциональных базисах строим по реализуемой функции у структурный граф, который затем с помощью коалгебры графов преобразуем в функциональный. Полученный функциональный граф и является искомой логической схемой. Предположим следующую процедуру преобразования структурного графа в функциональный. Предлагаемый ниже алгоритм рассмотрим на примере синтеза функционального графа, реализующего булеву функцию от трех переменных счетчика четности в базисе В = (-+, 01.
Алгоритм состоит из следующих шагов. 1. Структурный граф 6 Е В, реализующий булеву функцию у, сопоставляется максимальному элементу графа Нь, соответствующего базисному элементу 6 Е В. 2. Согласно графу Нь, определяющему функционально-структурные свойства элемента 6 Е В, выполняются соответствующие операции разложения и инверсии над графом Ну. 3. В результате выполнения операций и. 2 определяются структурные графы НА, соответствующие минимальным элементам графа Нь. Заметим, что максимальный элемент графа Нь соответствует выходу базисного элемента 6, минимальные — входам этого элемента.
350 Гл. 4. Творил формальных грамматик и автоматов Х, ! ! ! ! ! О(Х3 Х(О(«г, Хг) О(Х! « х, Выполнение первых трех шагов для рассматриваемого примера иллюстрируется на рис. 4.58. Для каждого из найденных графов Ну,. пп. 1-3 выполняют до тех пор, пока не получат структурные графы, реализующие булевы функции, которые допустимы на « з Хз входах логической схемы. Обычно такими функциями являются переменные х; или переменные и нх отрицания. Если на 3-м шаге преобразо- вания структурного графа в функХг циональный было получено гЧ графов, реализующих одну и ту же функцию с точностью до конъюнк- «3 ций тождественно равных нулю \ з то эти графы объединяются в Х, «, (13(/к,ьт) групп (( ) — знак бли! жайшего целого числа; й, „— вы- ходной коэффициент (козффициг ент разветвления) базисного элемента).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
