double arrow

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


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

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

А1´А2´ . . . ´Аn = {(а1, а2, . . . , аn) | aiÎAi }.

Если все множества Ai совпадают A = А1 = А2 = . . . = Аn, то прямое произведение А1´А2´ . . . ´Аn = An называют прямой n-ой степенью множества А.

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

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

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

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

RА = { (x, y) | x2 + y2 £ 1 }

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

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

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

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

полосу.

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




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

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

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

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

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

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

R1 È R2 = { (x, y) | (x, y)ÎR1 или (x, y)ÎR2 }.

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

R1 Ç R2 = { (x, y) | (x, y)ÎR1 и (x, y)ÎR2 }.

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

5) Двойственное отношение Rd = .

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







Сейчас читают про: