Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 77
Текст из файла (страница 77)
5.28, б), овределвющнй данную систему булевых фунгщнй г (Х) $ 5.4. Теоретико-структурная минимизация булевых функций Рассмотрим оптимизирующие функционалы усечения вариантов, построенные на основании учета структуры запрещенных фиРур. Исследуем более подробно процесс приведения произвольного мографа к упорядочиваемому виду. Количество меток каждой вершины о; мографа равно собственйой частоте соответствующей буквы модели, а количество общих удеток для пары вершин и; и о (ребра (г, у)) — значению взаимйой частоты соответствующих букв. Следовательно, ребро (г, у) мографа можно характеризовать тремя величинами: Д, уг и угу где Д вЂ” собственная частота буквы г; Д вЂ” собственная частота буквы 7; Д; — взаимная частота букв г и у' (г ф 2).
Прослеживая 'процесс образования запрещенных фигур Яд, 9н, Яв, замечаем, что чем больше сумма Д+ уу собственных чартот букв г и у при данной взаимной частоте Д или чем меньше Зваимная частота Д букв г и у при данной сумме их собственных Флстот, тем больше вероятность вхождения букв г, у в подмоделн Фила Ял, Яв, Ян.
Охарактеризуем каждое ребро (г, у) мографа Ф(у) значением производной от модели, вычисленной на соответствующей паре (в кв: у дф, . Л вЂ” 2Д+Д дЯ ' Д; Тогда чем больше значение производной, тем выше степень одинакового участия букв в словах; чем больше неоднородность графа, тем больше нероятность образования подмоделей вида , Ян, Ян в этой модели, тем более сложный (в смысле числа ментов) сиитезируемый граф соответствует этой модели. Пому максимальный интервал г функции у, которому соответпхвует полный подграф, будем оценивать средним значением р(г) Гл. 5.
||рикладнол элса ил алео иэнмоо 424 5 5.4. Теоретико-структурном минимиэоцил булеаых ункииб 425 производной, вычисленной для каждого ребра этого подграфа, т. е. выражением (5.1) 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 О 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 0 1 О О 0 1 О 1 О 0 1 1 0 1 0 1 0 1 1 0 ! 1 0 1 1 О 1 0 0 С 1 0 1 0 1 0 0 1 0 1 0 1 0 2 3 А 5 8. 9 11 12 14 15 где г — ранг простой импликанты 1 (он равен числу первичных терминов, образующих импликанту), Следовательно, оценка (5.1) позволяет синтезировать оптимальные ДНФ булевой функции, учитывая ее теоретико-структурные свойства.
Используя оптимизирующий функционал, представленный в виле оценки (5.1); приведем приближенный алгоритм теоретико- структурной минимизации булевой функции. 1. Заданную ДНФ функции ! определяем в виде матрицы инцидентности Я. 2. Выделяем простые имплнканты функции !' и записываем их в список 1. 3.
Строим ядро функции !. Если оно пустое, то переходим к и. 6, в противном случае из списка 1 вычеркиваем элементы ядра и переходим к п. 4. 4. В матрице Я заменяем единичные интервалы функции 1, покрываемые вычеркнутыми из списка 1 простыми импликантами, на эти простые имплнканты.
5, Если любая строка матрицы Я представляет собой простую имплнканту, то переходим к и. 8, в противном случае — к и. 6. 6. По матрице Я строим частотную матрицу отношений Р = — С)т х (). 7. Согласно (5.1) оцениваем каждую простую импликанту из списка 1.
Выбираем простую импликанту с минимальной оценкой, вычеркиваем ее из списка 1 и переходим к и. 4. 8. Определяем, задаст ли построенная матрица Я тупиковую форму. Если нет, удаляем избыточные простые импликанты. Полученная матрица Я задает минимизированную булеву функцию с учетом ее теоретико-структурных свойств. Пример 5.3. Мнннмпзнруем с учетом теаретлво-структурных свойств булезу Фуявшэю 1(лэ, *з, *з, хэ )(,= Ч(2, 3, 4, 5, 8, 9, 11, 12, 14, 15); на остальных наборах она равна нулю. 1.
Матрнка Я имеет знл Уэ ез зз ез Уэ еэ Уэ 2. Спксов 1 кроснах нмплнкант булевой $унпшэя следующий". 001-, 100-, 11-0, 010-, -011, 1-11, †1, 10-1, 111- . 3. Функция 1 нмеет ядро, состотцее нз абяаательных простых нмплнкант 010-, 001- н 100-. После вьэчеркнааиня элементов ядра свнсок ! принимает внд -100, 11-0, -011, 1-11, 10-1, 111-. 4. В результате соответствующей замены отрав матрнка !с прнннмает внд Уз зэ Уэ 1 1 0 0 0 1 1 0 1 1 1 0 О 0 1 0 1 О 0 1 0 з! Уэ зз 0 1 0 0 1 1 ! 0 0 1 О 0 1 0 1 1 О 1 1 0 1 001- озо- 100- 11 12 14 15 5. Строка матрацы 4)' с четвертой по седьмую не нмклнкантам, поэтому перехожие к и. б.
6. Частотная матрица отношення Р' (Р' = (ЭЭ') матрице !2', такова: соответствуют простым х !2'), соответствующая зэ Уэ оэ еэ 3 2 2 2 1 1 0 0 2 2 1 2 2 ! 1 0 4 0 2 1 0 3 0 1 2 0 2 0 1 1 0 2 Уэ аз Уг 0 3 2 2 1 1 1 4 0 1 0 3 1 2 2 1 2 1 0 1 1 0 2 0 У. Оценнваем ваядую простую нмвлнаанту яз спасла, полученного а и.3. Согласно (5.1) имеем Р(-100) м р(хзузуэ) = 1 14 — 2 ° 2-!.3 4 — 2 2+2 3 — 2 ° 1+21 3 ° 2~ 2 2 2 р( 011) яэО 91, р(10-1) зз 1,за р(1-11) ш О 58, р(11-0) ш 0,58, р(!!1-) ю 0,67. |)ьэбнраем простую нмплнпанту 11- О н переходнм к и. 4.
4. В матрице эс' заменяем ютстнтуеэпы еднннкы Фунпцнн 1, покрываемые лнкантой 11-0, на зту простую ямвлнвмпу. В результате колупаем матрнду Уэ ог зз оз ~з ез Уэ 0 1 О 1 1 0 О 0 0 1 1 О 0 1 0 0 1 0 О 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 001- 010- 100-. и-о 11 15 5. Матрица э„) содерянт канстнтуенты едннякы Фунвцян, не являюшяеся Простымя нмплнвантамя. Пер еходнм в д. 6. еэ 5 0 3 2 3 2 2 2 0 0 0 0 0 0 1 0 0 1 0 1 1 0 оэ еэ зг Уг ез Уз еэ еэ 5 5.4. Теореглико-структуривл мииимивоцил булевых ункчид 427 Гл.б.
Лрикладиол теорие алгоритмов 426 б. Частотная мзтрине отношений Р", соответствующая 4)", имеет зид Пт Ве Сз 2 2 1 1 1 1 0 1 1 3 2 1 2 3 0 о 1 2 0 о о о е) 4 0 г 2 2 1 2 1 ет о г г 1 3 1 0 1 1 1 1 о о 2 1 0 0 1 1 о 2 0 0 0 2 0 0 1 Е2 Л) Ст Лт. Сз ее ее Пе Ра 7. По формуле (5.1) оцениваем аростью импликонты нз списка 1, покрывающие оставшиеся канстнтуекты еаннилы фунвани !. Имеем р(-011) ш 0,75, р(1-11) ю 0,5, р(10- 1) 0,91, р(111-) ш 1,16.
Выбираем простую импликзнту 1-11 н переходим а и. 4. 4. После соответствующей замены строп, получаем метрнду ее оз ае 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 О 0 1 О 1 О 0 1 0 1 0 О 0 О 1 1 О О О 1 О 1 0 001- 010- 100- 11-0 1-11 )х)= (г г ' '). )2.2) 5. Любви стропе матрицы С)о' соответствует дростай импливолте. Переходим кп.
б. З. Метрика Яо' зедеег булеву фуюонпо у, минимизяровенную с у'тетом ее теоретико-струвтурных свойств. Ислользунмсгод сементнчеспагоэквнззлентнрозения, установим, носвольва удалена полученная ТДНФ функции у(л), хт, ле, хе) от ТДНФ фунвпии у, соответствующей минимальному структурному трефу. Йойдем все тупиковые ДНФ фунвнни !. Для етого построим нмплнвентиую таблицу и определим ее поврытин. Кендую ТДНФ функции ! задаем з виде магрофе.
Выделам запрещенные фигуры типов А и Б и построим сементи геенне таблицы. Затем нейдем и оценим их паврытян. В результате акенегсн, что тупюювен ДНФ, полученнен с помощью вредланелного елгоритме минимизовни, свободного ат переборе всех тупиковых ДНФ, соответствует абсолютна мяннмольному решению. Рассмотрим теоретико-структурную минимизацию системы булевых функций Р(Х). В эхом случае каждой многовыходной простой нмплнканте, как н простой импликанте прн минимизации одной булевой функции, соответствует полный подграф, вершины которого взвешены идентификатором этой МПИ в мографе СА4.
Учет распределения запрещенных фигур в рассматриваемом случае может быть оценен выражением (5.1). При этом производные вычисляют толъко для дуг, соединяющих вершины, взвешенные буквами т; и игу, для которых р(нт;) = р(тн.) = О. Для простоты опустим в выражении (5.1) постоянную частотную составляющую и будем оценивать МПИ по формуле Предложим следующую процедуру минимизации системы булевых функций с учетом их теоретико-структурных свойств, основанную на применении оптимизирующего функционала. 1. Задаем систему булевых функций Р(Х) = 1Л(Х) Ь(Х)2 "2!ь(Х)) множествами М1, Мо.
При этом ))' 1 на элементах Мг, ((О на элементах Мо. 2. Находим одним из известных способов все МПИ булевых функций и заносим их в список !. 3. Строим матрицу Я, каждому столбцу которой соответствует первичный терм, строке — конституента единицы (импликанта) 'функции у2(Х) б Р(Х) и 1, если зь входит в (-ю конституенту (импликанту), О в противном случае.
4. Определяем обязательные МПИ в списке !. Если они име)2отся, то переходим к и. 5, вычеркивая обязательные импликанты )бсз списка !. В противном случае переходим к и. 7. 5. Корректируем матрицу Я, заменяя конституенты единицы, :.покрываемые вычеркнутыми МПИ, этими МПИ. 6. Если любая строка матрицы Я представляет собой МПИ, то зцереходим к п. 9, в противном случае — к п. 7. 7.
По матрице Я строим частотную матрицу отношений бвт Теблнце 5.11 Р= Я х 42!. *2 *2 Лт Х) у) ут ув 8. Оцениваем каждую о о О о 1 о ~МПИ, вычисляя значение о о о 1 о о 'с(!). Выбираем МПИ с О О 1 0 0 О 1 0 0 1 1 1 0 1 ;Мннималъным Значением ')0~ни(!). ВыбРаннУю МПИ о 1 о 1 о о :вычеркиваем из списка 1 о 1 1 о о о о ,;й переходим к п. 5. 9. Устраняем избыточ- 1 О О О 1 1 0 "ность строк в матрице (4. 1 о 1 о о Матрица ъ! задает мини- 1 о 1 1 1 о )Визированную систему левых функций Р(Х) с (учетом теоретико-структурных свойств.
Пример 5.4. Задано системз булевых функднй Р(Х) = (у)(Х), у2(Х), Уе(Х)) (гобл. 5.11). "55.5. Характеризацил разлолсенцл графа перехас)ае 429 Гл.5. Прикладнал шеорил алеарпшмае 428 2. Список 1 многозыходных простых нмплнаант системы г (х) следующий; 3, 1з 3, 1» 1, 1з 3, 1ыю 1,3, 1и= 1,3~, 1„= 3, 1г 3, 1з 2, 1» 3, 1м 1 = оо-- 1» = -01- 1» = 1--0 1се = 1--1- 1ы = 1-11 1 = 1-10 Лз — — -100 0-0 -10- --11 11-- 11-0 -011 0-00 — -00 1-0- 1- -1 11-1 110- 1-00 1100 1,3, В скобках указаны яомера функций, рабочие точки которых покрызает со. атзетстзуююий интерпол. 3. Состазляем матрицу Я, з которой зандак копстнтуента едспсицы позторяегся столько раз, сколько ана юсодкт з булезы функции, 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
