Материал: discrete_mathematics

Рис. 2.3

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

Аналогічно відповідностям для відношень можна означити поняття оберненого відношення та композиції відношень.

Відношення R–1 називають оберненим до відношення R, якщо bR–1a тоді й тільки тоді, коли aRb. Очевидно, що (R–1)–1 = R.

Наприклад, для відношення більше або дорівнює оберненим є відношення менше або дорівнює, для відношення ділиться на –

відношення є дільником.

Композицією відношень R1 і R2 на множині M (позначають R1 ° R2) називають таке відношення R на M, що aRb тоді й тільки тоді, коли існує елемент c M, для якого виконується aR1c і cR2b.

Наприклад, композицією відношень R1 – є сином і R2 – є братом на множині чоловіків є відношення R1 ° R2 – є небожем.

Для відношення R на множині M через R(k) позначимо відношення R ° R °…° R (k разів). Вважаємо, що R(0) = iM і R(1) = R.

Приклад 2.26.

1. На множині людей P означено такі відношення:

(а) Нехай (x, y) F° F, тоді z: (x, z) F (z, y) F, тобто x –

батько z і z – батько y. Отже, F° F – це множина таких (x, y), що x є батьком батька y (або x – дідусь y через батька).

(б) Нехай (x, y) F–1 ° D, тоді z: (x, z) F–1 (z, y) D, тобто z

– батько x і z – донька y, що неможливо. Отже, F–1 ° D – порожня множина.

2. Довести, що для довільних відношень R1 і R2 виконується

(R1 ° R2)–1 = R2–1 ° R1–1.

(x, y)(R1°R2)–1 (y, x) R1°R2 z: (y, z) R1 (z, x) R2 z: (x, z) R2–1 (z, y) R1–1 (x, y) R2–1°R1–1.

3. Для яких відношень виконується рівність R –1 = R ?

Для жодних. Оскільки, припустивши існування такого відношення R, матимемо: якщо (x, x) R, то (x, x) R–1 та (x, x) R;

якщо ж (x, x) R, то знову дійдемо суперечності, тому що отри-

маємо (x, x) R–1 та (x, x) R.

4. Визначити, для яких відношень R на множині M виконується співвідношення:

(а) iM°R = R; (б) iM°R = iM; (в) iM R°R–1.

(а) Для всіх R. Якщо (x, y) iM°R, то (x, x) iM і (x, y) R, отже, (x, y) R. Якщо ж (x, y) R, то, ураховуючи (x, x) iM, з означення композиції відношень матимемо (x, y) iM°R.

(б) Тільки для R = iM (див. (а)).

(в) Для таких і тільки таких, що Pr1R = M. Нехай Pr1R = M,

тоді для довільного елемента x M послідовно маємо: (x, x) iM

та xPr1R y: (x, y) R (y, x) R –1 (x, x) R°R –1. Доведемо обернене твердження. Візьмемо x M, тоді

(x, x) iM (x, x) R°R –1 (y M: (x, y) R (y, x) R –1)y M: (x, y) R.

Отже, xPr1R і доведено включення M Pr1R. Обернене включення випливає із означення проекції відношення.

5. Довести, що коли R1 R2, тоді для довільного відношення

Q виконується Q ° R1 Q ° R2.

Нехай (x, y) Q°R1, тоді існує z такий, що (x, z) Q і (z, y) R1. Ураховуючи умову, матимемо (x, z) Q і (z, y) R2, отже, за озна-

ченням композиції відношень отримаємо (x, y) Q°R2. ◄

118

Наведемо властивості, за якими класифікують відношення. Нехай R – відношення на множині M.

1.Відношення R називається рефлексивним, якщо для всіх a M виконується aRa.

Очевидно, що відношення R1, R2, R4, R5, R7 – рефлексивні.

2.Відношення R називають антирефлексивним (іррефлек-

сивним), якщо для жодного a M не виконується aRa. Відношення більше, менше, є сином антирефлексивні, а від-

ношення R6 не є ні рефлексивним, ні антирефлексивним.

Усі елементи головної діагоналі матриці C для рефлексивного відношення на скінченній множині M дорівнюють 1, а для антирефлексивного відношення вони дорівнюють 0.

3.Відношення R називають симетричним, якщо для всіх a, b M таких, що aRb, маємо bRa.

4.Відношення R називають антисиметричним, якщо для всіх

a, b M таких, що aRb і bRa, маємо a = b.

Наприклад, відношення R3, R4, R5, R6, R8 – симетричні, а відношення R1, R2, R7 – антисиметричні.

Неважко переконатися, що відношення R симетричне тоді й тільки тоді, коли R = R–1.

5. Відношення R називають транзитивним, якщо із співвідношень aRb і bR c випливає aRc.

Наприклад, відношення R1, R2, R4, R5, R7, R8, R9 транзитивні, а відношення R3, R6 не транзитивні.

Неважко переконатися, що відношення R транзитивне тоді й тільки тоді, коли R ° R R (критерій транзитивності відно шення).

Зауважимо, що коли відношення R має будь-яку з наведених вище властивостей, тоді обернене відношення R–1 також має ту саму властивість. Отже, операція обернення зберігає всі п'ять властивостей відношень.

Відношення R на множині M називають толерантним (від ношенням толерантності, або просто толерантністю), якщо воно рефлексивне й симетричне.

Для довільного відношення R означимо нову операцію. Відношення R+ називають транзитивним замиканням відношення R на M, якщо a R+b, a, b M, тоді й тільки тоді, коли в множині M існує така послідовність елементів a1, a2, …, ak, що

119

a1 = a, ak = b і a1 R a2, a2 R a3, …, ak – 1 R ak.

Зокрема, k може дорівнювати 2; отже, якщо aRb, то a R+b. Тому R R+.

Іншим рівносильним означенням цього поняття є таке: тран зитивним замиканням відношення R на множині M називають найменше транзитивне відношення на M, що включає R.

Наприклад, нехай M – множина точок на площині й aRb, a, b M, якщо точки a та b з'єднані відрізком. Тоді cR+d, коли існує ламана лінія, що з'єднує точки c і d, c, d M.

Можна довести, що відношення R транзитивне тоді й тільки тоді, коли R+ = R. Крім того, справджується рівність

R+ = R(1) R(2) … R(k) … .

Відношення R+ iM позначають через R* і називають рефлек сивнимтранзитивнимзамиканням відношення R на множині M.

Приклад 2.27.

1.Навести приклад двох антирефлексивних відношень R1 і R2 на множині M = {1, 2, 3}, композиція R1°R2 яких не буде антирефлексивним відношенням. Наприклад,

R1 = {(1, 2)}, R2 = {(2, 1)}.

2.Довести, що композиція R1 ° R2 симетричних відношень R1 і R2 є симетричним відношенням тоді й тільки тоді, коли

R1 ° R2 = R2 ° R1.

Нехай для симетричних відношень R1 і R2 їхня композиція R1°R2 є симетричним відношенням. Розглянемо довільний еле-

мент (x, y) R1°R2, тоді (y, x) R1°R2. Звідси матимемо таку послідовність рівносильних тверджень:

(y, x) R1°R2 (z: (y, z) R1 (z, x) R2) (z: (z, y) R1 (x, z) R2) (x, y) R2°R1.

Отже, доведено рівність R1°R2 = R2°R1.

Навпаки, припустимо, що для симетричних відношень R1 і R2 виконується R1°R2 = R2°R1. Розглянемо довільний елемент

(x, y) R1°R2, тоді матимемо:

(x, y) R2°R1 (z: (x, z) R2 (z, y) R1) (z: (z, x) R2 (y, z) R1) (y, x) R1°R2.

Симетричність R1°R2 доведено.

120

3.Довести, що відношення R на множині M транзитивне тоді

йтільки тоді, коли R ° R R.

Припустимо, що R – транзитивне відношення, (x, y) R°R, тоді існує z такий, що (x, z) R і (z, y) R, отже, (x, y) R (за властивістю транзитивності R). Навпаки, нехай виконується включення R°R R. Розглянемо елементи (x, y) R і (y, z) R, тоді (x, z) R°R і з умови отримаємо (x, z) R. Отже, R – транзитивне відношення.

4.Довести, що композиція R1 ° R2 транзитивних відношень R1

іR2 є транзитивним відношенням, якщо R1 ° R2 = R2 ° R1.

Нехай для транзитивних відношень R1 і R2 виконується рів-

ність R1°R2 = R2°R1. Розглянемо елементи (x, y) R1°R2 і

(y, z) R1°R2. Тоді

(x, z)(R1°R2)°(R1°R2).

Використовуючи асоціативність операції композиції (для будьяких відношень R1, R2, R3 виконується (R1°R2)°R3 = R1°(R2°R3)), умову даної задачі, результат попередньої, а також приклад

2.25(5), отримаємо:

(R1°R2)°(R1°R2) = R1°(R2°R1)°R2 = R1°(R1°R2)°R2 =

=(R1°R1)°(R2°R2) R1°R2. Отже, (x, z) R1°R2.

5.Знайти помилку в наведених міркуваннях. Якщо R – симе-

тричне й транзитивне відношення на множині M, то R – рефлексивне, оскільки із того, що (a, b) R, послідовно випливає

(b, a) R і (a, a) R.

Якщо Pr1R ≠ M, то із симетричності й транзитивності відношення R не випливає його рефлексивність. Наприклад, відношення

R = {(1, 3), (3, 1), (1, 1), (3, 3)}

є симетричним і транзитивним, але не є рефлексивним на мно-

жині M = {1, 2, 3}.

6. Довести, що відношення

T = {(x, y) | | x – y | < 1, x, y R}

на множині дійсних чисел R є толерантним.

Рефлексивність T випливає із того, що для всіх дійсних x виконується нерівність | x – x | < 1, отже, (x, x) T. Симетричність T випливає із рівності | x – y | = | y – x |.

121