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

Введем обозначения: 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. Примеры булевых решеток

Дата добавления: 2014-01-04