Пояснение к работе

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

Тема: «Бинарные отношения»

Цель занятия:

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

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какие способы задания бинарного отношения вы знаете?

Что является областью определения бинарного отношения r?

Что является областью значений бинарного отношения r?

Какое отношение r называется рефлексивным на множестве X?

Какое отношение r называется симметричным на множестве X?

Главная диагональ матрицы какого отношения содержит только единицы?

Для какого отношения r всегда выполняется условие r = r – 1?

Для какого отношения r всегда выполняется условие r r Í r.

2. Дать определение следующих понятий:

– бинарное отношение;

– композиция отношений.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

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

Бинарным отношением 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 = }.

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

Отношение r называется рефлексивным на множестве X, если для любого x Î X выполняется xrx. Из определения следует, что всякий элемент (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 из xry следует yr 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 из xry и yrz следует xrz. Одновременное выполнение условий xry, yrz, xrz означает, что пара < 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 с.

Дата добавления: 2017-02-01