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

ОПРЕДЕЛЕНИЕ. Пусть А₁, А₂,..., А_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, y)ÎR, xÎX };

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

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

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

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

Как для любых множеств, для бинарных отношений можно определить понятия нестрогого и строгого включения и равенства. Так, например, R₁ содержится в R₂ (R₁ Í R₂), если любая пара (x, y), которая принадлежит отношению R_1, также принадлежит и отношению 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, z)ÎR₁ и (z, y)ÎR₂.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Доказать, что для любых множеств E, F, G справедливы равенства:

а) E´(F È G) = (E´F) È (E´G); б) E´(F Ç G) = (E´F) Ç (E´G);

в) (F È G)´E = (F´E) È (G´E); г) (FÇG)´E = (F´E) Ç (G´E).

2. Справедливы ли равенства:

а) (A´B) Ç (C´D) = (A Ç C) ´ (B Ç D);

б) (A´B) È (C´D) = (A È C) ´ (B È D)?

3. Доказать, что:

а) (A \ B)´C = (A´C) \ (B´C); б) A´(B \ C) = (A´B) \ (A´C).

4*. Доказать, что

(P´Q) \ (A´B) = ((P \ A)´Q) È (P´(Q \ B).

5. Пусть множества A и C непусты. Доказать, что, для того чтобы A Í B и C Í D, необходимо и достаточно, чтобы вы-полнялось включение A´C Í B´D. Остается ли в силе это утвер-ждение, если A или C пусто?

6. Доказать, что если A Í P, B Í Q, то

A´B = (A´Q) Ç (B´P).

Доказать тождества (7-13).

7. (A Ç B) ´ (C Ç D) = (A´C) Ç (B´D).

8. (A È B) ´ (C È D) = (A´C) È (B´C) È (A´D) È (B´D).

9. A´B = (A´D) Ç (C´B), где A Í C и B Í D.

10. S² \ (A´B) = [(S \ A) ´S] È [S´ (S \ B)].

11.Ç А_i´ Ç B_i= Ç(А_i ´ B_i).iÎI iÎI iÎI

12. È А_k´ ÈB_t= È (А_k ´ B_t). kÎK tÎT (k,t)ÎK´T

13. Ç А_k´ ÇB_t= Ç (А_k ´ B_t ).kÎK tÎT (k,t)ÎK´T

14. Пусть f: X®Y. Доказать, что отображение g: X® X´Y, определяемое равенством g(x) = (x, f(x)), инъективно.

15. Найти d_R, r_R, R ^–1, R o R, R o R ^–1, R ^–1 o R для отношений:

а*) R = { (x, y) | x,yÎ N, x делит y };

б) R = { (x, y) | x, yÎ N, y делит x };

в) R = { (x, y) | x, yÎ R, x + y £ 0 };

г) R = { (x, y) | x, yÎ R, 2x ³ 3y };

д) R = { (x, y) | x, yÎ[–p/2; p/2], y ³ sin x };

е) R = { (x, y) | x, yÎ R, 9x² £ 4y² };

ж) R = { (x, y) | x, yÎ R, y2 – 4y + 5 < 2x };

з) R = { (x, y) | x, yÎ R, 4x² – y² £ 1 };

и) R = { (x, y) | x, yÎ R, xy < 3 };

к) R = { (x, y) | x, yÎ N, x – y делится на m };

л) R = { (x, y) | x, yÎ R, x – [x] = y – [y] };

м) R = { (x, y) | x, yÎ N, x и y имеют общий делитель };

н) R = { (x, y) | x, yÎ R, 4x² + 9y² < 36 }.

Примеры решения

Задача 4.

1) Докажем включение (P´Q)\(A´B)Í((P\A)´Q)È (P´(Q\B)).

Пусть (x,y)Î(P´Q) \ (A´B), тогда (x,y)Î(P´Q) и (x,y)Ï(A´B). Это означает, что xÎP, yÎQ и либо xÏA, либо yÏB. В первом случае имеем xÎP, yÎQ, xÏA, следовательно, (x, y)Î(P \ A)´Q. Аналогично для второго случая получим, что (x, y)ÎP´(Q \ B). Следовательно, (x, y)Î((P \ A)´Q) È (P´(Q \ B)).

2) Докажем теперь обратное включение.

Так как (x, y)Î((P \ A)´Q) È (P´(Q \ B)), то (x, y)Î(P \ A)´Q или

(x, y)ÎP´(Q \ B). В первом случае получим, что xÎP, xÏA, yÎQ, во втором – xÎP, yÎQ, yÏB. Следовательно, в обоих случаях получим, (x, y)Î(P´Q) и (x, y)Ï(A´B), что и означает требуемое.

Задача 15 (а).

d_R={ xÎ N | yÎ N, x делит y }= N, так как для любого натурального x найдется yÎ N, например y = x, такой, что x делит y.

r_R={ yÎ N | xÎ N, x делит y }= N, так как для любого натурального y найдется xÎ N, например x = 1, такой, что x делит y.

R ^–1 ={ (x, y) | x, yÎ N, y делит x }.

RoR={ (x, y)Î N ² | $ zÎ N, x делит z и z делит y } = R, так как для любой пары (x, y)Î N ², такой, что x делит y, такое значение z существует, например z = x.

RoR ^–1={ (x, y)Î N ² | $ zÎ N, x делит z и y делит z }= N ². Такое натуральное z существует для любой пары (x, y)Î N ², например z=xy.

R ^–1oR={ (x, y)Î N ² | $ zÎ N, z делит x и z делит y } = N ². Такое натуральное z существует для любой пары (x, y)Î N ², например z = 1.