1.4. Решетки.

1.4.1 Диаграммы Хассе.

Рассмотрим отношение частичного порядка: “быть подмножеством“ на множестве-степени М={1,2}.

, где

Ф={<{},{}>;<{},{1}>;<{},{2}>;<{},{1,2}>;<{1},{1}>;<{1},{1,2}>;<{2},{2}>;<{2},{1,2}>};<{1,2},{1,2}>}.

Графически данное отношение можно изобразить следующим образом:

РИС 10 Графическое изображения отношения

Отношение является рефлексивным (графически это отображается петлями), антисимметричным ( графически - однонаправленные стрелки), транзитивным ( графически - транзитивными замыканиями вида:

Для отношений частичного порядка применимы диаграммы Хассе, которые строятся на основе обыкновенной диаграммы следующим образом:

1. рефлексивные петли и транзитивные связи не изображаются;

2. большие элементы ( элементы, в которые входят стрелки) располагают выше.

Таким образом, диаграмма Хассе для вышеприведенного примера будет выглядеть следующим образом:

{ Ø }

{ 2 }

{ 1 }

РИС 11 Диаграмма Хассе

Для частично упорядоченного множества справедливо следующее:

1. Элемент аА называется наибольшим (наименьшим) , если для всех х А выполняется x a ( a x). Если наибольший (наименьший) элемент существует, то он единственный.

2. Элемент аА называется максимальным (минимальным) , если нет а множестве А элементов, больших (меньших), чем а. Максимальных (минимальных) элементов может быть несколько.

3. Пусть ВА. Элемент аА называется можарантой (минорантой) , если для всех х  В этот элемент является наибольшим (наименьшим).

4. Множество мажорант В образует верхнюю границу множества В. Множество минорант В образует нижнюю границу множества В.

5. Наименьший элемент верхней границы называется точной верхней границей , или supremum ( sup ) B. Наибольший элемент нижней границы называется точной нижней границей, или infimum (inf) B.

6. Частично упорядоченное множество, у которого для любой пары элементов определен и существует sup и inf , называется решеткой.

ПРИМЕР

Пусть дано отношение, представленное на диаграмме Хассе

РИС 12 Диаграмма Хассе

Отношение А не является решеткой, т.к. элементы 7 и 8 не имеют sup.

Отношение В является решеткой, т.к. любая пара имеет sup и inf.

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

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

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

a b=b a a b=b a

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

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

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

а а=а а а=а

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

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

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

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

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

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

ПРИМЕР

П

5

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

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

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

Дана решетка ,

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

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

ПРИМЕР

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

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

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

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

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