Алгебраическое представление решеток

Введем обозначения: sup(a,b)=a b, inf(a,b)=a b. Для решетки справедливы следующие свойства:

1. Коммутативный:

a b=b a a b=b a

2. Ассоциативный:

а (в с)=(а в) с а (в с)=(а в) с

3. Идемпотентности:

а а=а а а=а

4. Поглощения:

а (а в)=а а (а в)=а

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

а (в с)=(а в) (а с) а (в с)=(а в) (а с)

называется дистрибутивной решеткой.

Решетка называется ограниченной, если он имеет максимальный и минимальный элемент.

ПРИМЕР

Пусть дана решетка (рис. 13). Определить является ли решетка дистрибутивной.

РИС 13 Диаграмма Хассе решетки

Решетка не является дистрибутивной, т.к. для элементов {2;3;4} не выполняется дистрибутивный закон:

Дана решетка j=<F,M>,

где М={x½0<x<1}, Ф={<x,y>½x<y}. Эта решетка не является, так как не определен максимальный элемент (0.9999999999....) и минимальный элемент (0.0000000...1).

Обозначим в ограниченной решетке максимальный элемент 1, а минимальный элемент 0. Элемент называется дополнением элемента а в данной решетке, если и . Решетка называется с дополнением, если каждый элемент имеет хотя бы одно дополнение.

ПРИМЕР

Рассмотрим решетку, представленную на рис. 13. Найдем дополнения для каждого элемента решетки

Данная решетка является решеткой с дополнением.

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

На рис. 14 представлены дистрибутивные решетки

РИС. 14. Примеры булевых решеток