Пусть рассматриваемые далее множества А и В - чум.
Наибольшим (наименьшим) элементом аÎА называется элемент а, если а ³ (£) х, где х Î А.
Теорема: Если в множестве А существует наибольший элемент, то он единственный.
Доказательство: Предположим, что существуют два наибольших элемента а1 и а 2, тогда :
а1 = а2;
}
а1 ³ а2
а2 ³ а1
Максимальным (минимальным) элементом множества А называется элемент аÎА, когда неверно, что а £ (³)х, где х Î А.
Мажорантой (минорантой)множества В (такого что Æ Ì В Í А) является
элемент а Î А, такой что элемент а является наибольшим (наименьшим) элементом для множества В.
Множество мажорант (минорант) множества В образует верхнюю (нижнюю) грань множества В.
Наименьший элемент верхней грани называется точной верхней гранью или Supremum (Sup).
Наибольший элемент нижней грани называется точной нижней гранью или Infimum (Inf).
Частично-упорядоченное множество, в котором любая пара элементов имеет Sup и Inf называется решеткой.
Примеры решеток.
Введем обозначения Sup(a, b) = a È b, Inf(a, b) = a Ç b ,
Будем считать традиционно используемые здесь значки È, Ç не имеющими никакого отношения к теоретико-множественным операциям объединения и пересечения.
Если выполняются законы :
1. a È b = b È a 1’. a Ç b = b Ç a
2. (a È b) È c = (b È c) Èa = a È b È c 2’. (a Ç b) Ç c = (b Ç c) Ç a = a Ç b Ç c
3. a È (a Ç b) = a 3’. а Ç (b È a) = a
4. a È a = a 4’. а Ç a = a
то имеет место решетка.
То есть решетка можно определить как алгебру Z = < L, Ç, È > , для операций которой выполняются вышеперечисленные законы.
Решетка называется дистрибутивной, если дополнительно к вышеперечисленным выполняется дистрибутивный закон:
5. a È b Ç c = (a È b) Ç(a È c) 5'. а Ç (b È c) = a Ç b È a Ç c
Пример :Недистрибутивная решетка:
a È b Ç e = (a È b) Ç (a È e)
а È e = a Ç a
a = a
b È c Ç d = b Ç c È b Ç d
b È e = a È a
b ¹ a недистрибутивность
Эта решетка недистрибутивная.
Решетка называется ограниченной, если она имеет максимальный и минимальный элементы.
Например, если взять отрезок действительной оси от 0 до 1 (вместе с конечными точками) и отношение "меньше", то это будет ограниченная решетка. Убрав крайние точки, получаем неограниченную решетку.
1 1
- неограниченная решетка - ограниченная
(без 1 и 0)
0 0
Обычно минимальный элемент решетки обозначают как 0, а максимальный как 1.
ā - дополнение а, если а È ā = 1 и а Ç ā =0
Решетка является решеткой с дополнением, если каждый элемент имеет хотя бы одно дополнение.
Ограниченная дистрибутивная решетка с дополнением является булевой.