Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 60
Текст из файла (страница 60)
Уровнем типа В называется подмножество Хя> множества Х такое, что для него справедлизо первое условие предыдущего определения и не справедливо зторое условие. При взвешивании яруса в структурном графе буквами подмножества Х~> так, чтобы ни одна буква х; (х; Е Х~>) не повторялась дважды к структурном графе, получаем граф, не эквивалентный искомому с числом путей, превосходящим В. Для удаления лишних путей в полученном графе необходимо расщепить некоторые буквы подмножестза Х>. После расщепления расширенное подмножество Хя> преобразуется в подмножество, образующее уровень типа А.
Операцию приведения уровня типа В к уровню типа А назозем операцией раси4епления первого типа. Подграф С>(и,) = (7', 17'>) графа С = (1т, 17') назызается подграфом с начальной вершиной о„если для каждой его вершины о; Е 1т' имеется хотя бы один путь [о„..., и;). ВеРшина и назызаетсЯ покРыватои4гй веРшинУ ип если з гРафе С = (>т, 17) имеется дуга вила (и;> оу) Е 1>. Расщепление первого типа производим в следующем случае. Пусть построено 1 ярусов структурного графа С, причем першины 1-го яруса взвешены множеством первичных термоа Хп и пусть в этом ярусе содержатся две вершины, а; и и, с весами саотзетстэенно х; и х (х;, х Е Хт) такие, что при построении (1+ 1)-го яруса множества весов Х(>7+7, и Х>т+7, вершин, покрывающих соответственна и;(х;) и и (х ), являются пересекающимися: Х,'„„Г Х,',+ц.
~ а. Тогда, если подграф с начальной вершиной и, взвешенной пераичным термам х (х Е Х'+ 1 >'> Х1,+ ) и покрывающей 332 Гл. 4. Теория формальных грамматоик и аетиоматоое от(х;), и подграф с начальной вершиной од, взвешенной тем же первичным термам х„и покрывающей вершину о (х ), реализуют различные булевы функции, то вес х расщепляется.
Уроенем жива С называется подмножество Х' множества букв Х такое, что: 1) ~~т, у,>В, ~, У>,фО' (415) х) чХс х, Кхз хьхзеХс 2) подмножество Х~ является покрытием матрицы инцидент- ности, задающей функцию у(Х). Например, пусть задана булеза функция 1(х1) х2) х3) = х1хтх3 )т хтх3 >>х1х2х3, мограф которой имеет следующий вид: аМУ) =(У, Я2, Яз), У = (х1) х1, х2> хз, хз)) 52 = ((х1) хз)У оз = ((Х1> Х2) Хзз) (Х1) Х2) Хз) )' Определим подмножества букв, которые могут претендовать на взвешивание вершин первого яруса искомого структурного графа. Очевидно, что претендентом на веса первого яруса могут быть уровни типа А или С, Подмножество букв, претендующее взвесить первый ярус, дол- жно покрывать своими элементами все строки матрицы инцидент- ности П) хз хз тз 1 О 1 О 1 1 1 О О 1 О 2' О 1 1 1 О 3 Согласно матрице инциндентности имеем следующие покрытия этой матрицы: (х1> х1) > (х1) х21) (х1> хз)> (х2) хз)> (хз) тз).
Первое и последние подмножества являются уровнями типа А, остальные — типа С. Ояерациеб раси4еяления еозорого типа будем называть при- ведения уровня типа С к уровню типа А или В. При расщеплении второго типа из подмножества Хс удаляются расщепленные элементы, образующие подмножество Хд такое, чта ',; ~.,= ~: Ь)-Л, *;фхз х>одет 14.). Сини)ез логических со>рукозур е тоонологических 6азисах 333 При расщеплении второго типа порождаются новые подмножества уровней типов А, В и С.
Результат операции расщепления первого типа есть повторение некоторых букв внутри одного яруса, а результат операции расщепления второго типа есть повторение некоторых букв между ярусами. Используя введенные понятия, можно предложить следующий метод синтеза структурных графов. Для снижения трудоемкости при синтезе оптимальных структурных графов в предлагаемом методе используется понятие яроизеодноб отл модели. Подграф с начальной вершиной о;, являюшийся концом дуги (о;, о;), бУдем называть подгРафом, ЯокРыеатои4ии веРизинУ оз (рис. 4.45, а) хз Рис. 4.43 Объединение подграфа с начальными вершинами о;„о;„...
..., от, являющимися концами дуг, начала которых есть вершины о;„о „..., о;„, образующие подъярус, будем называть подграфом, яокрыватои4им яодъярус (оз„о;„..., а „) (рис. 4.45,5). Матрица ннциндентнасти Ч = (о; ] модели Ф, по которой производится оценка в предлагаемом методе, строится следующим образом. Каждой строке взаимно однозначно сопоставляется первичный терм булевой функции, столбцу — выделенный подуровень и )у)з = 1 1, если веса вершин подграфа, покрывающего подъярус, взвешенный у-м подуровнем, содержат з-й первичный терм, О в противном случае.
334 Гл.4. Теорие формальны«грвммар>ик и ввтвмвтов Уровни, взвешивающие начальные вершины подграфов, покрывающих вершины построенного яруса, будем оценивать с помощью функции являющейся обратно пропорциональной производной дф/д5 от модели ф и характеризующей степень пересечения этих уровней. В качестве уровня, взвешивающего синтезируемый ярус, будем выбирать уровень с максимальной оценкой. Заметим, чта понятия уровень и ярус совпадают, если булева функция является решетчатой. В этом случае уровень является идентификатором яруса. Перед изложением метода синтеза рассмотрим случай неодинаковой длины путей синтезируемого графа. В этом случае имеем четвертый тип уровня — уровень типа В.
Подмножество Х~~ множества Х называется уровнем шина В, если выполняются следующие условия: 1) ~~~ /т <Н, ~ /,, =б; (417) «сдХр «>,«>чХр «> Ф»> 2) не существует такого элемента х е Х, включение которого в подмножество Х> приводит подмножество Х> к уровню хина А. Проиллюстрируем введенное понятие на следующем примере. Пусть дан граф (рис. 4.45, в), реализующий булеву функцию /(зт> эт> ..., Ха) = Х1кэзв Ч зтквгв Ч зьзвза Ч зэка Ч Ч хтхгхв Ч хэтгх«. Уровнем типа В является подмножество первичных термов (хз, зв,ха).
Предлагаемый алгоритм осуществляет синтез структурного графа по ярусам, т. е. на каждом шаге синтеза находятся первичные термы Хг такие, что ~ У.,тн, ~ /...,тО. тЕХ> «>,»>ВХ« «,ф» Следовательно, для получения таких подмножеств первичных термов (уровней типа А) необходимо в уровень типа В включать первичный терм хл такой, что ~/е = В ~~~ ~ „ ~/г«> = 0 т< б Х>>. »>пХр С помощью такого включения производится выравнивание длин путей.
$4.7. Сини>ее логических струк>оур в >нрорлргически«базиса«335 В рассматриваемом примере при синтезе булева графа в качестве подуровней, взвешивающих падграфы, покрывающие вершины, с весами хт и хт, выбиРаем соответственно 1хз, хв) и 1зь, зз). Очевидно, что подграф Н, покрывающий вершину с весам ха, является частью подграфа тг „покрывающего вершину с весом хв, и, следовательно, /«а> /«ь > где /«ь> — взаимная частота подуровней> взвешивающих подграфы Н, и Н»' /«ь — собственная частота подуровней, взвешивающих подграф Н„.
Частоты /«ь> и /«ь вычисляются по матрице инцидентности модели ф, построенной на этом шаге синтеза. Опишем процедуру выравнивания длин путей. 1. Отыскивается пара первичных терман эч и ху, для которых справедливо / а = /«,. 2. Проверяется равенство длин путей, началом которых являются соответственно вершины, взвешенные х; и х . 3. Если длины путей не равны, то в покрытие вершины, входящей в путь с меньшей длиной, включается расщепленный ее вес. Для рассматриваемого примера повторяем вес х' (рис. 4.45, г). Входной информацией для алгоритма синтеза структурных графов является матрица инциндентности модели ф, задающая ДНФ функции /. Опишем теперь алгоритм синтеза структурных графов.
1. Выделяем множество уровней типов А и С, претендующих на взвешивание первого яруса. Каждый уровень выделяется с помощью покрытия в матрице инциндентлости строк столбцами. Каждое покрытие взаимно однозначно сопоставляется выделяемому уровню. Число выделенных уровней определяет число различных структурных графов, которые необходима построить для поиска графа минимальной сложности.
Выбираем уровень, соответствующий первому покрытию матрицы инциндентности. 2. Для каждого первичного герма з; в выбранном уровне построим подматрнцу инциндентности, соответствующую падграфу, покрывающему вершину с весом х;. Покрытием подматриц инциндентнасти находим подуровни, взвешивающие вершины следующего яруса.
3. Для найденного множества подуровней В = (б;/ 1 = 1, ... ..., Л) строим модель для оценки уровней, претендующих на взвешивание строящегося яруса. 336 Гл. 4. Теория ормаяьных грамматяик и аешомашое 0 0 О 0 1 1 0 0 О 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 г з. 4 5 б Каждый уровень Хт = (Ь;/ 1 = 1, ..., тс) оцениваем с помощью функции 5-1 Ь р(Хт) = ~ ~~ '~, (4.18) тю1 1=1+1 гпе частоты уть А;, ут являются элементами частотной матрицы отношений Г(чт) (Г(тр) = я х я), 4. При наличии нескольких максимальных значений оценок, полученных в п. 3, оцениваем число расщеплений первого типа как расщеплений, оказывающих наибольшее влияние на сложность синтезируемого графа. Выбираем уровень с наибольшим значением р(Х1); прн нали- чии уровней с несколькими максимальными значениями р(Хт) выбираем из них уровень с минимальной оценкой числа расщеп- лений первого типа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
