Материал: 5540

Так как отношения на М задаются подмножествами, R M1 M 2

(или R M 2 , если М1 = М2 = М), для них определены те же операции, что

инад множествами.

1.Объединение R1 R2 :

21

7. Транзитивное замыкание R0.

Транзитивное замыкание R0 состоит из таких и только таких пар элементов a, b из М, т.е. (a, b) R0 , для которых в М существует цепочка из (k + 2) элементов М, k ≥ 0: a, c1, c2, …, ck, b, между соседними элементами которой выполняется R: aRc1, c1Rc2, …, ckRb, т.е.:

R0 (a, b) (a, c1), (c1, c2 ), ..., (ck , b) R .

Унарная операция транзитивного замыкания R0 может быть также определена как бесконечное объединение:

правнуком» и т.д. Тогда объединение всех этих отношений есть транзитивное замыкание R0 – «Быть прямым потомком».

Если отношение R транзитивно, то R0 = R. Например, транзитивное замыкание отношения R – «Быть больше» совпадает с этим отношением, т.е. R0 = R.

8. Рефлексивное замыкание R*.

Пусть тождественное отношение Е (a, а) a М . Тогда если R

транзитивно и рефлексивно, то R* = R.

Пример 1.10. Пусть отношение R – «Быть руководителем», определённое на множестве сотрудников организации М. Назовите отношения: R , R-1, R0, R*.

«Быть руководителем, в том числе по отношению к самому себе».

Пример 1.11. Пусть на множестве М = {2, 4, 6} определено отношение R – «Быть меньше». Задайте характеристическим свойством и списком отношение R, обратное отношение R-1 и дополнение R . Сравните отношения. Определите их свойства.

22

R-1 = {(4, 2), (6, 2), (6, 4)}.

R (М М ) \ R (a, b) (a, b) R(a, b) a b – «Быть не меньше».

R = {(2, 2), (4, 2), (4, 4), (6, 2), (6, 4), (6, 6)}.

Между R, R-1 и R имеют место соотношения:

Отношения R и R-1 – антирефлексивны, антисимметричны, транзитивны, т.е. являются отношением строгого порядка. Эти отношения задают полный порядок на множестве М.

Отношение R – рефлексивно, антисимметрично, транзитивно, т.е. является отношением нестрогого порядка; оно также задаёт полный порядок на множестве М.

Задача 1.13. Назвать отношения R , R-1, R(2), R0, R*, если отношение R означает:

а) «Быть братом»; б) «Быть сыном»;

в) «Жить в одном городе».

Задача 1.4. Пусть на множестве М = {1, 2, 3, 4} определено отношение R – «Быть больше». Выполнить операции над отношением R; задать полученные в результате операций отношения характеристическим свойством, списком, а также назвать отношения. Сравнить отношения; определить их свойства.

23

1.4 Соответствия

Соответствие – способ задания взаимосвязей, взаимодействий между элементами множества (наряду с отношениями).

1. Всюду (полностью) определённое соответствие – если np1G = A.

Частично определённое соответствие – в противном случае. 2. Сюръективное соответствие – если np2G = В.

Образом элемента а в множестве В при соответствии G называется множество всех b В , соответствующих элементу a А. Прообразом элемента b в множество А при соответствии G называется множество всех a А, которым соответствует b В .

Образом множества С np1G называется объединение образов всех элементов a C . Прообразом множества D np2G называется объединение прообразов всех элементов b D .

24

3.Функциональное (однозначное) соответствие – если образом любого элемента а из области определения np1G является единственный элемент b из области значений np2G.

4.Взаимно-однозначное соответствие – если оно:

а) всюду определено; б) сюръективно; в) функционально;

г) прообразом любого элемента b из области значений np2G является единственный элемент а из области определения np1G.

Если между множествами А и В существует взаимно однозначное соответствие, то мощности этих множеств равны, т.е. А В . В таком случае говорят, что множества А и В равномощны. Этот факт позволяет:

–установить равенство мощностей двух множеств, не вычисляя этих множеств;

–вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.

Множества, равномощные множеству натуральных чисел N, называются счётными.

Пример 1.12. Пусть G – множество всех пар действительных чисел (х, у), удовлетворяющих соотношению (х – 3)2 + (у – 2)2 ≤ 1. Графически такое соответствие G представляет собой круг радиуса 1 с центром в точке (3; 2). Таким образом, круг G задаёт соответствие между R и R (осью абсцисс и осью ординат, рисунок 1.9).

у

4

2

1

Рисунок 1.9 – Соответствие между R и R

25