Бінарні відношення. Способи задавання перерізів

Відношення між елементами двох множин, тобто бінарні відношення, встановлюють відповідність елементів однієї множини X елементам іншої множини Y.

Таке відношення задається деякою сукупністю впорядкованих пар (x,y), які є елементами множини X´Y. Але це зовсім не означає, що потрібно перелічувати всі такі пари. Часто відношення задається деяким символом, виразом у словесній або символьній формі.

Якщо А – відношення, то відповідність xAy можна записати у вигляді (x,y)ÎA, де АÌX´Y.

Елемент x називається першою координатою, а елемент y – другою координатою впорядкованої пари.

Області визначення і значень. Множина перших координат x є областю визначення (лівою областю) D_o(A), а множина других координат – областю значень (правою областю) D_з(A) відношення А. Якщо x ÎX і yÎY, то D_o(A)ÌX та D_з(A)Ì Y. У таких випадках говорять, що A є відношенням від X до Y. Його називають також відповідністю і позначають X®Y. Якщо Y=X, то будь-яке відношення xAy є підмножиною множини X´Y та називається відношенням у X.

Приклад 1: X={2,3};

Y={3,4,5,6};

X´Y={(2,3),(2,4),(2,5),(2,6),(3,3),(3,4),(3,5),(3,6)};

відношення “бути подільним” – A={(2,4),(2,6),(3,3),(3,6)};

відношення “=” – B={(3,3)};

відношення “>” – Æ;

D_o(A)={2,3}=X;

D_з(A)= {3,4,6}ÌY.

Якщо область відношення збігається з деякою множиною X, то говорять, що відношення визначене на X.

Заслуговують уваги три випадки відношень у X:

· Повне (універсальне) відношення P= X´ X, яке має місце для кожної пари (x₁, x₂) елементів із X. Наприклад,відношення “працювати в одному відділі” на множині відношень співробітників цого відділу.

· Тотожне (діагональне) відношення E, рівнозначне x = x, наприклад, рівність на множині дійсних чисел.

· Пусте відношення, котре не задовольняє жодна пара елементів із X, наприклад, відношення “бути братом” на множині жінок.

Бінарні відношення можна задати наступними способами:

1. За допомогою списку, елементами якого є пари, з котрих складається відношення.

2. За допомогою фактор-множини.

Переріз. Розглянемо відношення AÌX´Y; якщо x_iÎX, то переріз по x_i відношення А, позначений А(x_i), є множиною yÎY таких, що (x_i, y) ÎА.

Множина всіх перерізів відношення А називається фактор-множиною Y по відношенню А і позначається Y/A. Воно повністю визначає відношення А.

Приклад

X={ x₁, x₂, x₃, x₄, x₅};

Y= { y₁, y₂, y₃, y₄};

A= {(x₁, y₁), (x₁, y₃), (x₂, y₁), (x₂, y₃), (x₂, y₄), (x₃, y₁), (x₃, y₂), (x₃, y₄), (x₄, y₃), (x₅, y₂), (x₅, y₄)}.

Якщо запишемо під кожним елементом із X відповідний переріз відношення А, то елементи другого рядка утворять фактор-множину Y/A:

x₁ x₂ x₃ x₄ x₅

{y₁,y₃} { y₁,y_3, y₄} { y₁,y_2, y₄} {y₃} { y_2, y₄}.

Кінцеве відношення представляється за допомогою фактор-множини. Об’єднання перерізів за елементами деякої підмножини BÌX є перерізом A(B) цієї підмножини, тобто A(B)= Так, A(x_2, x₃)= A(x₂)È A(x₃)={ y₁, y_2, y_3, y₄}.

3. За допомогою матриць. Цей спосіб – матричний – оснований на представленні відношень за допомогою прямокутної таблиці (матриці). Її стовпці відповідають першим координатам, а рядки – другим координатам. На перетині i -го стовпця та j -го рядка ставиться одиниця, якщо виконується відношення x_iAy_j і 0, якщо це відношення не виконується. Така матриця містить усю інформацію про відношення А. Наприклад,

	x1	x2	x3	x4	x5
y1	1	1	1
y2			1		1
y3	1	1		1
y4		1	1		1

 

4. За допомогою графів. Вершини графа відповідають елементам множини X та Y, а дуга, направлена з вершини x_i до y_i, означає, що x_i А y_i (рис. 4.2.1).

Рис. 4.2.1. Граф відношення від X до Y (біграф)

Приклад: задане відношення (рис. 4.2.2)

А= {(x₁, x₂), (x₁, x₅), (x₂, x₁), (x₂, x₃), (x₃, x₁), (x₃, x₄), (x₄, x₃), (x₄, x₅), (x₅, x₅), (x₆, x₂)}.

Рис. 4.2.2. Граф відношень у множині X

Зобразимо графи повного, тотожного та пустого відношення (рис. 5.2.3).

Рис. 4.2.3. Граф повного, пустого й тотожного відношень

Симетричне відношення. Оскільки відношення – це множини, то над ними виконуються всі теоретико-множинні операції. Крім того, для відношення визначаються специфічні для відношення операції: обернення (симетризація) та композиція.

Відношення, симетричне (обернене) деякому відношенню AÌX´Y, позначається через А^-1 і являє собою підмножину множини Y´ X, утворену парами (y, x) Î Y´ X, для якого (x, y) ÎА. Перехід від А до А^-1 здійснюється взаємною перестановкою координат кожної впорядкованої пари, наприклад:

обернене відношення для “ x є дільником y” буде “ y ділиться на x”;

відношення A={(2,4),(2,6),(3,3),(3,6)}, A^-1={(4, 2),(6, 2),(3,3),(6, 3)}.

При переході від А до А^-1 область визначення стає областю значень і навпаки. Матрицю оберненого відношення одержуємо траснпонуванням вихідної матриці. Граф оберненого відношення знаходимо з вихідного графа заміною направлень усіх дуг на протилежні.

Композиція відношень. Нехай дано три множини X, Y, Z ідва відношення AÌX´Y та BÌY´ Z.

Композицією відношень A й B є відношення С, що складається з усіх тих пар (x,z) ÌX´ Z для яких існує такий yÎY, що (x, y) ÎА та (y,z) ÎB.

Як записати композицію відношень A та B? Якщо виходити із співвідношень xAy і yB z, то xCz=xABz, але для зручності прийнято записувати С=АВ або С=А×В.

Для композиції відношень справедливим є асоціативний закон, тобто D(BA)=(DB)A=DBA. Але не комутативний закон ВА¹АВ, наприклад:

X={ x₁, x₂, x₃, x₄, x₅};

Y= { y₁, y₂, y₃, y₄};

A= {(x₁, y₁), (x₁, y₃), (x₂, y₁), (x₂, y₃), (x₂, y₄), (x₃, y₁), (x₃, y₂), (x₃, y₄), (x₄, y₃), (x₅, y₂), (x₅, y₄)};

В= {(y₁, z₂), (y₂, z₁), (y₂, z₂), (y₃, z₃), (y₁, z₂), (y₄, z₃)}.

Тоді С={(x₁, z₂), (x₁, z₃), (x₂, z₂), (x₂, z₃), (x₃, z₁), (x₃, z₂),(x₃, z₃), (x₄, z₃), (x₅, z₁), (x₅, z₂), (x₅, z₃)}.

Переріз С(x₃)={ z_1, z_2, z₃};

B(A(x₃))=B({y_1, y_2, y₄})={z₁}È{ z_1, z₂}È{ z₃}={ z_1, z_2, z₃}.

Композиція відношень AÌX´Y та BÌY´ Z наочно представляється у вигляді графів. Перш за все необхідно до графа відношення А добудувати граф відношення В.

Граф відношення С=ВА одержимо, виключивши вершини, які відповідають елементам множини Y. При виключенні вершини y_i кожний шлях, що проходить через неї від вершин x до вершин z, замінюється однією дугою з тим же направленням.

Паралельні гілки з однаковими направленнями відповідають однаковим парам у С і розглядаються як одна гілка (рис. 4.2.4).

Рис. 4.2.4. Побудова графа композиції відношень xAy та yBz

Аналогічно можна одержати матрицю композиції С=ВА як добуток матриць відношень В й А (у порядку їх слідування), яке виконується за звичайним правилом множення прямокутних матриць із наступною заміною відмінного від нуля елемента результуючої матриці. Наприклад:

	y1	y2	y3	y4
z1		1					x1	x2	x3	x4	x5
z2	1	1				y1	1	1	1
z3			1	1		y2			1		1			x1	x2	x3	x4	x5
					*	y3	1	1		1		=	z1			1		1
						y4		1	1		1		z2	1	1	2		1
													z3	1	2	1	1	1