Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 41
Текст из файла (страница 41)
Согласно (3.31) и (3.34) имеем Ф()(ч) 0Б(Ф9(д)) цБ(Б(Ф()(д))) ц...0Б(Б...(Б(Ф()(ч)))...)ц » рвз иа(г(к...( (вз(з)))...) =вз(з+ И, (ззз) » р»з Проиллюстрнруем формулу (3.35) с помощью рис. 3.48. Для д = 4 Ф9(4) = Ф~(3) ц Б(Фр(3)) 0 Б(Б(Ф~(3))) ц 0Б(Б(Б(Ф (3)))) ц Й(Б(Б(Б(Ф (3))))). Очевидно, что всякая квазиполная модель первого порядка содержит не менее трех слов и всякой квазиполныб граф (ква- зиполная модель плотности 2) первого порядка плотности р содержит не менее р+ 3 вершин (рис. 3.49): С(3(4, 1) = (У, Ц, ~Ц = 7, ~У~ = р+ 3.
Теорема 3.45. Ф = Ф9 (р, 9) 4+ Ф = Ф()(р, 1) Ц ц (Б(Ф(2(р, з)) ц Й(Б(Фч(р, з)))/) = 1, 2,, Й вЂ” 1) 13.9. Харакзпсризаиил частичного упорядочения мографа 227 93.9. Хврвктеризаиия частичного упорядочения могрвфв Рассмотрим семантику (смысл) преобразования мографа (хм в диаграмму Хассе (структурный граф) Н при логической интерпретации. Прежде чем установить причины, приводящие к тому, что одному первичному терму сопоставляют две (н более) вершины в структурном графе (расщепляют первичные термы), рассмотрим преобразование мографа в структурный граф прн задании тупиковой ДНФ булевой функции у(х1, хг, ..., хг) = = х)хзха Ч х)х4 Ч хххз Ч х)хзхз Ч хзхахз Ч хххвхз, 2 З 6 в которая определяется моделью Ф, = (М, Яхз ЯЗ)з М = (Х)з Хы Хз, ХЗ, ХЗ, Хвз Хаз Хз ХЗ), 'з2 = 11Х)з Х4) з 1Х2з ХЗ) )з Яз = 1(1зх)з хз, хз), 1зх), хз, хз), (хз, хаз хз)з (хг, х4, хь) ) Мограф См(Ф,) изображен на рис.
3.50, а. Рассмотрим подмограф ((хм)' (рис. 3.50, 6), задающий третью, пятую и шестую простые импликанты. Сопоставим третьей импликанте хххз цепь и(хх) < и(хз). Пятой простой импликанте хзхвхг сопоставим цепь и(хз) < и(х4) < о(хг), шестой импликанте хгхахг — цепь о(хг) < и(Х4) < о(хг). При таком задании ОХНОШЕНИЯ УПОРЯДОЧЕННОСТИ ПОЛУЧаЕМ, Чта О(ХХ) < О(ХЗ) < О(Х4) з > т.
е. о(хз) сравнима с о(х4), о(хх) < о(х4), что противоречит заданию. 228 Гл. 3. Творил графов и могрвфов 13.9. Харакюгриэаиил часюичного унорлдочгнил мографа 229 Чтобы ответить на вопрос, является ли такое задание отношения < просто неудачным, не зная семантики преобразования, необходимо построить полностью синтаксическое дерево этого цреобразования, висячим вершинам которого соответствуют диаграммы Н;, и рассмотреть при этом не только эти три простые импликанты, но весь заданный мограф С~(Ф ). Число висячих вершин этого дерева равно 2! 2! 3! 3!.3!-3'. = 5184.
Фактическим построением такого количества диаграмм можно убедиться, что не существует способа задания отношения < в рассматриваемом мографе 0 (Ф,), при котором имеет место взаимно однозначное соответ- М ствие между первичными термами х и вершинами диаграмм Н такое, что каждая цепь и(х,„) < и(х„) « ... и(х,,) взаимно однозначно соответствует простой импликанте х,, х,,... х„.
Трудоемкость выявления таких противоречий, а следовательно, и построения абсолютно минимальной схемы, значительно меньше, если известна семантика преобразования, определяемая распределением запрещенных фигур, т. е. решена проблема характеризации преобразования См(у) -+ Н(у).
Введем понятие гомоморфных моделей. Разложением слова р = (т; / 1 = 1, 2, ..., э) на глубину 1с, О < Й < г-2, называется замена этого слова на (,' ) слов, каждое из которых образуется взятием э — 1с букв из слова и, причем лексикографически одинаковые буквы, входящие в полученные слова, считаются различными и переименовываются. Например, после разложения слова и = (у, х, а) на глубину, равную 1, получаем три слова: (у', х), (х', а), (а', у).
Разложением на глубину й нодмодгли Ф', состоящей из одного слова и в модели Ф, называется замена ее подмоделью, образованной разложением слова 1с на глубину Й и повторением каждого слова ус, (1с, Е Ф 1 Ф') вида а П р, ф й1 столько раз, сколько раз были повторены буквы (до их переименования при разложении слова и), принадлежащие ни и„причем при построении и, эти буквы записываются каждый раз в переименованном виде. Например, рассмотрим модель Фв = (М, Зт, ~з) М=(у,х,а,с,о,р), Ят = ((у, с), (о, х), (а, рЦ Яз = ((у, х, аЦ.
Разложим-подмодель Ф',„= ((у, х, аЦ, состоящую из слова и = (у, х, а), на глубину, равную 1. В результате разложения этой подмодели слово и заменяется словами (у', х), (х', а), (а', у); слова (у, с), (о, х), (а, р) — славами (у, с), (у', с), (о, х), (о, х'), (а, р), (а', р). Окончательно в результате разложения подмодели Ф' на глубину, равную 1, получаем модель Фд = (М, Яэ), М = (у, х, а, у', х', а~, с, о, р), Яэ — ((у', х), (х', а), (а', у), (у, с), (у, с), (о, х), (о, х ), (а, р), (а', РЦ.
Две модели иэоморфны, если их матрицы инцидентности подобны с точностью до переименования букв. Модели называются гомоморфными, если одна из них преобразуется с точностью до изоморфизма в другую разложением некоторых подмоделей. В рассмотренном примере модели Ф и Фд (рис. 3.51) являются гомоморфными. При разложении подмоделей на нулевую глубину получаем изоморфные модели. Для получения неизоморфных моделей необ- Рис. 3.51 ходимо разлагать на положительную глубину; для этого нужно, чтобы мощность разлагаемого слова р, а следовательно, и степень сигнатуры подмодели Ф' = (ус), была больше 2, т. е. чтобы модель ,Ф' не являлась графом.
Для графов, как известно, существует свое понятие гомоморфизма. Два графа называются гомеоморфными, если один из них преобразуется с точностью до изоморфизма в другой путем замены некоторых ребер цепями (разложением ребра в цепь) произвольной длины. Например, графы С и Сд (рис. 3.52) 'являются гомеоморфными. В случае графов гомоморфизм имеет линейную структуру.
Для мо- 5 с делей, не являющихся графами, гоМоморфизм имеет более сложную Рис. 3.52 структуру — сочеп~аоггльную. Гомоморфизм (линейный) графов изменяет только мощность их носителей. Гомоморфизм (сочетательный) моделей, не являющихся графами, изменяет не только носители, но и их сигнатуры. Гл.З. Теория графов и мографов 230 хх(З, б/ тг(5/ з/( сф / Рис.
3.53 хг хг х/ Рис. 3.54 Модель называется частично упорядочиваемой, если найдется взаимно однозначное соответствие // между ее буквами и вершинами диаграммы Хассе, при котором каждое слово модели взаимно однозначно соответствует цепи, составленной из вершин, соответствующих буквам этого слова. Теорема 3.46. Модель ч/ частично упорядочиваема тогда и только гпогда, когда она не содержит подмодели, гомоморфноб квазиполноб подмодели положительного порядка: ф ~/ ф(/(р /,) ~ > 0 На основании этой теоремы и свойства включаемости квази- полных моделей (3.32) имеем теорему 3.47. Теорема 3.47.
Запрещенными фигурами ЯА, Ян преобразования мографа С~ в диаграмму Н являются подмографы типов А и Б (рис. 3.53). Подмограф типа А представляет собой цикл нечетной длины с циклической перестановкой идентификаторов слов. Подмограф типа Б является треугольником с висячими вершинами, каждая нз которых имеет общий идентификатор со смежной висячей верши- ной, и все вершины треугольника имеют общий идентификатор; при этом висячие вершины могут совпадать как попарно, так и все вместе с соответствующкм объединением их идентификаторов. Наличие одной из таких фигур в мографе делает принципиально невозможным задание отношения < прн преобразовании ( 'М -+ Н без расщепления первичных термов в мографе (хм, причем такое расщепление без знания семантики преобразования (хм -+ Н происходит "вслепую".
При этом кроме ликвидации запрещенных фигур расщепляются лишние первичные термы, что уменьшает оптимацьность получаемого решения. Выделение запрещенных фигур типов А и Б сводится к задаче нахождения циклов нечетной длины в мографе с последующей проверкой распределения идентификаторов слов (весов) на 53.9. Ха актеригаиил частичного упорядочения мографа 231 них. При выделении циклов нечетной длины в мографе вершины с одним весом не рассматривают как вершины, которые могут соответствовать только висячим вершинам фигур типа Б. В приведенном выше примере для выделения циклов нечетной длины достаточно рассмотреть подграф (С~)», изображенный на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
