Решетки - это частично-упорядоченные множества (ЧУМ, множества с определенным на нем частичным порядком), отношения порядка на которых, удовлетворяют ряду дополнительных требований.
Диаграммы Хассе используются для того, чтобы за счет принятых по умолчанию соглашений облегчить графическое представление частично-упорядоченных множеств.
Пример изображения частичного порядка (устанавливаемого отношением включения) для множества {Æ, {0}, {1}, {0,1}}
По умолчанию на диаграмме Хассе:
«Стрелки» направлены снизу вверх.
Не отображается рефлексивность.
Не отображаются транзитивные замыкания.
Понятие решетки:
Пусть рассматриваемые далее множества А и В - чум.
Наибольшим (наименьшим) элементом аÎА называется элемент а, если а ³ (£) х, где х Î А.
Теорема: Если в множестве А существует наибольший элемент, то он единственный.
Доказательство: Предположим, что существуют два наибольших элемента а1 и а 2, тогда:
а1 ³ а2 }
а2 ³ а1 } а1 = а2
Максимальным (минимальным) элементом множества А называется элемент аÎА, когда неверно, что а £ (³)х, где х Î А.
|
|
Мажорантой (минорантой) множества В (такого что Æ Ì В Í А) является
элемент а Î А, такой что элемент а является наибольшим (наименьшим) элементом для множества В.
Множество мажорант (минорант) множества В образует верхнюю (нижнюю) грань множества В.
Наименьший элемент верхней грани называется точной верхней гранью или Supremum (Sup).
Наибольший элемент нижней грани называется точной нижней гранью или Infimum (Inf).
Частично-упорядоченное множество, в котором любая пара элементов имеет Sup и Inf называется решеткой.