✖

Бінарне відношення

Бінарне відношення — це особливий тип відношення з арністю два. До типових бінарних відношень належать, наприклад, «менше ніж», рівність, подільність, «більше ніж» тощо.

Приклади

Бінарне відношення — одне з типових і найпоширеніших відношень. Водночас воно має деякі цікаві властивості, які ми тут опишемо.

Прикладом бінарного відношення може бути зв'язок «батько — син», пара «транспортний засіб — кількість коліс» або загальніше «об'єкт — властивість об'єкта». Об'єктом може бути тварина, а властивістю — кількість ніг, середня тривалість життя, кількість волосин на голові тощо.

Бінарне відношення R між множинами M1 і M2 можна означити так: R ⊆ M1 × M2. Бінарне відношення — це множина пар, причому ця множина є підмножиною декартового добутку двох множин, між якими відношення запроваджуємо. Отже, відношення «батько — син» може бути відношенням між множинами всіх людей, між множинами всіх людей у Європі чи в Києві. Множину можна обмежити й іншим способом: можемо сказати, що відношення означаємо між множинами всіх чоловіків, а не людей загалом.

Для бінарних відношень зазвичай використовуємо спеціальне позначення. Замість того щоб писати (a; b) ∈ R, можемо написати aRb. Наприклад, замість (3; 1) ∈ > можемо написати 3 > 1. Подібно для інших відношень. Отже, запис aSb рівносильний запису (a; b) ∈ S.

Обернене відношення

Обернене відношення — це відношення, протилежне до поточного. (Увага, не плутай із доповненням відношення.) Яке відношення протилежне до відношення «менше ніж»? «Більше ніж». Якщо відношення «менше ніж» містить елемент (4; 7), тобто 4 < 7, то обернений елемент буде протилежним: 7 > 4, в оберненому відношенні буде обернена пара (7; 4).

Якщо маємо відношення R ⊆ M1 × M2, то обернене відношення R−1 будуємо так: беремо всі елементи (a; b) ∈ R і вносимо в R−1 їхню обернену пару. Тобто якщо відношення R містить елемент (a; b), то відношення R−1 має містити елемент (b; a). Це виконується й навпаки: якщо R−1 містить елемент (b; a), то відношення R має містити елемент (a; b).

Якщо записати це формально, то відношення R−1 обернене до R тоді й лише тоді, коли виконується:

∀a∈M1∀b∈M2:(a;b)∈R⇔(b;a)∈R−1

Отже, 6 < 8 тоді й лише тоді, коли 8 > 6. Подібно для інших пар.

Композиція відношень

Бінарні відношення можна поєднувати в композицію. Нехай маємо два відношення: перше, R, — «бути батьком свого сина», і друге, S, — «бути братом своєї сестри». Отже, відношення R містить пари (батько; син), друге відношення містить пари (брат; сестра).

Спробуймо тепер утворити композицію відношень. Утвориться нове відношення, позначимо його R ∘ S, і це відношення містить елемент (a; c) тоді й лише тоді, коли (a; b) ∈ R і водночас (b; c) ∈ S. Зверни увагу, що в обох елементах трапляється b: один раз на другому місці, а потім на першому місці пари. Це свого роду сполучний елемент композиції.

Приклад: R = {(Антон; Марко), (Петро; Яків)} і S = {(Марко; Яна), (Марко; Леся), (Яків; Люба)}. Антон — батько Марка, Петро — батько Якова. Марко має сестер Яну й Лесю, а Яків має сестру Любу.

Тепер утворімо композицію відношень: R ∘ S. Шукаємо таку пару з R, у якої на місці сина стоїть той, хто у відношенні S значиться як брат. Наприклад, ці дві пари: (Антон; Марко) і (Марко; Яна). Марко — сполучний елемент, він нам далі не потрібен, а з решти імен створюємо нову пару: (Антон; Яна). Отже, відношення R ∘ S містить пару (Антон; Яна). Марко має ще одну сестру, Лесю, її теж додамо до композиції: (Антон; Леся). Нарешті лишився син Яків. Він має сестру Любу. Тож маємо дві пари: (Петро; Яків) і (Яків; Люба). З них створюємо ще один елемент: (Петро; Люба).

Результат — відношення: R ∘ S = {(Антон; Яна), (Антон; Леся), (Петро; Люба)}. Як можна було б назвати це відношення? Найімовірніше, «бути батьком своєї доньки».

Ще раз повне означення:

(a;c)∈(R∘S)⇔∃b(a;b)∈R∧(b;c)∈S

Примітка: іноді використовують зворотний запис, тобто для того самого означення замість R ∘ S писали б S ∘ R.

Розділи: Відношення, Операції з відношеннями, Бінарне відношення, Бінарне відношення на множині, Відношення еквівалентності, Відношення порядку, Ґратки