Бинарни релации

Бинарната релация е специален вид релация с арност две. Типични бинарни релации са например „по-малко от“, равенство, делимост, „по-голямо от“ и т.н.

Примери

Бинарната релация е една от типичните и най-често срещаните релации. Същевременно има някои интересни свойства, които ще опишем тук.

Пример за бинарна релация може да бъде връзката „баща – син“, двойката „превозно средство – брой колела“ или по-общото „обект – свойство на обекта“. Обектът може да е животно, а свойството – брой крака, средна продължителност на живота, брой косми на главата и подобни.

Бинарната релация R между множествата M₁ и M₂ можем да определим така: R ⊆ M₁ × M₂. Бинарната релация е множество от двойки, като това множество е подмножество на декартовото произведение на двете множества, между които въвеждаме релацията. Така релацията „баща – син“ може да бъде релация между множествата на всички хора, между множествата на всички хора в Европа или в София. Множеството можем да ограничим и в друга посока: можем да кажем, че релацията определяме между множествата на всички мъже, а не на всички хора.

За бинарните релации обикновено използваме специално означение. Вместо да пишем (a; b) ∈ R, можем да напишем aRb. Например вместо (3; 1) ∈ > можем да напишем 3 > 1. Подобно е и за останалите релации. Така записът aSb е равносилен на записа (a; b) ∈ S.

Обратна релация

Обратната релация е релацията, противоположна на дадената. (Внимание, да не се бърка с допълнението на релация.) Коя е противоположната релация на релацията „по-малко от“? „По-голямо от“. Ако релацията „по-малко от“ съдържа елемента (4; 7), тоест 4 < 7, обратният елемент ще е противоположният: 7 > 4, в обратната релация ще бъде обратната двойка (7; 4).

Ако имаме релация R ⊆ M₁ × M₂, обратната релация R⁻¹ построяваме така: вземаме всички елементи (a; b) ∈ R и в R⁻¹ поставяме техните обратни. Тоест ако релацията R съдържа елемента (a; b), релацията R⁻¹ трябва да съдържа елемента (b; a). Важи и обратното: ако R⁻¹ съдържа елемента (b; a), релацията R трябва да съдържа елемента (a; b).

Ако го запишем като определение, релацията R⁻¹ е обратна на R тогава и само тогава, когато е изпълнено:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a;b)\in R\iff (b;a)\in 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)\in (R\circ S)\iff \mathrm{\exists }b(a;b)\in R\wedge (b;c)\in S$$

Забележка: понякога се използва обратен запис, тоест за същото определение вместо R ∘ S би се използвало S ∘ R.