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

Решетки.

Рассмотрим отношение частичного порядка: “быть подмножеством“ на множестве-степени М={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.

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