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

ЛЕКЦИЯ № 5

ОПРЕДЕЛЕНИЕ. Пусть А₁, А₂,..., А_n - некоторые множества. Их прямым или декартовым произведением называется множество упорядоченных наборов из n элементов, т.е.

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

Если все множества A_i совпадают A=А₁=А₂=... =А_n, то прямое произведение А₁´А₂´... ´А_n=Aⁿ называют прямой 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| £ 1 }

полосу.

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

Областью определения бинарного отношения R называется множество

d_R={ xÎA | yÎB, (x, y) ÎR }.

Областью значений бинарного отношения R называется множество

r_R={ yÎB | xÎA, (x, y)ÎR }.

Образом множества X относительно отношения R называется множество

R(X) = { yÎB | xÎX, (x, y)ÎR };

прообразом X относительно R называется R ^-1(X).

В теории выбора и принятия решений большую роль играют бинарные отношения предпочтения, то есть такие отношения, согласно которым в паре (x, y)ÎR элемент x в каком-то смысле лучше чем y. Например:

- в смысле отношения R₂ "лучше" означает "больше или равно";

- в смысле отношения R₃ понятие "лучше" может означать "отстоит не больше чем на единицу".

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

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

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

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

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

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

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

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

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

7) R₁ содержится в R₂ (R₁ Í R₂), если любая пара (x, y), которая принадлежит отношению R_1, также принадлежит и отношению R₂.