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

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

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

ab=ba ab=ba

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. Примеры булевых решеток