Множества и операции над ними. Отношение принадлежности. Множество. Элемент. Унификация объектов, страница 4

Используя св-ва операций над отношениями и св-ва степеней отн.

DÌrÞD^-1Ìr^-1ÞDÌr^-1  ref (r^-1)

r^-1ÇrÌD  ant (r^-1)

r²ÌrÞ(r²)^-1Ìr^-1Þ(r^-1)²Ìr^-1  tra (r^-1)

Þ теор: r - порядок Þ r^-1.

r^-1 называется порядком, двойственным к r

Пример: ³ и £ на R

m | n   m делит n

m делится на n

Еще один важный пример:

Отношение включения на множестве всех подмножеств (частичный порядок)

U = P({1, 2, 3}) = {Æ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

Опр. Отрезок на частично-упорядоченном множестве А с порядком r

1)  [a, b]_r = {x | (a, x)Îr, (x, b)Îr}

2)  Отрезок называется простым, если он содержит только свои границы:

[a, b]_r = {a, b}

Пример: Отношение m делит n на N    m|n:

[2, 8]₁ = {2, 4, 8}

[3, 11]₁ = Æ

[4, 8]₁ = {4, 8}

2|2, 2|8; 2|4, 4|8; 2|8, 8|8

4|4, 4|8; 4|8, 8|8

Диаграмма Хассе: граф, в котором вершины соотв. элементам частично упорядоченного множества, причем

1)  если (x, y)Îr, то y отображается выше x

2)  2 вершины соединяются между собой, если они явл. границами простого отрезка. (Петли тоже простые отрезки, но их не отображают)

ÆÌ{1}, ÆÌ{2}, ÆÌ{3}

([Æ, {1, 2}])_Ì =

={Æ, {1}, {2}, {1, 2}} –

Перевернуть, чтобы получить двойственный порядок É

¨  Упражнение

Построить диаграмму Хассе для отношения делимости чисел от 1 до 20.

Экстремальные элементы подмножеств частично упорядоченных множеств.

p - порядок. Исп. запись  xpyÛ(x, y)Îp

<A, p> - частично упорядоченное множество  XÌA

Опр.

1) аÎХ, наименьший элемент Х в смысле порядка p, если а p х "хÎХ; lt, Lt(X) – множество наименьших элементов.

2) аÎХ минимальный элемент Х в смысле порядка p, если хÎХ, хpа Þ х=а;  min, Min(X) – мн-во минимальных элементов.

3)  аÎХ называется нижней гранью Х в смысле порядка p, если а p х "хÎХ; inf

1)^* 2)^* 3)*    Двойстренные: наибольший – gt, максимальный – max, верхняя грань – sup

4)    X_*={aÎA| a px  "xÎX} – мн-во нихних граней

4)^*  X^*={aÎA| x pa  "xÎX} – мн-во верхних граней

5)    Наибольший эл. Х_* называется точной нижней гранью

5)^*   Наименьший эл. Х^* называется точной верхней гранью

¨  Упражнение

1.  Доказать, что наименьший элемент, если он существует, то он единственный.

2.  Сколько различных отношений порядка можно построить на  множестве из трех элементов. Привести все их диаграммы.

Замыкание отношений

rÌА²

Задача: наименьшим по числу добавляемых элементов (пар, стрелок) дополнить заданное отношение так, чтобы результат был

1.  Рефлексивен

2.  Симметричен

3.  Транзитивен

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

I.  - рефл. замыкание r, если

II.  - Симметричное замыкание r, если

III.  - Транзитивное замыкание r, если

Теор

1.  t=rÈD - Рефл. зам. r

2.  t=rÈr^-1 – Симм. зам. r

3.  Если |A| = n Þ t==rÈr²È…Èrⁿ – Транз. замыкание r

Док-во: