Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 84
Текст из файла (страница 84)
Выбираем покрытие хз как оптимальное, так как при этом расшепляется минимальное количество точек пространства Р(Х,) (рис. 5.47, б, в, г). В результате размерность пространства Р(Х,), Х, = (х1, х2, хз), увеличилась Иа 1: Р(Х„) — 1 Р(Ха), Х~ = (х1, х2, хз, хв), размерность пространства Р(Хь), Хб = (хв, хб), — также на 1: Р(ХЬ) -+ Р(Хь), Хь' = (хг, хв, хб). Пространству Р(Х,') соответствует граф противоречивости гз„р(Х,') (рис. 5.48,а), пространству Р(Хь) — граф О„р(Хь) Гл. 5.
Прикладная теория аягорил>мов (рис. 5.47, в), хроматические числа которых равны Гь(>лир(Х>)) = =3, Ь(а„,(Х,')) =2. Соотношение (5.7) справедливо: [1о$2 Й(блр(Хв))] + [10$2Слр(Хь)] < 5> следовательно, функциональная декомпозиция сушествует. Для ее построения раскрашиваем вершины графа Гзлр(Х,'): а=(0,2Я,З",7~, Ь вЂ” (1,2',5,6), с=(3'1, и вершины графа Гзлр(Хь): ст' = (О', 2), Гу = (О", 1, 3). Кодируем краски: а — 01, Ь вЂ”,10, с — 11, используя функцио- нальные символы 1Р1>Р2, и при кодировании ст — О, ГЗ вЂ” 1— символ >Рз. Склеивая соцветные вершины, получаем внешнюю функцию Р(>Р1» Р2> >Рз) (рис.
5.48, б). В результате получим функ- циональную декомпозицию вида у(х1, хз, ...,хь) = = Р(>Р1(х1> х2, хз> х4)» Р2(Х1> х2> хз> Х4)» Рз(х1> х4> хб)) ( 1 на 1, 2', 3', 5, 6, >Р1(хм х2, хз, хь) = [ О О' 2л' 3» ( 1 на О, 2", 3', 3", 7, >Р2(Х1>.*2> хз> Х4) = ~ 0 (1 на О",1,3, >Рз(хь> хь, хб) = 0 0> Г1 на 2,5, '1 О на 3, 4, 6, 7. Таблица $.42 Матрица Вейча, соответствуюшая этой декомпозиции, имеет вид табл. 5.42.
15.8. Синтез функциональной декомпозиции в Гт-знвчной логике 467 35.8. Синтез ф ициональной деиомиоанцнн в >с-значной логике Обобщим найденные критерии функциональной декомпозиции на случай Гс-значной логики. Теорема 5.10. Функция Гт-эначной логики /(Х) декомпоэи- руема в виде Р(1Р1 (Х.), ч'2(Х.),..., Р*(Х.), Хь) тпогда и только птогда, когда [1обь Гь(0лр(Ха))] < ~Ха)> Ха ОХь = Х, Ха Г1 Хь = О; (5 8) ( ] — знак близкайи>его целого числа; >злр(Х,) — граф противо- речивости, соответствующий пространству Р(Х,), Р(Х) = = Р(Х,) х Р(Хь). Теорема 5.11 (А.В.
Горбатов). Функция Ь-эначной логики у'(Х) декомпоэируема в виде Р(>Р1(Хв) » Рз(Ха) » ° ° >Ра(Ха) > т71 (Хь) > тГ2(Хь) » ° ° цт(Хь)) тогда и только тогда, когда ([1обь Гь(>зпр(Ха))] < ]Х,])Й([1обь Гь(бпр(Хь))] < ]Хь!) (5 9) при совместной раскраске стпрочного графа протпиворечивос- ти С„р(Х ) и стполбцевого графа противоречивоспьи С„р(Хь), Х, О ь = Х, Х, Г1Хь = О, при предстповлении прострайства Р(Х) в виде Р(Х,) х Р(Хь). Теорема 5.12 (А.В. Горбатов).
Функци,я /с-эначной логики 1(Х) декомпоэируема в виде Р(>21(Ха)» Р2(Ха)» . >Рт(Ха)> тд(Хь)> тГ2(Хь)» тГт(Хь))> Х, и Хь = Х, Х, Г1 Хь уь О, тогда и тполько'тогда, когда после редукции хроматических чисел Гь(>злр(Х )) и Гь(>злр(Хь)) [1обь >7(Я,)] + [1обь д(ьГь)] < !Х], (5.10) где д(Я ) — кваэиплоп>ность редуцированного стпрочного гра- фа противоречивости >лир(Х,); >уфь) — кваэиплотностпь реду- цированного столбцевого графа противоречивости Гзир(Хь).
Рассмотрим функцию трехзначной логики 2 на 0,2,3,23,38,43,67,68, У(х1> х2> хз, х4) = 1 на 10 27 29 35 50 53 57 60 61 79 0 на 4,8,21,33,45,51,78,80. Представим исходное пространство Р(Х) в виде произведе- ния двух сопряженных надпространств Р(Х,), Р(Хь), Р(Х) = = Р(Х,) х Р(Хь), Х, = (х1, хэви, Хь = (хз, хь); тогда матрица Вейча имеет вид табл. 5.43.
468 Таблица 5.43 Дь(4, 0> з з Да(3, (> Да(4, 0) Дз Рис. 5.5! ЛЗЗ4 О 1 2 3 4 5 б 7 В Рис. 5.50 Рис. 5.49 Таблица 5.44 Гл.б. Приклоднал теорие алгоритмов Таблица Вейча (табл. 5.43) определяет граф Кенига (рис. 5.49), и строчный граф противоречивости бар(Х,) (рис. 5.50), ребра о О ! 2 3 4 5 б 7 В 7 з!зз которого взвешены сцепляюшими векторами сопряженного пространства Р(ХВ). Размерность пространства Р(Х,) равна 2: г(Р(Х,)) = 2.
Следовательно, чтобы по переменным х(, хз существовала декомпозиция, необходимо и достаточно, чтобы хроматическое число Ь((з„р(Х,)) было равно 3; тогда одним троичным символом можно $5.8. Синтез !бункциональноб декомпозиции в к-значноб логике 469 закодировать краски вершин графа (знр(Ха): 3"~~~~'В !. Отсюда, запрещенными фигурами при поиске этой декомпозиции будут з квазиполные графы квазиплотности 4: Я(4). Граф сзир(Х,) содержит шесть квазиполных подграфов квазнплотиости 4 (рис.
5.51): (Р((4, О) = ((О, 2), (О, 5|, (О, 6), (2, 5|, (2, 6), (5, 6) ), дэ(4, О) = ((О, 3), (О, 5), (О, 6), (3, 5), (3, 6), (5, 6) ), Яз(бю 0) = ((Зв 5)~ (31 6)в (3 8) (5з 6)ю (5~ 8)~ (61 8))ю Щ4, 0) = ((3, 4), (3, 6), (3, 8), (4, 6), (4, 8), (6, 8)), Яб(3, 1) = ((О, 2), (О, 3), (О, 5), (2, 5), (2, 6), (3, 5), (3, 8), (5, 6), (5, 8), (6, 8)), Яе(З> 1) = ((О, 2), (О, 5), (0~ 6)~ (2~ 5), (2 6) (3 4) (3, 5), (3, 8), (4, 6), (4, 8), (6, 8)).
Семантическая таблица, определяющая распределение ребер по запрещенным фигурам, имеет вид табл. 5.44. 470 Ь (О',2,3,5",$~).» зз 0 5 с (О".1,5,7 $) ' С)О ( ) 0" +100 хз хв 0~.~100 "~хз, «в 7 -«-21 0"~100 хз, хв 1 ° -01 - хз, хв ~ хзхзхв 5~"12 +хз, хв 7 е-21 В" Вхз 8'= Вхс )) Вхз 7 -2! х Вл 122 ™в Рнс. 5.52 Гл.б.
Прикладная теория алгоритмов Минимальным покрытием строк столбцами является ((О, 5), (3, 6) ); после соответствуюшего сужения сигнатуры графа противоречивости ('ир(Х,) его минимальная раскраска имеет внд а=(0,4,5), Ь=(1,2,8), с=(3,6,7). Склеивая соцветные вершины графа Сир(Х,) и расширяя сопряженное пространство Р(ХЬ) до пространства Р(Х'), Х' = (хз, хз, хв), штриховкой векторов О, 6, 8 Е Р(ХЬ), которыми сцеплены удаленные из графа ('ир(Х,) ребра, получаем граф Кеннга (рнс.
5.52). Верхний ярус графа Кеннга соответствует введенной 0 = (О, 4, 5) 1 (1, 2, $) 2 (3, б, 7) хз) ! 0'-Ох,' 0 -Ох!! р з" 1'2 3 4 5 б'=без! б" бх( функции из!(хз, хз), полученной после кодирования красок а, Ь, с графа сзир(Х,) значениями соответственно О, 1, 2: (О на 0,4,5, (оз(хз хз) = 1 на 1 2 8 2 на 3,6,7. СтРонм гРаф пРотивоРечивости Сир(Хь) длЯ веРшин нижней доли графа Кенига (рис. 5.52). Этот О» граф имеет вид, представленный на рнс, 5.53. Редуцируем хроматическое число )з(Сир(Х~)) до 3, чтобы согласно (5.10) можно было синте- 8' зировать внутреннюю функцию искомой декомпозиции в пространстве Р(Х,'). Запрешенными фи- 7 гурами прн этом поиске будут ква- зиполные графы квазиплотности 4. 4 Читателю предлагается найти эти подграфы и на основе распределения ребер в них определить оптиРнс.
5.53 мальное сужение сигнатуры графа 15.8. Синнзез рнкционаяьноп декомпозиции в Ь-змеиной логике 471 Сир(ХЬ). Одним из таких сужений будет удаление семи ребер: (4,6'), (О",5), (О",7), (0,8е), (1, 5), (5,7), (7,8е) (рис. 5.54), в результате чего хроматическое число )з(вх„р(ХЬ)) (х!) хз) хв) а (4,5',$') 1 ~ — ~~ 4-е-11 б-в-20 .+ хз, .хв Рнс. 5.54 становится равным 3 (рис.
5.55): а = (4, 6', 8'), Ь = (О', 2, 3, 6", 8т), с = (О", 1, 5, 7, 8н). При удалении ребер необходимо учитывать, что нельзя удалять ребро, вершины которого взвешены одним и тем же вектором рассматриваемого пространства, на- Ь О' пример, в нашем случае ребро 0" (8', 8н) (см. рис. 5.53), так как векторы 8', 8и Е Р(Х,') не отличаются переменными йодпространства Р(ХЬ), и, следовательно, штриховка сцепляюшего их вектора 0 (О Е с Ь 2 Е Р(~рз)) физически не реализуема: отсутствуют переменные подпрост- 7 с 3 ранства Р(ХД, которыми отличаются векторы 8' и 8н и которые могли 4 быть вделегированы» в сопряженное подпространство для штриховки сцепляюшего их вектора. Рнс. 5.55 Гл.б. Прикладная теория алгоритмов 472 15.9. Синтез функционаяьноа декомаозиции 473 В рассматриваемом случае (см. рис.
5.54) для сацветности вершин 4, 6', 8' необходимо была удалить ребро (4, 6'), для чего расширить сопряженное надпространство Р(~р!) да Р(!рь, хз) или Р(~р„хь) переменной хз или х4, которыми отличаются векторы 4 и 6'. Вершины 0', 2, 3, 6", 8т образуют пустой полграф, и удаления ребер не требуется. Пля соцветнастп вершин 0', 1, 5, 7, 8а необходимо удалить шесть ребер При этом векторы, соответствующие вершинам ребер (О", 5), (О", 7), (О", 8а), (1, 5), 15, 7) отличаются как переменной хз, так и хь.
Векторы, соответствующие ребру (7, 8а), отличаются переменной хь. Следовательно, при расширении переменной хь сопряженнога подпространства Р(~р!) -+ Р(~рь, хь) реализуема штриховка всех векторов подпространства Р((о!), порождающих семь удаляемых ребер в пространстве Р(Х'). Склеиваем сацветные вершины, окрашенные красками а, 5, с (рис. 5.56); кодируем эти краски соответственно как а =Ояь! !'- (4 „!"- (4, 2"-2г) О' Оя( О Оя( !" ьяь! 2' 2гу 2"'= 2яг / г ! р!гь рг а (4,б~з'1 ь (О',2,з,б",3 ) с (О",ь,б,7,31 Рнс б.бб О, 1, 2. В результате полученный граф Кенига определяет внешнюю функцию Р(Ьог, хь, ~рэ) искомой декомпозиции: ! (х! ~ х21 хз) хь) = Р(фь(хг~ Х2), х41 фз(хь, хз) хв)).
Здесь функция трехзначной логики от четырех переменных представлена в виде оптимальной повторной декомпозиции одной функции (р! ат двух переменных и двух функций <рз и Р от трех переменных. Вид функции <р! был представлен выше. Функция <рэ(хь, хз, хз) имеет вил (см. рис. 5.52) 0 на -11, 120, 022, свь(хь,хз, хь) = 1 на 000, -02, -10, 220, 222, 2 на 100, -01, -12, -21, 122. Функция Р(~рь, хь, ~рр) имеет вид (рис. 5.56) О на 000, 002, 010, 020, 101, 121, 200, Р(ср„ хь,<рз) = 1 на 022, 112, 201, 202, 211, 212, 221, 222, 2 на 001, 011, 012, 021, 122, 210.
Таким образам, стратегия синтеза оптимальной функциональной лекомпозиции в (с-значной логике заключается в выполнении следующих этапов: — разбиение исходного пространства Р(Х) на два сопряженных, Р(Х,) и Р(Хь); Р(Х,) х Р(Хь) = Р(Х), Х,(2Хь = (с(, Х, (!Хь = Х; — построение графа противоречивости Сар(Х,), его раскраска и, если эта необходимо для выполнения соотношения (5.8), осушествление редукции его хроматического числа путем расширения подпРостРанства Р(Хь) до Р(ХЬ), Хь — — Хь (.! 4".ьХ„' — склеивание соцветных вершин графа !а!ар(Х,), кодирование красок и построение соотвегствуюших внутренних функций в полпространстве Р(Х,); — построение графа противоречивости Сар(Х'), его раскраска и, если это необходимо для выполнения соотношения (5.9), осушествление редукции ега хроматического числа на основе расширения надпространства Р(Ф) до Р(Ф'), Ф' = Ф!ьХЬ; — склеивание соцветных вершин графа ('ар(ХЬ), кодирование красок и построение соответствуюших внутренних функций в падпространстве Р(ХЬ); — при необходимости дальнейшая декомпозиция полученных внутренних функций на основе этой стратегии и в результате построение внешней функции Р искомой декомпозиции.
3 5.9. Синтез функциональной деномиоаиции заданной размерности Многие практические задачи сводятся к синтезу функциональной декомпозицик булевой функции, в которой полученные внутренние и внешняя функции имеют заданную размерность. Рассмотрим синтез функциональной декомпозиции булевой функции у(хь, хэ, ..., х„) через функции от четырех переменных. Тогда в выражении (5.5) параметры (с н з удовлетворяют неравенству Й+ в < 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
