8.2. Методи представлення бінарних відношень

Спеціальна природа бінарних відношень як множини впорядкованих пар дозволяє різноманітні методи їх представлення, що не обмежуються лише множинами.

a) Матриці

Щоб виписати всі елементи (пари) деякого бінарного відношення у випадку скінчених множин зручно використовувати спеціальні таблиці, що називаються матрицями. За допомогою матриці легко знайти всі елементи множини A B і виділити ті пари, що належать даному бінарному відношенню. Представимо у вигляді матриці бінарне відношення R₁ з попереднього параграфу. Перший стовпчик матриці це елементи множини А, перша строчка матриці – елементи множини В. Інші строчки і стовпчики є елементи множини A B. Підкреслені ті пари, які належать R₁ .

Це ж саме відношення можна представити дещо простіше

Для кожної одиниці формуємо пару із чисел, що стоять в її рядку і стовпцю і таким чином одержуємо бінарне відношення.

b) Діаграми

Бінарні відношення R₂ e R₃ попереднього прикладу можна представити наступними діаграмами

R2 1 2 2 3 3 4 A B

R3 1 2 2 3 3 4 A ` B

Fig. 1

c) Графи

За допомогою орієнтованих графів зручно представляти бінарні відношення з A в A. В цьому випадку говорять, що бінарне відношення визначено в A або в A A . Орієнтований граф є множина точок, що відповідають елементам множини A ( вершини ) і стрілочок, що з’єднують перші координати відношення з другими координатами (ребра). Якщо один з елементів А перебуває у відношенні з самим собою, то стрілочка переходить в дугу , що виходить і повертається в ту ж саму точку. На Рис. 2 маємо відношення R = { (a, c), (c, c ), (d, a ), (d, b ), (b, d ) } в A = { a, b, c, d }

a c

b d

Fig. 2

d) Графіки

У випадку коли множини A і B нескінчені, бінарні відношення зручно представляти графіками. Графік це множина точок координатної площини чиї абсциси x ( Dom( R ) і ординати y ( Im( R ). Графік бінарного відношення

R = {(x,y): (x (R) ( (y(R⁺₀) ( (y = x² )}

відомий як парабола.

8.3. Деякі приклади бінарних відношень

паралельність на множині прямих (x II y);

f g

a b c d e

Пари (a,b), (a,d), (a,e), (b,d), (b,e), (d,e) і їм обернені (b,a) і т. д., а також (f,g) належать бінарному відношенню x II y, (a, c) , (a,f) і інші не належать.

перпендикулярність прямих ( x ( y);

d f

e

a b c

Пари (a,d), (a,e), (b,e), (b,d), (c,f) і їм обернені належать відношенню x ( y, (e, d), (a,c) і інші – не належать.

конгруентність на множині натуральних чисел по модулю d ( N

x ( y ( mod. d) тоді і тільки тоді, коли x - y = kd , k ( Z.

Нприклад, пари всіх елементів 1, 5, 9, 13 ... належать відношенню x ( y ( mod. 4) , так як різниця між будь якими двома із цих чисел кратна 4. Те ж саме можна сказати про пари чисел 2, 6, 10, 14, ... . Не змішуйте функцію x MOD y з x ( y ( mod. d)

В загальному випадку, якщо пара ( x, y ) належить відношенню R, пишуть xRy . В розглянутих вище випадках R означає II, ( e ( відповідно.

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

A = {1, 2, 3, 4}, B = {1, 3, 5}. Перечислити елементи відношення R₁ = {(x,y): ((x,y) (A B ) ( (x < y)} і побудувати його на діаграмі A B.

A = { 2, 3, 4, 5}, B = { 3, 6, 7, 10}, R = {(x, y): ( (x, y) ( A B ) ( ( x I y )}. Перечислити елементи відношення R і побудувати його на діаграмі A B

Побудувати в координатній площині графіки бінарних відношень :

a) R = {(x, y) : y = x ^2} c) R = {(x, y) : y ( x ^2} e) R = {(x, y) : y < 3 - x}

b) R = {(x, y) : y ( sen x } d) R = {(x, y) : y ( x^3 } R = {(x, y) : y > x ^2}

4. Перечислити елементи бінарних відношень заданих орієнтованими графами:

a b R1 c d

a b R2 c d

a b R3 c d

Рис. 4