Тема „Відношення і функції”
Відношення означає якійсь зв’язок між елементами або поняттями. Відношення між парами об’єктів називаються бінарними (двомісними).
Приклади бінарних відношень:
відношення належності (a A);
включення множин (A B);
рівність дійних чисел (a = b, a, b N);
нерівності (натуральних, дійсних чисел).
Відношення записуються у вигляді співвідношень xAy, де A – відношення, яке встановлює зв’язок між x X і y Y. Отже, відношення повністю визначається множиною всіх пар елементів (x, y), для яких воно справджується. Тому будь-яке бінарне відношення можна розглядати як множину впорядкованих пар (x, y).
Означення 1. Бінарним відношенням A, що діє з множини X у множину Y, називається деяка підмножина X Y (A X Y).
Співвідношення xAy можна записати у вигляді (x, y) A X Y.
Наприклад, 4 < 7 еквівалентно (4, 7) „<” (але не можна записати (7, 4) „<”).
Елемент x називається першою координатою, а елемент y – другою координатою впорядкованої пари. D0(A) – множина перших координат –називається областю визначення (лівою областю) відношення A. D3(A) – множина других координат – називається областю значень (правою областю) відношення А.
Якщо x X, y Y, тоді D0(A) X, D3(A) Y. A є відношенням від X до Y. Його називають відповідністю та позначають X Y. Якщо Y = X, то будь-яке відношення A: X Y є підмножиною X X і називається відношенням в X.
Приклад. X = {2, 3}, Y = {3, 4, 5, 6}.
Нехай A – відношення „бути дільником” від X до Y. Тоді A = {(2, 4), (2, 6), (3, 3), (3, 6)}. Відношення B – „=” від X до Y: B = {(3, 3)} і відношення C – „>” від X до Y: C = , D0(A) = {2, 3} = X, D3(A) = {3, 4, 6} Y.
Якщо D0(X) = X, то кажуть, що відношення A задано на X.
Окремі випадки відношень
Повне (універсальне) відношення P = X X, яке справджується для будь-якої пари (xi, xj) елементів X. Наприклад, P – відношення „вчитися в одній групі”.
Тотожне (діагональне) відношення, що виконується тільки з одним і тим же елементом. Наприклад, рівність на множині цілих чисел.
Порожнє відношення – відношення, яке не задовольняє жодна пара елементів із X. Наприклад, A – відношення „бути братом” у множині X, де X – множина жінок.
Означення 2. Розглянемо відношення A X Y, xi X. Перерізом відношення A за елементом xi називається множина елементів y Y, для яких пара (xi, y) A
A(xi) = {y Y (xi, y) A}.
Множину всіх перерізів відношення A називають фактором-множиною множини Y за відношенням A і позначають Y/A. Вона повністю визначає відношення A.
Приклад. X = {x1, x2, x3, x4, x5}, Y = {y1, y2, y3, y4}. Відношення A = {(x1, y1), (x1, y3), (x2, y1), (x2, y3), (x2, y4), (x3, y1), (x3, y2), (x3, y4), (x4, y3), (x3, y2), (x5, y4)}. Очевидно, що A(x1) = {y1, y3}. Випишемо переріз за всіма елементами множини X у такому вигляді
-
x1
x2
x3
x4
x5
{y1, y2}
{y1, y3, y4}
{y1, y2, y4}
{y3}
{y2, y4}
Об’єднання множин другого рядка утворюють фактор-множину Y/A. Об’єднання перерізів за елементами деякої підмножини B X є перерізом A(B) відношення A за підмножиною B, тобто
A(B)
=
Оскільки для B = {x2, x3} маємо A(B) = {y1, y2, y3, y4} = A(x2) A(x3).
Матричний спосіб подання бінарних відношень грунтується на поданні відношення A X Y відповідною прямокутною таблицею (матрицею), що складається з нулів та одиниць, де стовпці – перші координати, а рядки – другі, причому на перетині i-го стовпця і j-го рядка буде 1, якщо виконується співвідношення xiAyi, або 0 – якщо воно не виконується.
Приклад. X = {x1, x2, x3, x4, x5}, Y = {y1, y2, y3, y4}, A = {(x1, y1), (x1, y3), (x2, y1), (x2, y3), (x2, y4), (x3, y1), (x1, y2), (x3, y4), (x5, y2), (x5, y4)}
-
x1
x2
x3
x4
x5
y1
1
1
1
0
0
y2
0
0
1
0
1
y3
1
1
0
1
0
y4
0
1
1
0
1
Матриця повного відношення – це квадратна матриця, що складається лише з одиниць.
Матриця тотожного відношення – по діагоналі 1, решта – нулі. Матриця порожнього відношення – квадратна матриця з нулів.
Відношення можна також зобразити за допомогою орієнтованого графа.
Означення 3. Графом G(V, E) називається сукупність двох множин – порожньої множини V (множини вершин) і множини E неупорядкованих пір різних елементів множини V (E – множина ребер).
Приклад. Граф відношення, наведеного в попередньому прикладі, має вигляд
x |
y1 |
Граф бінарного відношення – це дводольний граф. Відношення в X зображується графом із вершинами, що відповідають елементам цієї множини. Якщо xiAxi й xiAxj, то вершини зв’язуються двома протилежними спрямними дугами, які умовно можна замінювати однією |
x |
y2 |
|
x |
||
x |
y3 |
|
x |
y4 |
|
|
1
2
3
4
5неспрямною дугою (ребром). Співвідношенню xjAxj відповідає петля.
Приклад 3. Бінарне відношення A = {(x1, x2), (x1, x5), (x2, x1), (x2, x3), (x3, x1), (x3, x4), (x4, x5), (x6, x2)} подається графом (рис. 1)
x3
x3
x2
x1
x4
x5
x6
x2
x1
x4
x5
Рис. 1
Рис. 2
Граф повного відношення A = X X, де X = {x1, x2, x3, x4, x5} має вигляд (рис. 2)
Граф тотожного
(діагонального відношення)
Граф порожнього
відношення
x2
x1
x4
x5
x3
x2
x1
x4
x5
x3
Симетричне відношення. Оскільки відношення – це множина, то над ним можуть виконуватися всі теоретико-множинні операції.
Означення 4. Відношення, симетричне (обернене) деякому відношенню A X Y, називається A-1 і є підмножиною множини Y X, утвореною тими парами (y, x) X Y, для яких (x, y) A.
Перехід від A до A-1 здійснюється взаємною перестановкою координат кожної впорядкованої пари. Наприклад, відношення A – „x дільник y” має обернене до нього A-1 – „y кратне x” .
Приклад. A = {(2, 4), (2, 6), (3, 3), (3, 6)}, A-1 = {(4, 2), (6, 2), (3, 3), (6, 3)}.
При переході від A до A-1 область визначення стає областю значень і навпаки. Матриця A-1 – це транспонована матриця відношення A.
Граф оберненого відношення A-1 утворюється із графа відношення А заміною всіх дуг на протилежні.
Композиція відношень. Нехай дано три множини X, Y, Z та два відношення A X Y, B Y Z.
Означення 5. Композицією відношень A і B називається відношення C, що складається з усіх тих пар (x, z) X Z, для яких існує таке y Y, що (x, y) A й (y, z) B.
Будемо позначати композицію відношень символом . Тоді BA = C = {(x, z) X Z: y Y((x, y) A і (y, z) B)}, тобто C(x) = B(A(x)).
Приклад 5. A = {(x1, y1), (x1, y3), (x2, y1), (x2, y3), (x2, y4), (x3, y1), (x3, y2), (x3, y4), (x4, y3), (x5, y2), (x5, y4)}, B = {(y1, z2), (y2, z1), (y2, z2), (y3, z3), (y4, z3)}.
C = BA = {(x1, z2), (x1, z3), (x2, z2), (x2, z3), (x3, z2), (x3, z1), (x3, z3), (x4, z3), (x5, z1), (x5, z2), (x5, z3) }.
Візьмемо переріз C за x3, C(x3) = {z1, z2, z3}. З іншого боку маємо B(A(x3)) = {y1, y2, y3} = {z2} {z1, z2} {z3} = {z1, z2, z3}.