Визначення. Бінарним відношенням R називається підмножина пар (a, b) ∈R декартова твори A × B, т. Е. R⊆A × B. При цьому безліч A називають областю визначення відносини R, безліч B - областю значень.
Позначення: aRb (т. Е. A і b знаходяться у відношенні R). /
Зауваження. якщо A = B. то кажуть, що R є відношення на безлічі A.
Способи завдання бінарних відносин
1. Списком (перерахуванням пар), для яких це відношення виконується.
2. Матрицею. Бінарним відношенню R ∈ A × A. де A = (a1. A2. An), відповідає квадратна матриця порядку n. в якій елемент cij. стоїть на перетині i-го рядка і j-го стовпця, дорівнює 1, якщо між ai і aj має місце відношення R. або 0, якщо воно відсутнє:
Нехай R - відношення на множині A, R ∈ A × A. Тоді відношення R:
рефлексивно, якщо Ɐ a ∈ A: a R a (головна діагональ матриці рефлексивного ставлення містить тільки одиниці);
антирефлексивне, якщо Ɐ a ∈ A: a R a (головна діагональ матриці Рефл пасивного відносини містить тільки нулі);
симетрично, якщо Ɐ a. b ∈ A: a R b ⇒ b R a (матриця такого ставлення симетрична щодо головної діагоналі, тобто cij cji);
антисиметрично, якщо Ɐ a, b ∈ A: a R b b R a ⇒ a = b (в матриці такого ставлення відсутні одиниці, симетричні відносно головної діагоналі);
транзитивно, якщо Ɐ a, b, c ∈ A: a R b b R c ⇒ a R c (в матриці такого ставлення повинно виконуватися умова: якщо в i-му рядку стоїть одиниця, наприклад в j-ой координаті (стовпці) рядки, т. е. cij = 1. то всім одиницям в j- ой рядку (нехай цим одиницям відповідають k е координати такі, що, cjk = 1) повинні відповідати одиниці в i-му рядку в тих же k-х координатах, т. е. cik = 1 (і, може бути, ще й в інших координатах).
Завдання 3.1. Визначте властивості відносини R - «бути дільником», заданого на множині натуральних чисел.
рефлексивно, що не антирефлексивне, так як будь-яке число ділить саме себе без залишку: a / a = 1 для всіх a∈N;
не симетричні, антисиметрично, наприклад, 2 дільник 4, але 4 не є дільником 2;
транзитивно, таккакеслі b / a ∈ N і c / b ∈ N, то c / a = b / a ⋅ c / b ∈ N, наприклад, якщо 6/3 = 2∈N і 18/6 = 3∈N, то 18/3 = 18 / 6⋅6 / 3 = 6∈N.
Завдання 3.2. Визначте властивості відносини R - «бути братом», заданого на безлічі людей.
Рішення.
НЕ рефлексивно, антирефлексивне через очевидного відсутності aRa для всіх a;
не симетричні, так як в загальному випадку між братом a і сестрою b має місце aRb. але не bRa;
НЕ антисиметрично, так як якщо a і b -Брат, то aRb і bRa, але a ≠ b;
транзитивно, якщо називати братами людей, які мають спільних батьків (батька та матір).
Завдання 3.3. Визначте властивості відносини R - «бути начальником», заданого на безлічі елементів структури
- НЕ рефлексивно, антирефлексивне, якщо в конкретній інтерпретації не має сенсу;
- не симетричні, антисиметрично, так як для всіх a ≠ b не виконується одночасно aRb і bRa;
- транзитивно, так як якщо a начальник b і b начальник c. то a начальник c.
Завдання для самостійного рішення
Визначте властивості відносини Ri. заданого на безлічі Mi матрицею, якщо:
Операції над бінарними відносинами
Нехай R1. R1 є відносини, задані на множині A.
Определеніе.Степенью відносини R на множині A називається його композиція з самим собою.
Визначення. Якщо R ⊂ A × B. то R º R -1 називається ядром відносини R.
Теорема 3.1. Нехай R ⊂ A × A - відношення, задане на безлічі A.
- R рефлексивно тоді і тільки тоді, (далі використовується знак ⇔) коли I ⊂ R.
- R симетрично ⇔ R = R -1.
- R транзитивне ⇔ R º R ⊂ R
- R антисиметрично ⇔ R ⌒ R -1 ⊂ I.
- R антирефлексивне ⇔ R ⌒ I = ∅.
Завдання 3.4. Нехай R - відношення між множинами і, заданий перерахуванням пар: R =. Крім того, S - відношення між множинами S =. Обчисліть R -1. S -1 і S º R. Перевірте, що (S º R) -1 = R -1. S -1.
Завдання 3.5. Нехай R відношення «. батько. », А S відношення«. брат. »На безлічі всіх людей. Дайте короткий словесний опис відносин:
R-1. S -1. R º S, S -1 º R -1 і R º R.
R -1 - відношення «. дитина. »;
S -1 - відношення «. Брат чи сестра. »;
R º S - відношення «. батько. »;
S -1 º R -1 - відношення «. дитина. »
R º R - відношення «. бабуся чи дідусь. »
Завдання для самостійного рішення
1) Нехай R - відношення «. батько. », А S - відношення«. сестра. »На безлічі всіх людей. Дайте словесний опис відносин:
R-1. S -1. R º S, S -1 º R -1. R º R.
2) Нехай R - відношення «. брат. », А S - відношення«. матір. »На безлічі всіх людей. Дайте словесний опис відносин:
R-1. S -1. S º R, R -1 º S -1. S º S.
3) Нехай R - відношення «. дід. », А S - відношення«. син. »На безлічі всіх людей. Дайте словесний опис відносин:
R-1. S -1. R º S, S -1 º R -1. S º S.
4) Нехай R - відношення «. дочка. », А S - відношення«. бабуся. »На множе- стве всіх людей. Дайте словесний опис відносин:
R-1. S -1. S º R, R -1 º S -1. R º R.
5) Нехай R - відношення «. племінниця. », А S - відношення«. батько. »На безлічі всіх людей. Дайте словесний опис відносин:
R-1. S -1. S º R, R -1 º S -1. R º R.
6) Нехай R - відношення «сестра. », А S - відношення« мати. »На безлічі всіх людей. Дайте словесний опис відносин:
R-1. S -1. R º S, S -1 º R -1. S º S.
7) Нехай R - відношення «. матір. », А S - відношення«. сестра. »На множе- стве всіх людей. Дайте словесний опис відносин:
R-1. S1, R º S, S1 º R1, S º S.
8) Нехай R - відношення «. син. », А S - відношення«. дід. »На безлічі всіх людей. Дайте словесний опис відносин:
R-1. S -1. S º R, R -1 º S -1. R º R.
9) Нехай R - відношення «. сестра. », А S - відношення«. батько. »На множе- стве всіх людей. Дайте словесний опис відносин:
R-1. S -1. R º S, S -1 º R -1. S º S.
10) Нехай R - відношення «. матір. », А S - відношення«. брат. »На безлічі всіх людей. Дайте словесний опис відносин:
R-1. S -1. S º R, R -1 º S -1. R º R.