Решетки
def. Решёткой называется частичное упорядоченное множество , в котором каждая пара элементов имеет и . Для заданных элементов элемент называется пересечением элементов (обозначается ), а называется объединением элементов (обозначается ), таким образом решётка – это алгебраическая система .
Отметим, что операции здесь понимаются как абстрактные операции алгебраической системы и отличаются от теоретико-множественных операций объединения и пересечения, определенных в алгебре множеств (в частных случаях могут с ними совпадать).
Решетка – это алгебраическая система
где - бинарные операции на множестве , - бинарное отношение частичного порядка на .
Заметим, что если в системе введены операции , то отношение можно по этим операциям восстановить следующим образом:
, а также
Наименьший (наибольший) элемент решетки, если он существует, называют
нулем (единицей). Обозначаются эти элементы соответственно через 0 и 1. В конечных решетках всегда имеются 0 и 1.
Пример 1. Любое конечное линейно упорядоченное множество является решеткой.
Пример 2. Рассмотрим , в котором , а элементы . Система образует решётку, показанную на рисунке 1.
В этой решётке a=0, e=1
Пример 3. Если | | > 1 , то ч.у.м. не является решеткой, поскольку для любых различных элементов из множества А не определены операции и по отношению .
def. Решетка называется дистрибутивной, если она подчиняется дистрибутивным законам, т.е.
.
Не все решётки являются дистрибутивными. Решётка, изображенная на рис. 1, не дистрибутивна, поскольку , тогда как .
Дистрибутивная решётка называется булевой алгеброй, если в имеется 0 и 1, и
Р
ешетка на рис. 2 является дистрибутивной.
Пример 4. Рассмотрим множество и зададим частичный порядок на следующим образом:
Система является булевой алгеброй, в которой , .
- Дм. Лекция №6 Тема: «Алгебраические структуры»
- Алгебры с одной бинарной алгебраической операцией
- Алгебры с двумя бинарными алгебраическими операциями
- Гомоморфизмы алгебр
- Булевы алгебры
- Примеры булевых алгебр
- Двоичная алгебра логики.
- Алгебра множеств
- Алгебра высказываний
- Алгебра событий
- Свойства булевой алгебры
- Алгебраические системы
- Решетки