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

Решетки.

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

j=<F,M>, где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИМЕР

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

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

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

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