Бинарные отношения. Прямое произведение множеств

Бинарным отношением r называется множество упорядоченных пар. Если r есть некоторое отношение и пара (х, у) принадлежит этому отношению, то употребляется запись (х, у)Î r или х rу. Элементы х и у называются координатами или компонентами (объектами) отношения r. Если х и у компоненты (объекты), то через (х, у) обозначают упорядоченную пару. Равенство упорядоченных пар определяется следующим образом: (а, b) = (с, d):= а = с и b = d (:= – операция присваивания).

Областью определения бинарного отношения r называется множество D _r = { x ׀существует такое у, что х rу }. Областью значений бинарного отношения r называется множество R _r = { y ׀существует такое x, что х rу }.

Так как бинарное отношение – множество, то способы задания бинарного отношения такие же, как и способы задания множества. Бинарное отношение может быть задано перечислением упорядоченных пар или указанием общего свойства упорядоченных пар.

Кроме того, бинарное отношение может быть задано матрицей бинарного отношения. Пусть А = { a ₁, a ₂, …, a _n } – конечное множество. Матрица бинарного отношения C есть квадратная матрица порядка n, элементы которой c_ij определяются следующим образом:

c_ij =

Пример. А = {1, 2, 3, 4}. Зададим бинарное отношение r тремя перечисленными способами.

1. r = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} – отношение задано перечислением всех упорядоченных пар.

2. r  = {(a_i, a_j) ç a_i < a_j; a_i, a_j Î А } – отношение задано указанием свойства "меньше" на множестве А.

3.  – отношение задано матрицей отношения C.

Пусть даны два множества Х и У. Прямым (декартовым) произведением двух множеств Х и У называется совокупность всех упорядоченных пар (х, у), таких, что х Î Х и у Î У. Обозначается прямое произведение множеств Х и У через Х × У:    Х × У:= {(х, у)| х Î Х и у Î У }.

Каждое отношение r есть подмножество прямого произведения некоторых множеств Х и У, таких, что D _r Í Х и R _r Í У, то есть r Ì Х ´ У. Если Х = У, то говорят, что r есть отношение на множестве Х, и тогда r Ì Х ².

Примеры. 1. Пусть Х = {1, 2, 3}, У = {0, 1}. Тогда

Х ´ У = {(1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)};

У ´ Х = {(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3)}.

Пусть r есть отношение на множестве Х. Введем понятия: обратное отношение: r ^-1 = {(х, у)| (у, х) Î r }; дополнение отношения: ` r = {(х, у)| (х, у)Ï r }; тождественное отношение: I = {(х, x)| х Î x }. Композицией отношений r ₁ и r ₂ называется отношение r₁О r ₂ = {(х, z)| существует у такое, что (х, у) Î r ₁ и (у, z)Î r ₂}. Для любых бинарных отношений выполняются следующие свойства: 1) (r ^-1)^-1 = r; 2)   r₂О r ₁ = r ₁ ^{- 1} О r ₂ ^-1.

Пример. r = {< x, y > çy = }. s = {< x, y > ç y = }.

s r = {< x, z > çсуществует такое y, что < x, y > Î r и < y, z > Î s } = {< x, z > çсуществует такое y, что y =  и z = } = {< x, z > ç z = }.

Свойства отношений

Отношение r называется рефлексивным на множестве X, если для любого x Î X выполняется x r x. Из определения следует, что всякий элемент (x, x) Î r.

Пример. 1. Пусть X – конечное множество, X = {1, 2, 3} и r  = {<1, 1>, <1, 2>, <2, 2>, <3, 1>, <3, 3>}. Отношение r рефлексивно. Если X – конечное множество, то главная диагональ матрицы рефлексивного отношения содержит только единицы. Для данного примера

2. Пусть X – множество действительных чисел и r – отношение равенства. Это отношение рефлексивно, т. к. каждое число равно самому себе.

Отношение r называется симметричным на множестве X, если для любых x, y Î X из x r y следует y r x. Очевидно, что r симметрично тогда и только тогда, когда r = r ^{– 1}.

Пример. 1. Пусть X – конечное множество, X = {1, 2, 3} и r = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <3, 1>, <3, 3>}. Отношение r симметрично. Если X – конечное множество, то матрица симметричного отношения симметрична относительно главной диагонали. Тогда .

2. Пусть X – множество действительных чисел и r – отношение равенства. Это отношение симметрично, т. к. если x равно y, то и y равно x.  

Отношение r называется транзитивным на множестве X, если для любых x, y, z Î X из x r y и y r z следует x r z. Одновременное выполнение условий x r y, y r z, x r z означает, что пара < x, z > принадлежит композиции r r. Поэтому для транзитивности r необходимо и достаточно, чтобы множество r r являлось подмножеством r, т. е. r r Í r.

Пример. Пусть X – конечное множество, X = {1, 2, 3} и r = {<1, 1>, <1, 2>, <2, 3>, <1, 3>}. Отношение r транзитивно, т. к. наряду с парами < x, y >и < y, z >имеется пара< x, z >. Например, наряду с парами <1, 2> и <2, 3> имеется пара <1, 3>.

Задания

Для аудиторных занятий

1. Перечислить элементы множеств А ´ В, В ´ А:

а) А = {1, 2}, В = {3, 4, 5};

б) А = {1}, В = {1, 2, 3}.

2. Пусть А, В Í С. Доказать, что А ´ В = (А ´ С) Ç (С ´ В).

3. Пусть А, В, С, D – непустые множества. Доказать следующие тождества:

а) (А Ç В) ´ (С Ç D) = (А ´ С) Ç (В ´ D);

б) (В È С) ´ А = (В ´ А) È (С ´ А).

4. Доказать, что для любых непустых множеств А, В, С из равенства (А ´ В) È (В ´ А) = С ´ С следует, что А = В = С.

5. Перечислить все элементы бинарного отношения r:

а) х rу Û х < у;	на множестве А = {1, 2, 3, 4};
б) х rу Û   х / у;	на множестве А = {2, 5, 10}.

6. Для каждого из следующих бинарных отношений, определенных на множестве R, найти область определения, область значений и нарисовать декартову диаграмму, то есть изобразить на плоскости множество всех точек (х, у), таких, что х rу:

а) х rу Û х £ у;	д) х rу Û х ^2 = у;
б) х rу Û х = у;	е) х rу Û х ^2 = у ^2;
в) х rу Û х < у;	ж) х rу Û х + у = 1;
г) х rу Û у ^2 = х;	з) х rу Û у =

7. Для бинарного отношения r между элементами множеств А и В найти область определения D _r и область значений R _r: А = {1, 2, 3, 4, 5},    В = {{1}, {1, 2}, 3, 4, 5}.

8. Найти r ^-1, rО r, r ^{- 1} О r, rО r^{- 1} отношений:

а) r = {(x, y)| х, у Î R и х + у ≤ 0};	г) х rу Û х ^2+ x = у ^2+ y, х, у Î R;
б) х rу Û х ^2 = у, х, у Î R;	д) х rу Û х ^2 = у ^2, х, у Î R;
в) х rу Û х у > 1, х, у Î R;	е) х rу Û х + у = 1, х, у Î R.

9. Задано бинарное отношение r = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}. Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

10. Привести пример отношения нетранзитивного, нерефлексивного и несимметричного.

Для самостоятельной работы

1. Перечислить элементы множеств А ´ В, В ´ А:

а) А = {1}, В = {1, 2, 3};

б) А = Æ, В ={ 1, 2, 3, 4}.

2. Пусть А = { и, л }. Перечислить элементы множеств А ², А ³.

3. Определить упорядоченную пару á a, b ñ как множество {{ a }, { a, b }}. Доказать, что á a, b ñ = á c, d ñ тогда и только тогда, когда a = c и b = d.

4. Пусть на плоскости задана декартова система координат. Изобразить на плоскости следующие множества:

а) [ a, b ] ´ [ c, d ], где a, b, c, d Î R и a < b, c < d;

б) [ a, b ]².

5. Доказать, что подмножество С множества А ´ В является прямым произведением некоторого подмножества А ₁ множества А и подмножества В ₁ множества В тогда и только тогда, когда для любых пар á a, b ñ, á c, d ñ из С пары á a, b ñ, á c, d ñ также принадлежат С.

6. Перечислить все элементы бинарного отношения r и нарисовать его график:

а) х rу Û у = х + 1;

на множестве А = {1, 2, …, 10}.

7. Для каждого из следующих бинарных отношений, определенных на множестве R, найти область определения, область значений:

а) х rу Û х ≥ у;	в) х rу Û х ^3 = у;
б) х rу Û х = у;	г) х rу Û х ^2 = у ^2.

8. Какими свойствами обладают следующие бинарные отношения (рефлексивность, симметричность, транзитивность), заданные на R?

а) х rу Û х > у;	в) х rу Û х + у = 1;
б) х rу Û у ^3 = х;	г) х rу Û у = sin x.

9. Привести пример отношения транзитивного, рефлексивного и симметричного.

10. Для каждого из следующих бинарных отношений выяснить, какими свойствами (рефлексивность, симметричность, антисимметричность, транзитивность) оно обладает. Дать обоснование ответа.

Отношения определены на множестве R:
а) х rу Û х ^2 = у ^2;	в) х rу Û у = | х |;
б) х rу Û х ^2 + у ^2 = 1;	г) х rу Û х ^2+ x = у ^2+ y.
Отношения определены на множестве Z:
а) х rу Û х £ у + 1;	б) х rу Û 3/(х – у).
Отношения определены на множестве всех прямых плоскости:
а) х rу Û х параллельна у;	б) х rу Û х пересекается с у.

Литература

1. Куликов, Л. Я. Сборник задач по алгебре и теории чисел / Л. Я. Куликов, А. И. Москаленко, А. А Фомин. – М.: Просвещение, 1993. – 288 с.

2. Иванов, Б. Н.  Дискретная математика. Алгоритмы и программы: учеб. пособие для вузов / Б. Н.  Иванов. – М.: Лаборатория базовых знаний, 2002. – 288 с.

3. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2005. – 304 с.

 

Практическое занятие № 3