Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 6

Докажем теорему для случая наибольшего элемента. Действительно, если т, тд — два наибольших элемента, то т < тд и тд < т, откуда в силу антнсимметричности отношения < следует т = тв. Доказательство для наименьшего элемента аналогично. Наибольший элемент упорядоченного множества М, если он существует, назовем единичным и будем обозначать 1. Наименьший элемент упорядоченного множества М, если он существует, назовем нулевым и будем обозначать О. В упорядоченном семействе множества 1 пустое множество соотпетствует нулевому элементу, 1 — единичному элементу. Элемент, покрывающий 0 в частично упорядоченном множестве М, т.

е. минимальный элемент в подмножестве множества М, полученном исключением О, называется атомом или точкой. При задании с помощью графа семейства множества М точке (атому) соответствует элемент универсума. Под изоморфизмом между двумя упорядоченными мкожествами М и М' будем понимать взаимно однозначное соответствие ц между М и М" такое, что из т; < т следует 0(т;) < 0(т ) п из Ч(т;) < я(ту) следует т; < т1. Два упорядоченнып множества, М и М', называются изоморфными тогда и только тогда, когда между ними существует изоморфнзм.

29 11.4. Решегика Гл. 1. Основы многосоргиных множеегив 28 Под отношением В, обратным В, понимают такое отношение, при котором (т;, т.) б В тогда и только тогда, когда (т, т;) б б В. Принцип двойственности. Огиношение, обратное отношению упорядоченности, также является отношением упорядоченности. Двойственным к частично упорядоченному множеству М называется частично упорядоченное множество М, определенное на том же носителе с помощью обратного отношения. На рнс. 1.10, в изображена диаграмма, являющаяся двойственной к диаграмме Хассе (рнс.

1.10, б). Часто принцип двойственности формулируют следующим образом: если теорема справедлива для частично упорядоченных множеств, то справедлива и двойственная ей теорема. Очевидно, что подмножество М' упорядоченного множества М является упорядоченным множеством, и если это упорндоченное' множество М' является линейным, то подмножество М' является цевью М' в М.

Одной из важных числовых характеристик цепи М' является ее длина 1, равная ~М'~ — 1, где [М'~ — мощность носителя линейно упорядоченного подмножества М'. Каждая цепь длины 1 изоморфна цепи целых чисел 1, 2,, ! + 1. Высотой д(т1) элемента т; упорядоченного множества М называется максимум длины (1„,„,) цепей то < тг « ... т; в М, для которых т; — наибольший элемент, то — минимальный элемент множества М.

Длиной Ы(М) упорядоченного множества М называется максимум длин цепей в М. Другими словами, длиной д(М) упорядоченного множества называется максимум высот д1(т1) его элементов д(М) = гпах й1(т,), т; б М. Наименьшей верхней гранью называется верхння грань, меньшая всякой другой верхней грани. Наибольшая нижняя грань определяется аналогично.

Очевидно, что подмножество упорядоченного множества имеет не более одной наименьшей верхней и не более одной наибольшей нижней грани. Другим важным бинарным отношением является отношение эквивалентности ( ). Бинарное отношение эквивалентности, обладающее свойствами рефлексивности, симметричности и транзитнвностн, называется отношением эквивалентности. Назовем классом эквивалентности К(т,) элемента т, множество всех элементов тн каждый из которых находится с этим элементом в отношении эквивалентности (множество эквивалентных элементов): К(т,) =(т;/ т; т,). Согласно свойству рефлексивности отношения имеем т, Е б К(т„). Из свойства транзитивности отношения эквивалентности (та ть) Й (ть "" те) Ф та те следует К(т„) э К(ть), а нз свойства симметричности— ть ть — К(те) = К(ть).

Два различных класса эквивалентности, К(т ) и К(т„), т / тю не пересекаются: К(т ) Г1 К(те) = ю, так как в противном случае онн бы совпали. Действительно, пусть найдется элемент т„принадлежащий этим классам: т, б К(ги ), К(тв); тогда согласно приведенным выше свойствам К(т ) = К(т,) = = К(т„). Иначе говоря, если найдется элемент т„принадлежащий двум классам эквивалентности, К(т ) и К(тв), то К(т ) = = К(ти„), что можно записать (используя вместо слова "найдется" обозначение 3) (3 т, Е К(т ), Е1(тв)) — + (К(т ) = К(тд)). Представление множества М в виде попарно непересекающихся подмножеств (М1) будем называть разбиением этого множества: ОМ;=М, М' г1М;, =З, 1,Мгь Таким образом, классы эквивалентности образуют разбиение множества.

Тестом распознавания отношения эквивалентности, заданного матрицей смежности, может быть приведение с помощью перестановки строк (столбцов) матрицы смежности к виду, изображенному на рис. 1.11, где около главной диагонали расположены Рнс. 1.11 подматрицы, состоящие из единиц (онн заштрихованы), остальные элементы матрицы равны нулю. Каждая заштрихованная подматрнца соответствует классу эквивалентности. 9 1.4. Решетка Используя понятие частичного упорядоченного множества, определим понятие решетки.

Решеткой называется упорядоченное множество (М, <), любые два элемента т;, т которого имеют наибольшую нижнюю грань, или пересечение т; П т, и наименьшую верхнюю грань, или объединение т; 11 ту. 6чевидно, 31 Гл.1. Основы миагаса 1вныл множестве у 1.4. Решеглка 30 что упорядоченное множество М, двойственное решетке М, является решеткой, в которой пересечение и объединение меняются местами. Упорядоченное множество, в котором любое подмножество имеет наибольшую нижнюю и наименьшую верхнюю грани, называется волной решеткой.

Очевидно, что если все цепи в решетке конечны, то всякое подмножество в решетке имеет наименьшую верхнюю и наибольшую нижнюю грани. Нзйлем в качестве упрзппекпл пересечение и объединение кекетарыд элементов решетки, апределекпсй диаграммой Хассе Н (сы. рнс. 1.10, 6): (у)О(л)=(у,т), 1ОЯ=1, (у)1Ч(а, у) =(у), (у, е)Г1(а) =я, (у, л) П (а, л) = (л), (у) О (а, е) = 1. Решетку можно определить и как алгебру А = (М, О, П), сиг- натура которой обладает следующими свойствами: коммутативности т; О гп = гв О т;, гп; П гп = гп П тб (1.2) ассоциагвиености (т; Овьу) О та = т; О (т Отд), (т; Пт ) Пть = т; П (гп Пть); (1.3) воглоецения т;Огп;Пт =т;, т;П(т;От ) =ты (14) На основе закона поглощения можно доказать свойство идем- потентности (дедекнндовости) этой алгебры: т;=т1От;П(т;От ) еетсОт1, т; = т; П (т; О т; П ту) = т1 П тс (этот результат получен Дедекиндом).

В любой алгебре, удовлетворяющей свойствам (1.2)-(1.4), т1 П т = т тогда и только тогда, когда т;Оту-— т;Огв;Пт, =гп;. При введении отношения упорядоченности <: ть > ту 1-ь ть П ту = т,, получаем определение решетки, в которой т; П т. и т1 О т явля- ются соответственно наибольшей нижней и наименьшей верхней гранями.

Свойство рефлексивности отношения <: т;<т;, вытекает из справедливости закона идемпотентности т;Пт;=гв;; свойство антисимметричности отношения < вытекает из закона коммутативности: т; < гп бс гп. < гп; <-+ т; = т. П т; = т; П т = т . Если т; > т 3с т > ть, то согласно (1.3) т; П ть = т; П (ту П ть) = (т; П ту) П ть = ту П ть = ть откуда т; > гпгй в результате доказано свойство транзитивности отношения <.

Наконец, согласно свойствам идемпотентности, коммутативности н ассоциативности операции пересечения получаем гп;П(т;Пт ) =(т;Пт)Пт =гп;Пт., и т; П т является нижней гранью для тв;, а согласно (1.2) — и для гп-. Более того, т; П гп есть наибольшая нижняя грань, так как нз гп; > ть н ту > ть вытекает согласно (1.3) (гп; П т;) П ть = т; П (т П ть) = гп; П ть = гпь. Согласно принципу двойственности т; От является наименьшей верхней гранью для т; и т . В результате проведенного доказательства получена связь между определениями решетки как частично упорядоченного множества и как алгебры с двумя операциями П и О, где Π— операция взятия наименьшей верхней грани элементов (объединения); П— операция взятия наибольшей нижней грани элементов (пересечения).

В качестве упражнение вычислим значение некоторой формулы Р, рассматривал решетку кзк алгебру. Имеем Р(а,Ь) = (а й (а О Ь)) Г1 ((а О (а й Ь)) й й(аСУЬ)) Оома ы аГ$(ай(аСУЬ)) мама = (айа) ОООа = аГУОЦа = ама ю а, Прп упрошеппн Р(а, Ь) были пспальзавзны свойстве (1.4), (1.2) и пдеыпа.

тептнасть. Здесь и ниже О и 1 в решетке будем называть структурными нулем и единицей; при этом (Чтб) (О П т; сс О, О О т; = т;, тг П 1 = т;, т1 О 1 = 1). Определим в решетке свойство дистрибутивности. Подрешеткой А решетки А называется подмножество решетки А, которое вместе с каждой парой элементов т;, т из А содержит также тб О т. н ту П т . Интервалом Ю, определенным элементами та и тд в решетке А, называется подрешетка А' решетки А с наибольшим элементом тл и наименьшим злементом т: У = (та, тд] = (ту б А / та < т1 < тл) ° В решетке А со структурными нулем и единицей два элемента, гп„и тд, называются дополнительными, если таПтл=О~ таОтз=1.

зз Гл. 1. Основы мнегосореаные множеств З2 $1 4 Решетка Элемент, дополнительный к т (т), называется также дополнением элемента т в решетке А. Два элемента, обладающие общим дополнением в решетке А, называются свлэанными в А. Важным классом решеток являются дистрибутивные решетки. Решетка А называется дистрибутивной, если она удовлетворяет следующим тождествам: (т;0ту)Пть=т;Пть0т Пть, теП (т10т ) = пььПт;0 теПт для всех т;, т, ть б М. Согласно свойству коммутативностн пересечения для определения дистрибутивной решетки достаточно выполнения одного из этих тождеств. Критерий дистрибутивности решетки.