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

Определение 1. Пусть   AB бинарное отношение между элементами множеств A и B. Обратным бинарным отношением для бинарного отношения  называется бинарное отношение ^1 между элементами множеств B и A, которое состоит из всех пар вида (b,a), где (a,b): ^1 = {(b,a)(a,b)}.

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

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

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

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

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

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

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

X  A, X  B,₁ =   (XY).

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

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

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

У



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

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

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

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

2. 3. Отношение эквивалентности

Определение 1. Бинарное отношение  на множестве A называется рефлексивным, если (a, a)   для любого aA.

Определение 2. Бинарное отношение  на множестве A называется антирефлексивным, если (a, a)   для любого aA.

Определение 3. Бинарное отношение  на множестве A называется симметричным, если (a, b)  , то (b, a)   для любых a, bA.

Определение 4. Бинарное отношение  на множестве A называется антисимметричным, если (a, b)   и (b, a)  , то a = b для любых a, bA.

Определение 5. Бинарное отношение  на множестве A называется транзитивным, если (a, b)   и (b, c)  , то (a, c)   для любых a, b, c  A.

Определение 6. Бинарное отношение  на множестве A называется полным или линейным , если a  b, то (a, b)   или (b, a)   для любых a, b A.

Определение 7. Бинарное отношение I = {(a,a) aA } на множестве A называется тождественным.

Теорема 8.1. Пусть  бинарное отношение на множестве A. Тогда имеют место равносильности:

1.  - рефлексивно  I ;

2.  - симметрично   =  ^-1;

3.  - транзитивно  _   ;

4.  - антисимметрично    ^-1 ;

5.  - антирефлексивно    I =;

6.  - полно   I ^-1=U.