Алгебра отношений. Обратное бинарное отношение. Композиция бинарных отношений.

 

Определение 1. Пусть r Í A´B бинарное отношение между элементами множеств A и B. Обратным бинарным отношением для бинарного отношения r называется бинарное отношение r ^{- 1} между элементами множеств B и A , которое состоит из всех пар вида (b , a), где (a , b)Îr: r^-1 = {(b , a)½(a , b)Îr}.

r-1

2

44

3

5

6

A

4

6

2

B

Рис. 4

Например, обратное бинарное отношение к бинарному отношению из примера 5.1 равно r^-1 = {(4, 2), (6, 3)}, а обратное бинарное отношение к бинарному отношению из примера 5.2 изображено в виде графа на рис. 3 (по сравнению с графом на рис. 1 все стрелки направлены в противоположную сторону).

Определение 2. Пусть r - бинарное отношение между элементами множеств A и B , s - бинарное отношение между элементами множеств C и D . Бинарные отношения (A, B, r)и (С, D, s) называются равными, если равны множества A = C , B = D , r = s. Обозначается r = s.

Определение 3. Композицией двух бинарных отношения (A, B, r)и (B, C, s) называется бинарное отношение между множествами A и C , обозначаемое , которое состоит из всех пар вида (a , c), для которых существует такой элемент bÎ B , что (a , b) Îr и (b , c) Îs.

b

c

a

B

1

34

2

4

5

A

Рис. 5

a

g4

b

d

C

1

34

2

4

5

A

a

g4

b

d

C

r°s

r

s

Пример 1. Пусть A = {1, 2, 3, 4, 5}, B = {a, b, c}, C = {a, b , g, d}, r  = {(1, a), (1, c), (2, b), (4, c), (5, c)}, s  = {( a, a), (a, b), (c, g), (b, d)}. Тогда  = {(1, a), (1, b), (1, g), (2, d), (4, g), (5, g)}. При представлении этих отображений в виде графов их композиция проиллюстрирована на рис. 3.

Теорема 1. Операция композиции обладает свойством ассоциативности, т.е.  для любых трех бинарных отношения (A, B, r), (B, C, s) и (С, В, t) .

Доказательство. ТУ.

Определение 3. Бинарным отношение r₁Í X´Y называется сужением бинарного отношения r Í A´B на множества X и Y, если

X Í A , X Í B , r₁ = r Ç (X´Y).

Определение 4. Бинарным отношением на множестве A называется любое подмножество   r Í A´A.

При изображении бинарного отношения r на конечном множестве A в виде графа на плоскости изображается только одно множество A. Каждой паре (a , b)Î r соответствует ребро, идущее из точки a в точку b . Пара (a , a)Î r петля изображаться в виде петли, идущее из a в a , с фиксированным направлением обхода. Если пары (a , b), (b , a)Î r, то принято изображать их одним ребром с двумя стрелками (такое ребро называется неориентированным).

Пример 1. A = {1, 2, 3, 4, 5, 6, 7}, r  = {(a, b)½a, b ÎA, a - b делится на 3}. Граф отношения r изображен на рис. 1.9.

r

Упражнение. Перечислить все бинарные отношения между множествами A = {1, 2, 3}, B = {4, 5}.

1

2

3

4

5

6

7

Рис. 6

A

5.2. A = {1, 2, 3, 4, 5, 6}, B = {1, 2, 3, 4}, r  = {(a, b)½a, b ÎA, a + b четное число}. Записать его всеми способами. Найти D(r), E(r), r ^-1.

5.3. Доказать теорему 1.

Найти сужение указанного выше бинарного отношения r на множества X = {1, 2, 3, 4}, Y = {1, 2, 3}.