Решетки

def. Решёткой называется частичное упорядоченное множество , в котором каждая пара элементов имеет и . Для заданных элементов элемент называется пересечением элементов (обозначается ), а называется объединением элементов (обозначается ), таким образом решётка – это алгебраическая система .

Отметим, что операции здесь понимаются как абстрактные операции алгебраической системы и отличаются от теоретико-множественных операций объединения и пересечения, определенных в алгебре множеств (в частных случаях могут с ними совпадать).

Решетка – это алгебраическая система

где - бинарные операции на множестве , - бинарное отношение частичного порядка на .

Заметим, что если в системе введены операции , то отношение можно по этим операциям восстановить следующим образом:

, а также

Наименьший (наибольший) элемент решетки, если он существует, называют

нулем (единицей). Обозначаются эти элементы соответственно через 0 и 1. В конечных решетках всегда имеются 0 и 1.

Пример 1. Любое конечное линейно упорядоченное множество является решеткой.

Пример 2. Рассмотрим , в котором , а элементы . Система образует решётку, показанную на рисунке 1.

В этой решётке a=0, e=1

Пример 3. Если | | > 1 , то ч.у.м. не является решеткой, поскольку для любых различных элементов из множества А не определены операции и по отношению .

def. Решетка называется дистрибутивной, если она подчиняется дистрибутивным законам, т.е.

.

Не все решётки являются дистрибутивными. Решётка, изображенная на рис. 1, не дистрибутивна, поскольку , тогда как .

Дистрибутивная решётка называется булевой алгеброй, если в имеется 0 и 1, и

Р

Пример 4. Рассмотрим множество и зададим частичный порядок на следующим образом:

Система является булевой алгеброй, в которой , .