Примеры бинарных отношений

Бинарные отношения и операции над ними

Def. Пусть А₁, А₂, . . . , А_n – некоторые множества. Их прямым или декартовым произведением называется множество упорядоченных наборов из n элементов, т.е.

А₁´А₂´ . . . ´А_n = {(а₁, а₂, . . . , а_n) | a_iÎA_i }.

Если все множества A_i совпадают A = А₁ = А₂ = . . . = А_n, то прямое произведение А₁´А₂´ . . . ´А_n = Aⁿ называют прямой n-ой степенью множества А.

Отношением (n-арным отношением) между элементами множеств А₁, А₂, . . . , А_n называется любое подмножество R Í А₁´А₂´ . . . ´А_n.

Бинарным отношением между элементами множеств А и В называется любое подмножество R Í A´B. Если множества A и B совпадают А = В, то R называют бинарным отношением на множестве А.

Если (x, y)ÎR, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R.

Пусть A = B = R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение

R_А = { (x, y) | x² + y² £ 1 }

определяет замкнутый круг единичного радиуса с центром в точке (0, 0) на плоскости, отношение

R_Б = { (x, y) | x ³ y }

полуплоскость, а отношение

R_В= { (x, y) | |x – y| £ 2 }

полосу.

Диагональ множества A´A, т.е. множество D={(x,x) | xÎA}, называется единичным бинарным отношением или отношением равенства в A.

Областью определения бинарного отношения R называется множество d_R = { xÎA | $ yÎB, (x, y) ÎR }– множество первых элементов пар (x, y).

Областью значений бинарного отношения R называется множество r_R = { yÎB | $ xÎA, (x, y)ÎR }– множество вторых элементов пар (x, y).

Как для любых множеств, для бинарных отношений можно определить понятия нестрогого и строгого включения и равенства. Так, например, R₁ содержится в R₂ (R₁Í R₂), если любая пара (x, y), которая принадлежит отношению R₁ а также принадлежит и отношению R₂. Например, R_А Í R_В, т.к. все точки (x, y), принадлежащие кругу R_А принадлежат также полосе R_в.

Операции над бинарными отношениями определяются подобно операциям над соответствующими множествами. Пусть А – произвольное множество на котором введены бинарные отношения R, R₁, R₂,...

1) Дополнение к отношению ={ (x, y) | (x, y)Î(A´A) \ R}.

2) Объединение двух бинарных отношений R₁ и R₂ – это отношение

R₁ È R₂ = { (x, y) | (x, y)ÎR₁ или (x, y)ÎR₂ }.

3) Пересечение двух бинарных отношений R₁ и R₂ – это отношение

R₁ Ç R₂ = { (x, y) | (x, y)ÎR₁ и (x, y)ÎR₂ }.

4) Обратное отношение R ^–1 = { (x, y) | (y, x)ÎR}.

5) Двойственное отношение R^d = .

6) Композиция (суперпозиция) отношений R = R₁oR₂ содержит пару (x, y) тогда и только тогда, когда существует такое zÎA, что (x, z)ÎR₁ и (z, y)ÎR₂.