3. Бинарные отношения во множествах

Опр.: Бинарное отношение ρ есть любое непустое подмножество декар­тового произведения двух множеств: ρ.

Бинарное отношение обозначается так: <х, у> ρ или х у или. Эти выражения эквивалентны и читаются как «х находится в отношении ρ к у».

Если рассматривается декартово произведение трех множеств, то говорят о тернарном отношении.

Пример

1. Отношениями могут служить:

х=у; ху; х > у; х < у в множестве Х действительных чисел;

2. х // у, х  у в множестве прямых плоскости;

3. Пусть X = {1,2, 3}, К = {1,2} рассматриваются как три издательства и два магазина, продающие книги. Тогда отно­шение ρ = {< 1,1 >, < 2, 2 >, < 3, 2 >} означает, что издательство I заключило договор с магазином 1, издательство 2-е магазином 2, издательство 3-c этим же магазином 2.

4. «х и у – родители z» - тернарное отношение.

5. Примером п -арного отношения, где п = 4, может служить таблица:

	Фамилия	Год рожд.	Место жительства	Образование
1	Иванов	1958	Оренбург	Высшее
2	…	…	…	…

Опр.: Областью определения бинарного отношения ρ (обозначение: D_ρ) называют множество первых координат элементов из ρ, областью значений отношения R (обозначение: E_ρ) — множество вторых координат элементов из ρ.

Например, областью определения для отношения мате­ринства служит множество всех матерей, в то время, как область значении этого отношения — множество всех людей.

4. Способы задания отношений

1. С помощью графика

Аналитическая геометрия плоскости основывается на допуще­нии о том, что между точками евклидовой плоскости и декартовым произведением R х R существует взаимно однозначное соответствие. Каждой точке на плоскости соответствуют ее координаты — упорядоченная пара <х, у>. Поэтому отношение на множестве R можно изображать па плоскости некоторой конфигурацией пли множеством точек. Например, отношение равенства можно изобра­зить в виде прямой у = х в декартовой системе координат.

Опр. Если основным предметом изучения служат отношения на множестве действительных чисел R, то множество точек, соответствующих элементам отношения, называют графиком этого отношения.

Ниже на рис. приводятся четыре примера отношений, для каждого из которых схематически представлен его график. В тех случаях, когда график является частью плоскости, эта часть плоскости на чертеже заштриховывается.

2. C помощью графа

Если задано отношениех ρ у, хХ, уУ, то элементы множеств X и У можно изображать точками на плоскости, а упорядоченную пару — линией со стрелкой (дугой), направленной от х к у. Тогда отношение на конечном множестве элементов может быть представлено в виде графа.

Пример

Рассмотрим отношение "х делится на у" для множеств Х={20, 25, 30, 35, 40} и Y= {2, 3, 4, 5). Граф этого отношения имеет следующий вид:

3. Матричный способ задания отношении

Зададим отношение ρ: «х дружит с у» на множестве М, где М= {а₁, а₂, а₃, а₄} множество персонажей. Это отношение можно представить в виде таблицы (матрицы), элементы которой равны единице, если между соответствующими элементами есть отношение дружбы, и нулю в противном случае.

	а1	а2	а3	а4
а1	1	0	1	0
а2	0	1	0	0
а3	1	0	1	1
а4	0	0	1	1

Из этой таблицы видно, что а₁ дружит с а₃, а₂ не дружит ни с кем, кроме как с самим собой, а а₃ дружит со всеми, кроме а₂. Такой способ задания отношений называется матричным способом.

В этом случае отношение ρ ХхУ представляется в виде матрицы А = || а_ij || с элементами а_ij, где i - номер строки, j - номер столбца; а_ij = 1, если элементы х_i и y_j находятся в отношении ρ, и а_ij = 0 в противном случае.

Если || а_ij || = 0, то ρ≡ 0 - пустое отношение;

если || а_ij || = 1, то ρ≡ 1 - полное отношение.