8.4. Обернені відношення

Означення 3. Будь яке відношення з A в B має обернене відношення R^-1 з B в A , що визначається як

R ^-1 = {(b, a)( B A : (a, b) ( R }

Другими словами, обернене відношення R^-1 складається з пар, для яких пари, одержані переміною порядку елементів, належать R.

Приклади

1. Нехай A = {1, 2, 3} і B = {a, b}. Тоді, R = {(1, a), (1, b), (3, a)} є відношення A в B. Обернене відношення R^-1 = {(a, 1), (b, 1), (a, 3)}.

2. Нехай W = {a, b, c}. R = {(a, b), (a, c), (c, c), (c, b)} є бінарне відношення в W. Обернене відношення R^-1 = {(b, a), (c, a), (c, c), (b, c)}.

3. R = {(1,5), (4,5), (1, 4), (4, 6), (3, 7), (7, 6)}. Dom R = {1, 3, 4, 7}; Im R = {4, 5, 6, 7};

R^-1 = {(5, 1), (5, 4), (4, 1), (6, 4), (7,3), (6, 7)}.

4. R = {(x, y): (x, y ( N) ( ( 2x + y = 10)}.

R = {(1, 8), (2, 6), (3, 4), (4, 2)}; R^-1 = {(8, 1), (6, 2), (4, 3), (2, 4)}

8.5. Композиція (добуток) відношень

Означення 4. Якщо x R₁ y є бінарне відношення з A в B, y R₂ z є бінарне відношення з B в C, тоді x R z є бінарне відношення з A в C що називається композицією або добутком відношень

R =R₂ ( R₁

Зверніть увагу, спершу виконується відношення R₁ , а потім над його образом виконується відношення R₂ , ось чому в такому порядку слідують відношення в R.

Приклади.

1. Нехай A = {1, 2, 3} e R = {(1,1), (2, 3), (3, 1)}, T = { (1, 2), (2, 2), (3, 2)}.

Тоді, R (T = {(1,3), (2, 3), (3, 3)}, T ( R = {(1, 2), (2, 3), (3, 2)}.

Як бачимо, R (T ( T ( R.

2. R ( R^-1 = R^-1 ( R = {(x, x): x ( Dom(R)}, ou R ( R^-1 = R^-1 ( R = xRx.

Відношення i_A = {(x, x): x ( A } або i_A = xRx називається тотожністю в A. Ясно, що

i_A ( R = R ( i_A = R.

Вправи на закріплення

1. Нехай

E = {(p, q ) ( P P : p є ворогом q } і

F = {(p, q ) ( P P : p є другом q }

де P є множина всіх людей. Виразити в термінах бінарних відношень “ ворог мого ворога є мій друг”.

2. Нехай A = { 1, ,2, 3 }, B = { 4, 5, 6 }, R ( A B ) = {(1, 4), (1, 5), (2, 5), (3, 6)}, S ( B B ) = = { (4, 5), (4, 6), (5, 4), (6, 6) }. Знайти:

a) S ( R ;

b) S ( S ;

c) S^-1 ( R ;

d) R^-1 ( S.

3. Нехай R e S є бінарні відношення з A в B. Чи істинні наступні пропозиції:

a) R ( Dom ( R ) Im ( R );

b) Se R ( S, entao R^-1 ( S^-1 ;

c) ( R ( S )^-1 = R^-1 ( S^-1 .?

Обгрунтувати відповідь доведенням або контр прикладом.

4. Нехай R бінарне відношення з A в B e S, T є бінарні відношення з B в C. Чи істинні наступні пропозиції:

a) Se S ( T , entao S ( R ( T ( R ; c) ( S ( T ) ( R = ( S ( R ) ( ( T ( R );

b) ( S ( T ) ( R ( ( S ( R ) ( ( T ( R ); d) ( S ( T ) ( R = ( S ( R ) ( ( T ( R );

Обґрунтувати відповідь доведенням або контр прикладом.

8.6. Рефлексивні відношення

Означення 5. Бінарне відношення в А є рефлексивним, якщо xRx для всіх x ( A .

В термінах логіки і теорії множин

( x ( A ( x R x ) ou ( x ( A ((x, x ) ( R ).

Приклади.

1. Нехай V = {1, 2, 3, 4} і R = {(1, 1), (2, 4), (3, 3), (4, 1), (4, 4)}. R не є рефлексивним, тому що пара (2, 2) ( R.

2. Нехай А множина трикутників. Відношення R визначене предикатом “ x подібний y “ є рефлексивним, тому що кожний трикутник подібний самому собі.

3. Відношення “включення” визначене на множині множин є рефлексивним, тому що кожна множина включає саму себе.

8.7. Симетричні відношення

Означення 6. Бінарне відношення в A є симетричним, якщо (x, y) ( R імпліка (y, x) ( R.

Приклади.

Нехай А множина трикутників. Відношення R визначене предикатом “ x подібний y “ є симетричним, тому що коли трикутник a подібний трикутнику b, то b також подібний a.

Нехай R бінарне відношення у множині натуральних чисел визначене як x I y (x ділиться на y). Це відношення не симетричне, тому що із 4 ділиться на 2 (4 | 2) не слідує, що 2 ділиться на 4 (2 | 4). Іншими словами,

(4, 2) ( R, але (2, 4) ( R.

Перевірте, чи відношення Larger(x,y), Smaller(x,y), Right(x,y), Left(x,y), Front(x,y), Back(x,y) є симетричними в Bolanda.

Nota. Так як (a, b) ( R імпліка (b, a) ( R^-1 , то R є симетричним тоді і тільки тоді, коли R = R^-1.