Введение в прикладную комбинаторику, Кофман А. (984071), страница 30
Текст из файла (страница 30)
Так как Π— наибольший элемент М, то Π— нижняя грань А. Аналогично Π— верхняя грань В=(В, С,О). Максимальная цепь, Цепь С называется максимальной, если она не содержится строго ни в какой другой цепи. П р им ер 1. Граф на рис. 177 можно рассматривать как множество с отношением порядка: Х; ~( Хь если Х; я ГХь Цепи (Е, В, О, С), (Е, Е, А) максимальные, цепи (В, О, С), (Е, В, С), (Е, О, С), (Е, А) не максимальные. При мер 2. Рассмотрим множество Е делителей числа 36, упорядоченное отношением «Х~ делит Хга (рис. 178). Цепь С = (1, 3, 9, 18, 36) максимальная, так как для любого элемента из Š— С можно найти элемент из С, не сравнимый с ннм. Очевидно, что (1, 2, 36) — не максимальная цепь.
Верхняя полуструктура. Упорядоченное множество называют верхней полуструктурой, если для каждой пары его элементов существует верхняя грань. Нижняя полуструктура. Упорядоченное множество называют нижней полуструктурой, если для каждой пары его элементов существует нижняя грань. Рис. 177. Рис. 176. Пример 1. Упорядоченное множество на рис. !79 — верхняя полуструктура.
Действительно, зпр(А, В) =А, аир(Л, С) =А, вцр(А, О) =А, зпр(А, Е) =А, апр(В, С) =В, впр(В, О)=А, вцр(В, Е) =А, (39.7) апр )С,.О) = А, впр (С, Е) = А, зцр (О, Е) = Л, Это не нижняя полуструктура, так как (О, Е) не обладает нижней гранью. Если на рис. 179 изменить направление стрелок на обратное, то для упорядоченного таким образом множества справедливо обратное утверждение.
П р и м е р 2. Любая цепь является одновременно верхней и нижней полу- структурой, как, например, множество (Л, В, С) на рис. 179. То же справедливо для множества на рис. 178. П р и м е р 3. Множество У(Е) подмножеств из Е, упорядоченное по включению, — одновременно верхняя н нижняя полуструктура. Действительно, если А, В ~Я(Е), то Рис. 179.
апр(А, В)=А() В, (39.8) !п1 (А, В) = А П В. (39.9) Структуры. Упорядоченное множество, являющееся одновре- менно верхней и нижней полуструктурой, называют структурой, или решеткой. Примеры структур: упорядоченное множество (Л, В, С, .О, Е, Е, О) на рис. 180; множество всех подмножеств множества Е = 226 = (А, В, С) (рис. 181); множество делителей числа 36, упорядоченное отношением делимости (рис. 178). Рис. 181 Рис. 180 Подструктуры. Пусть Т вЂ” структура и подмножество А упо. рядочено введенным в Т отношением порядка.
~.,в~-,, / '~1л Рис. 188. Рис. 182. Назовем А подструитурой структуры Т, если для любых двух элементов Х, У ~ А верхняя и нижняя грани впр, (Х, У) и !п1, (Х, У) (39.10) принадлежат А, т. е. (их) (17У) (Хе= А и У еи А) ~(вирт (Х, У) ~ А и 1п1т (Х, У) ев А) (39.11) или р,(х, У) = р„(х, У) А, !и!т (Х, У) =!и!и (Х, У) еи А. (39.12) Примеры подструктур:(А, С, Е, Е, 6) — подструктура структуры (А, В, С, О, Е, Е, 6) (рис. 182); (О,(В),(С),(А, С),(В, С), Е)— подструктура структуры У(Е), где Б = (А, В, С) (рис. 183); 227 множество А = (1, 2, 3, 6, 12, ! 8, 36) (39.13) — подструктура структуры Т делителей числа 36 (рис.
184), а множество В= )1, 2, 3, 12, 18, 36) (39.14) — не подструктура этой структуры (рис. 185), так как апр (2, 3) = 6, 6 Ф В и, более того, в В не существует верхней грани для (2, 3) в силу того, что множество М = (12, !8, 36) его :эх';9 /у'\ .4П ) Рис. 184 Рис. 188. мажорант не обладает наименьшим элементом в В; подмножество (рис. 186) С = )1, 2, 3, 4, 6, 9, 36) (39.15) — не подструктура структуры Т, так как эпр (4, 6) = 12 и 12 ф С, однако легко убедиться, что С вЂ” структура; множество У(Е) — (Е, Я), упорядоченное по включению, не является подструктурой структуры Я(Е), так как оно вообще не структура (не является ни верхней, ни нижней подструктурой).
Заметим, что для любой пары (Х, У) элементов подмножества С с: Т, упорядоченного введенным в структуре Т порядком, справедливо п1!с (Х, у) ~~1п1г (Х, У) ~(впр (Х, у) (впр )Х у) (39 16) Аксиоматическое определение структуры. До сих пор мы определяли структуру как некоторое множество Т, в котором для каждой пары элементов (Хь Х1) определены верхняя н нижняя грани.
Они обозначались соответственно вирт (Хь Х;) (или зпр(Хь Х )), !п1 (Х,, Хз) (или !п!(Хь Х1)). 228 Будем рассматривать теперь зцр и 1п1 как операции на множестве Т! зцр(А, В) = А т7 В, (39. 17) 1п1 (А, В) = А хх В. (39. 18) Тогда свойство множества Т быть структурой эквивалентно условию (!!7А) (17'В) (А ен Т и В ~ Т) =)~ (А т7 В ~ Т и А 7х В = — Т), (39.19) Операции Ь и Х7 можно рассматривать как отображения Т Х Т в Т, которые каждой паре (А, В) из Т К Т сопоставляют Рис. !96.
соответственно А Ь В и А ~7 В из Т; эти операции — внутренние законы композиции. Для любых элементов А, В, С ~ Т справедливы следующие соотношения: 229 Ах7В=Вх7А, (коммутативность), А т7 (В с7 С) = (А х7 В) х7 С, 4 (1 ~С) (4 А С7 А = А, (идемпотентность), А с7 (А Л В) = А, (поглощение). Об аксиоматической теории структур см. Г. Б и р к го ф структур, ИЛ, 1952.
(39.20) (39.21) (39. 22) (39. 23) (39.24) (39.25) (39. 26) (39.27) Теория Двойственность. Из формул (39.20) — (39.27) вытекает, что любая формула, относящаяся к структурам, имеет двойственную, которая получается из нее, если произвести замены: ~( Ъ, ~ )+(, т7 Л, Л г7. Например, формула (А ~ (В)Ф((А Л Х) ~((В Л Х)) (39.28) двойственна формуле (А Ъ В) ='Ь((А т7 Х) )~ (В тг Х)).
(39.29) Мвдулярные структуры. Для любых элементов А, В и С структуры Т справедливо (А ~( С) ~ (А ~7 (В Л С)) ( (((А с7 В) Л С), (39,30) Докажем теперь свойство, называелюе свойством кслабой дистрнбутивности»: А х7 (В Л С) ~( (А с7 В) Л (А ~г С), А Л (В х7 С) 3- (А Л В) ~ (А Л С). Предварительно докажем (А ( В) Ф ((А Л Х) ( (В Л Х)), (39. 31) (39. 32) где Х вЂ” произвольный элемент Т. По определению нижней грани А Л Х ~( Х, А Л Х ( А, и так как А ~( В, то А Л Х ~ (В; поэтому А Л Х= Х, АЛ Х~(В и А Л Х~(ХЛВ, так как В Л Х вЂ” наибольшая из минорант для (В, Х). Аналогично (А) В) 4>((Ах7 Х) ~) (Вх7 Х)). (39.33) В силу определения верхней грани В ~( (Вт7 С), и имеем (В ~( (В х7 С)) Ф (В Л А) ~( ((В с7 С) Л А) .
или (А Л В) ~ ((А Л (В с7 С)). из (39.32) (39. 34) (39.35) Аналогично доказывается (АЛС) ((АЛ(Сс7В)) =(А Л(В~7 С)). (39.36) ((АЛВ)с7(АЛС)) ~К(АЛ(Вс7С)), (39.37) что и требовалось доказать. В силу двойственности ((А~В)Л(Ах7С)) ~)(Ас7(ВЛС)). (39.38) Если примем А (С, то С = АСС и в силу (39.31) (Ат7(ВЛС)) ~(((А~7В) ЛС). (39.39) 230 Элемент АЛ(Вт7С) мажорирует элементы АЛВ и АЛС, следовательно, и их верхнюю грань: 0 п р ед ел е н и е. Говорят, что структура модулярна, если для любых ее трех элементов А, В, С имеем (А ~( С).=~(А ту (В гх С)) =((А!у В) г.'хС), (39.40) 3 а м еч а н ие. Если два из элементов А, В, С равны между собой, то это соотношение выполняется для любой структуры (свойство поглощения).
П р и м е р: Рассмотрим структуру на рис. 187 и проверим для нее (39.40). Легко видеть, что (/ — верхняя, а Π— нижняя грань для любой пары элементов. Как уже отмечалось, доста- точно рассмотреть тройки различных элементов, два из которых сравнимы. В каждой такой тройке присутствует либо (7, либо О, так как любые два из элементов Х, У, Л несравнимы. Для определенности рассмотрим тройки с О и проверим (А ~( (7) Ф (.А су (В ~~. (7) =- (А ту В) Тх (7) (39.
41) Так как для любого Т ТТхЮ =- Т, (39.42) то имеем (А ху В) Л (7 = А ~ В, (39.43) Вс!!7= В, т. е. Рис. !8х Л ху В = А !7 В, (39.44) (39.45) 23! и структура модулярная. Диаграмма Хассе. Для более простого изображения конечных структур используют представление ее максимальных цепей с помощью неориентированных графов, называемое диаграммой Хассе. В такой диаграмме элементы представляются точками (вершинами), и две сравнимые последовательные вершины Х и У (т. е. Х~ (У и пе существует Х Ф Х, У с Х ~(Я ~~ У) соединяются негоризонтальным ребром, причем Х располагается ниже У, Тем самым каждая максимальная цепь (в смысле структур) на диаграмме Хассе представляется цепью неориентированного графа. Рассмотрим, например, структуру на рис.
188, а). (С, Р, Е,А) и (С, В, А) — ее максимальные цепи. Изображая их, как на рис. 188,б), и стирая стрелки, получаем диаграмму Хассе (рис. 188, в). На рис. 189- — 191 приведены другие примеры диаграмм Хассе. Дистрибутивные структуры. Структура дистрибутивна, если выполнено условие А !у (В Ь С) = (А ху В) ~ (А !у С) или двойственное ему условие А Л (В Ст С) = (А Л В) СУ (А Ь С). (39.45) Например, структура, представленная диаграммой Хассе на рнс. 192, дистрибутивна. Действительно, А,Л(А,туАс)=(А,ЬА,)с7(А,ЬАи), (39,47) так как А,Л(А,ту Аз) = А,й~А,= А„ (39.
48) (А, й А,) с7 (А, Л Ас) = А» с7 А, = А,. (39.49) Теорем а. Всякая дистрибутивная структура модулярни С б) б) Рис. 188. В самом деле, для любых элементов А, В, С дистрибутивной структуры выполняется Аху(ВЛС) (Ас7В)Л(АСС), (39. 50) Если (39.51) А~С, то ХЛХ=О, Х ~у Х = У. (39.54) (39.55) 232 Асу(ВЛС) (АттВ)ЛС, (39. 52) так как А ху С = С. Т е о р е м а. Всякая подструктура дистрибутивной структуры дистрибутивна. Пусть А, В, С вЂ” любые элементы подструктуры Т' структуры Т. Тогда А с7 (В Л С) = (А ху В) й (А ту С). (39. 53) Структуры с дополнениями. Дополнение. Рассмотрим структуру Т, содержащую «нулевой» элемент О, являющийся нижней гранью Т, и «универсальный» элемент У, являющийся верхней гранью Т.
Элемент Х~ Т называют дополнением элемента Х, если (39.56) д Ряс. 193. 0 Рис. 194. Предположим противное, т. е, что В и С вЂ” два дополнения А; Л йл В = О, Л т7 В = У, Л Л С = О, Л т7С = У, (39.57) откуда Лт~В=АЛС, Ал7В=Лл7С. (39.58) Покажем, что ((ЛЛВ= ЛЛС) н (Ал7В=Ал7С)) Ф(В=С), (39,59) По предположению ЛЛВ=ЛЛС и Ал7В= — Лл7С (3960) и можно записать В = (В сл А) т7 В (поглопление), = (Л сл. В) л7 В (коммутативность с.'л), = (Л с~ С) т7 В (предположение), = (Л т7 В) сл (С Ст В) (дистрибутивность). (39,61) Аналогично С = (С сл А) л7 С (поглощение), = (А ~ел С)'7 С (коммутативность с'), = (А с~ В)лс С (предположение), = (Л т7 С)сл(В \7 С) (дистрибутивность), = (А '7 С) сл (С л7 В) (коммутативность ',7), = (Л л7 В) сл (С ~ В) (предположение).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
