1.3. Бинарные отношения и их свойства

1.3.1. Декартово произведение и бинарное отношение

Декартовым произведением двух множеств A и B является но-

вое множество C, элементами которого являются все упорядоченные пары (a,b):

C = A × B = {(a, b) / a A, b B} .

Порядок в паре очень важен, в общем виде A × B ≠ B × A . Выбирая различные подмножества декартова произведения, мы

приходим к понятиям бинарного отношения, операции и функции. Бинарным отношением Т(М) на множестве М называется под-

множество M 2 = M ×M , T (M ) M 2 . Довольно часто использует-

ся другая, инфиксная форма записи бинарного отношения aTb ={(a,b) / (a,b) T M × M}.

Мы уже стакивались с понятием отношения при рассмотрении(включение) и = (равенство) между множествами. Также неоднократно использовались отношения =, ≠, ≤, ≥, >, <, заданные на

множестве чисел как натуральных, так и целых, рациональных, вещественных и т.д.

Определим несколько понятий относительно отношения

R(M ) M ×M [1]:

обратное отношение R−1 ={(x, y) / ( y, x) R};

дополнительное отношение R = {(x, y) /(x, y) R} ; тождественное отношение U = {(x, x) / x M } ; универсальное отношение I = {(x, y) / x M и y M}.

Обобщая понятие бинарного отношения, введем n-арное отношение как множество упорядоченных кортежей (наборов), являющееся подмножеством n-арного декартового произведения:

R M1 ×M2 ×...×Mn ={(m1 ,m2 ,...,mn ) / m1 M1

и m2 M2 ... и mn Mn }

Задача 1.3. На множестве M1= {a, b, c, d, e, f} построить тождественное бинарное отношение U.

17

Решение. По определению, на множестве M1={a, b, c, d, e, f} тождественное бинарное отношение

U = {(a,a), (b,b), (c,c), (d,d), (e,e), (d,d)}.

Задача 1.4. На множестве M натуральных чисел от 1 до 5 построить бинарное отношение R={(a,b)/mod(a,b)=0}.

Решение. В соответствии с заданием, на множестве натуральных чисел M строим такие пары (a, b), что а делится на b без остатка

(mod(a,b) = 0). Получаем

R = {(1,1), (2,2), (3,3), (4,4), (5,5), (2,1), (3,1), (4,1), (5,1), (4,2)}.

1.3.2. Функции и операции

Бинарное отношение F декартова произведения X ×Y называется функцией, если для каждого элемента x X найдется не более одного элемента y Y такого, что (x, y) F (x, y) , т.е. выпол-

няется свойство однозначности полученного результата. Множество X называется областью определения функции Dom,

и множество Y, область значений функции. Если элемент z DomF , то говорят, что функция F не определена на z. Таким образом, функции могут быть как полностью определенными на множестве X, так и частично определенными. Точно так же область значений функции может не совпадать с множеством Y, а быть его подмножеством.

Если область определения функции F из X в Y совпадает с X, то пишут F: X →Y.

Например: тождественная функция U переводит множество X само в себя, причем U: X → X для любого x X . А функция константы С, полностью определенная на Х, переводит все элементы множества Х в один единственный элемент y0 Y , С: X → у0.

Для функций обычно вместо записи (x, y) F или xFy, исполь-

зуют y = F(x).

Функция F: X →Y называется инъективной (или инъекцией, или вложением), если она переводит разные элементы в разные, то есть

x X и z X , x ≠ z → F(x) ≠ F(z) .

18

Функция F: X → Y называется сюръективной (или сюръекцией, или наложением), если множество ее значений есть все Y, т.е.

y Y x X : y = F (x) .

Иногда такие функции называют отображениями на Y. Функция F: X →Y называется биекцией (или взаимно одно-

значным соответствием), если она одновременно является инъекцией и сюръекцией (вложением и наложением),

Если F – биекция, то существует обратная функция F-1, для которой F −1 ( y) = x тогда и только тогда, когда F −1 (x) = y .

Частным случаем функции является операция 0. В этом случае область значения Х и область определения Y совпадают, т.е. 0 M 2 , x M !y,(x, y) 0 .

Задача 1.5. Построить на множестве M={a, b, c, d} отношение, сюръекцию, инъекцию и биекцию максимальной мощности.

Решение. Отношение максимальной мощности совпадает с декартовым произведением M ×M и его мощность равна 16.

При построении инъекции необходимо учитывать, что разным х соответствуют разные у, например F1 = {(a, b), (b, c), (c,d), (d,a)}. Для построения сюръекции нужно использовать все элементы у, F2 = {(a,a), (b,d), (c,c), (d,b)}. Обе эти функции являются как сюръекциями, так и инъекциями, следовательно, они – биекции. Мощность во всех случаях равна четырем.

Сами решения могут быть и другими, но максимальная мощность вычисляется однозначно.

Декартово произведение, отношение, функция или операция могут быть и n-арные.

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

Бинарные отношения R можно задать:

•перечислением, как любое множество пар;

•графически, когда каждый элемент х множества М представляется вершиной, а пара (x, y) R(M ) представляется дугой из х в у;

•матричным способом, с помощью матрицы смежности или матрицы инцинденций (инциндентности);

•фактор-множеством.

19

Перечисление элементов бинарного отношения мы использовали при решении задач. Построим графическое решение задачи 1.4 (рис.1.2).

Рис. 1.2

Матрица смежности S (рис. 1.3) представляет собой квадрат-

ную матрицу m ×m,		где m = | M | , и каждый ее элемент
			1,		если (m ,m			) R,
	sij =					i	j
					в противном случае.
			0,
1		1			2		3	4		5
		1			0		0		0	0
2		1			1		0		0	0
3		1			0		1		0	0
4		1			1		0		1	0
5		1			0		0		0	1

Рис. 1.3

Фактор-множеством R/M множества М по отношению к R называется множество окрестностей единичного радиуса для всех элементов М при заданном R. Для определения фактор-множества необходимо определить окрестность единичного радиуса mi M ,

состоящую из таких m j M , что (mi , m j ) R(M ) .

Решение задачи 1.4 в виде фактор-множества выглядит следующим образом:

	R/M =	1	2	3	4	5
		{1}	{1, 2}	{1, 3}	{1, 2, 4}	{1, 5}

20