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

ОПРЕДЕЛЕНИЕ. Пусть А₁, А₂, ..., А_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.

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. A. определении прав пользователя на операции с файлами и каталогами
2. I. Классификация установок, по Узнадзе.
3. I. Межличностные отношения, общение
4. I. Стиль отношения учителя к учащимся
5. III Изучение отношения потребителей к определенной марке товара
6. III. Актуализация знаний. Проверка работы над проектом
7. IV. Работа над пройденным материалом.
8. V. Работа над пройденным материалом.
9. VI. Предупредительные надписи
10. VIII. Какую массу бихромата калия надо взять для приготовления 2 л 0,02 н. раствора, если он предназначен для изучения окислительных свойств этого вещества в кислой среде.
11. XVI. Международные отношения. Проблемы глобализации и секуляризма.
12. XX конкурса-фестиваля детского художественного творчества «Лучики надежды – 2017»