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

Нехай 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 доведено.