Задачі та вправи

І. Побудувати приклади унарних, бінарних та тернарних відношень, заданих на множині {1,2,3,4,5,6}.

ІІ. Побудувати приклади унарних, бінарних та тернарних відношень, заданих на множині:

1) N, 2) Z, 3) Q,

4) R, 5) людей, 6) тварин,

7) птахів, 8) квітів, 9) країн світу,

10) учнів школи, 11) днів тижня, 12) видів спорту.

ІІІ. Нехай А={1,2,3,4,5,6,7,8,9,10}, RА². Записати відношення R у явному вигляді:

1) R={<x,y>| x,yA, x – дільник y, х5},

2) R={<x,y>| x,yA, x<y, х2},

3) R={<x,y>| x,yA, xy+1, y>7},

4) R={<x,y>| x,yA, x–y ділитьcя на 3},

5) R={<x,y>| x,yA, x+y ділитьcя на 5},

6) R={<x,y>| x,yA, x>y, x+y<6},

7) R={<x,y>| x,yA, x парне, y непарне},

8) R={<x,y>| x,yA, x просте, y складене},

9) R={<x,y>| x,yA, x кратне 5, y<5},

10) R={<x,y>| x,yA, x,y не мають спільних дільників, відмінних від 1}.

IV. Нехай Х=P({а,б,в}). Знайти усі елементи відношень , , , ,  на Х.

Операції над відношеннями

Нехай R₁, R₂ – відношення, задані на множинах A₁,…,A_n. Об’єднанням відношень R₁ та R₂ (позначається R₁R₂) називається мно-жина R₁R₂={<a₁,…,a_n>| <a₁,…,a_n>R₁ або <a₁,…,a_n>R₂}. Перетином відношень R₁ та R₂ (позначається R₁R₂) називається множина R₁R₂={<a₁,…,a_n>| <a₁,…,a_n>R₁, <a₁,…,a_n>R₂}. Різницею відношень R₁ та R₂ (позначається R₁\R₂) називається множина R₁\R₂={<a₁,…,a_n>| <a₁,…,a_n>R₁, <a₁,…,a_n>R₂}. Доповненням відношення R₁ (познача-ється R₁) називається множина R₁=А₁…A_n\R₁, тобто R₁={<a₁,…,a_n>| <a₁,…,a_n>А₁…A_n, <a₁,…,a_n>R₁}. Вираз <a₁,…,a_n>R₁ означає, що <a₁,…,a_n>R₁ (при цьому, звичайно, <a₁,…,a_n>А₁…A_n, але для скорочення запису це твердження опускають).

Нехай, наприклад, A₁={1,2,3}, A₂={a,b,c}, R₁, R₂ – відношення, за-дані на множинах А₁ та А₂, й R₁={<1,a>,<1,b>,<2,b>,<3,c>}, R₂={<1,b>, <3,c>,<3,a>}. Тоді:

R₁R₂={<1,a>,<1,b>,<2,b>,<3,c>,<3,a>},

R₁R₂={<1,b>,<3,c>},

R₁\R₂={<1,a>,<2,b>},

R₁={<1,c>,<2,a>,<2,c>,<3,a>,<3,b>}.

Розглянемо дві операції, визначені для відношень, заданих на двох множинах. Нехай відношення R задано на множинах А та В. Відношенням, оберненим до R (позначається R^-1), називається відно-шення, задане на множинах В та А, виду R^-1={<x,y>| <y,x>R}.

Нехай, наприклад, А={а,с,е}, В={1,3,5}, RАВ й R={<a,1>, <a,3>,<c,3>,<c,5>,<e,5>}. Тоді R^-1={<1,a>,<3,a>,<3,c>,<5,c>,<5,e>}. Відношенням, оберненим до відношення , заданого на булеані деякої множини А, є відношення, задане на булеані множини А, виду {<S,T>| <T,S>}, тобто множина упорядкованих пар <S,T> підмножин множини А таких, що ТS, або SТ. Отже, відношенням, оберненим до , є відношення .

Нехай R₁ – відношення, задане на множинах А та В, а R₂ – відно-шення, задане на множинах В та С. Добутком (або композицією) відношень R₁ та R₁ (позначається R₁R₂ або R₁○R₂) називається відно-шення, задане на множинах А та С, виду R₁R₂={<x,y>| для деякого z з B <x,z>R₁, <z,y>R₂}. Іншими словами, добуток відношень R₁ та R₂ складається з таких упорядкованих пар <x,y>, які «побудовані» з пар виду <x,z> та <z,y>, що належaть відповідно відношенням R₁ та R₂.

Наприклад, нехай А={a,b,c,d}, B={1,2,3}, C={2,4,6}, R₁AB, R₂BC, R₁={<a,3>,<a,2>,<b,1>,<c,2>}, R₂={<2,2>,<3,6>}. Тоді добуток R₁ та R₂ – це відношення, задане на множинах А та С, виду R₁R₂={<a,6>,<a,2>,<c,2>}. Розглянемо тепер відношення R₃={<a,1>, <b,1>,<d,1>}, задане на множинах А та В, й обчислимо R₃R₂. Оскільки відношення R₃ та R₂ не містять пар виду <x,z> та <z,y>, тобто таких пар, що другий компонент першої пари (тієї, що належить відношенню R₃) збігається з першим компонентом другої пари (тієї, що належить відношенню R₂), пар виду <x,y> утворити не можна, отже, R₃R₂=.

Теорема 5. Нехай R, R₁, R₂, R₃ – бінарні відношення на множині А. Тоді:

1) (R^-1)^-1=R, 2) (R₁R₂)^-1=R₁^-1R₂^-1,

3) (R₁R₂)^-1=R₁^-1R₂^-1, 4) (R^-1)=(R)^-1,

5) (R₁\R₂)^-1=R₁^-1\R₂^-1, 6) RR=RR=R,

7) R₁(R₂R₃)=(R₁R₂)(R₁R₃), 8) (R₁R₂)R₃=(R₁R₃)(R₂R₃).

9) (R₁R₂)R₃=R₁(R₂R₃), 10) (R₁R₂)^-1=R₂^-1R₁^-1.

Доведемо рівність 4. Використовуючи означення доповнення відношення та означення відношення, оберненого до даного, маємо: <x,y>(R^-1)  <x,y>R^-1  <y,x>R  <y,x>R  <x,y>(R)^-1. Отже, (R^-1)(R)^-1. Покажемо, що (R)^-1(R^-1). <x,y>(R)^-1  <y,x>R  <y,x>R  <x,y>R^-1  <x,y>(R^-1). Отже, показали, що (R^-1)=(R)^-1.

Доведемо останню рівність. Використовуючи означення відно-шення, оберненого до даного, та означення добутку відношень, маємо: <x,y>(R₁R₂)^-1  <y,x>(R₁R₂)  існує такий елемент z з множини A, що <y,z>R₁ тa <z,x>R₂  <x,z>R₂^-1, <z,y>R₁^-1  <x,y>R₂^-1R₁^-1. Отже, (R₁R₂)^-1  R₂^-1R₁^-1. Покажемо, що R₂^-1R₁^-1  (R₁R₂)^-1. <x,y>R₂^-1R₁^-1  існує такий елемент z з множини A, що <x,z>R₂^-1 та <z,y>R₁^-1  <z,x>R₂, <y,z>R₁  <y,x>R₁R₂  <x,y>(R₁R₂)^-1. Таким чином, доведено, що R₂^-1R₁^-1  (R₁R₂)^-1, отже, рівність 10 доведено.