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

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

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

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

Задача 1.. Доказать, что

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

Решение.

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), что и означает требуемое.

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

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

Диагональ множества 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).

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

Задача 2. Найти 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 }

Решение. 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.

Задача 3. Доказать тождество`R = (R<sup>–1</sup> \ R) È (`R Ç R^d).

Решение.

1) Покажем, что`R Í (R<sup>-1</sup> \R) È (`R Ç R^d). Пусть (x, y)Î`R, т.е. (x, y)ÏR. Для пары (y, x) возможны два случая: либо (y, x)ÎR, либо (y, x)ÏR. В первом случае получаем, что (x, y)ÎR<sup>–1</sup> и (x, y)ÏR, следовательно, (x,y)Î R<sup>–1</sup> \ R. Для второго случая спра-ведливо (x, y)Î`R и (x, y)Î R^–1 = R^d, что означает (x, y)Î`RÇ R<sup>d</sup>. В обоих случаях получим, что (x, y)Î (R<sup>-1</sup> \ R) È (`R Ç R^d).

2). Докажем теперь обратное включение. Так как (x,y)Î Î( R^–1 \ R) È (`R Ç R<sup>d</sup>), то (x, y)Î R<sup>–1</sup> \R или (x, y)Î`R Ç R^d. В обоих случаях то, что (x, y)`R следует непосредственно из определений пересечения или разности множеств.

Задача15(г).

Решение.Пусть yÎr_R°R, т.е. существует такой xÎA, что (x,y) Î

ÎR₁oR₂. Следовательно, найдется такое z, что (x,z)ÎR₁ и (z,y)Î ÎR₂, но это по определению означает, что z Î r_Rи zÎd_R. Поэтому, zÎr_RÇd_R. Так как (z,y)Î R₂, то по определению образа множества относительно отношения, получим yÎ R₂(r_RÇd_R). R₁^d.

2) Докажем обратное. Пусть yÎ R₂(r_RÇd_R), тогда существует элемент xÎr_R°R, что (x,y) Î R₂. Следовательно, xÎr_Rи xÎd_RxÎrR следует, что найдется такой z, что (z,x) Î R₁, а так как (x,y)Î R₂, то (z,y) Î R₁oR₂. Поэтому yÎr_R°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. Пусть множества A и C непусты. Доказать, что, для того чтобы A Í B и C Í D, необходимо и достаточно, чтобы вы-полнялось включение A´C Í B´D. Остается ли в силе это утвер-ждение, если A или C пусто?

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

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

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

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

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

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

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

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

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

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

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

14. Найти 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 }.

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

а) d_R= Æ Û R=Æ Û r_R = Æ; б) d_R^–1 =r_R, r_R^–1=d_R;

в) d_R°R= R₁^-1 (r_RÇd_R); г) r_R°R= R₂(r_RÇd_R);

д) если B¹Æ то d_A´B =A; е) если A¹Æ то r_A´B=B.

16. Доказать, что R ¹ R^d для произвольного отношения R .

17. Доказать включение R^–1Í RÈ(`R Ç R^–1).

18. Доказать, что для любых бинарных отношений:

а) Qo(ÈR_i ) = È(Q o R_i); I ÎI i Î I б) Q o ( Ç R_i) Í Ç(Q oR_i); i ÎI i Î I

в) (ÈR_i)oQ = È(R_i oQ); i ÎI i Î I г) (ÇR_i)oQ Í Ç( R_ioQ). i ÎI i Î I

19. Доказать, что для того, чтобы отношение R Í A´B было взаимно однозначным соответствием между A и B, необходимо и достаточно, чтобы R o R^–1 = R^–1 o R = D.

20. Пусть X = {2, 3, 4, 5, 6, 7, 8, 9}. Построить матрицу и граф следующих бинарных отношений:

а) R = { (x_i ,x_j) | x_i ,x_jÎX, x_i делится на x_j };

б) R = { (x_i ,x_j) | x_i ,x_jÎX, x_i >x_j };

в) R = { (x_i ,x_j) | x_i ,x_jÎX, x_i и x_j имеют общий делитель};

г) R = { (x_i ,x_j) | x_i ,x_jÎX, x_i ×x_j £15};

д) R = { (x_i ,x_j) | x_i ,x_jÎX, $ n: x_j =x_i ⁿ }.

21. Для бинарных отношений R, определенных в задаче 15 п.1 построить множества G_R(x) и H_R(x).

22. Пусть x=(x₁,x₂) и R = { (x,y) | , x,yÎR, r(x,y) £ k}. По-

строить верхний и нижний срезы отношения R, если:

а) r(x,y) = ; б) r(x,y) = max | x_i - y_i |; i i

в) r(x,y) = å|x_i - y_i |. I