Материал: Дискретная математика. учебное пособие. Собенина О.В

Задачи и упражнения

1. Даны множества Х₀={1,2,3,4,5,6}, X₁={1,2,3,4}, X₂={2,3,4,5}, X₃={2,3,4}, X₄={3,4,5}, X₅={2,3}, X₆={3,4}, X₇={4,5}, X₈={2,4}. Сформируйте частичный порядок на этих множествах.

2. Пусть Х - множество всех прямых на плоскости. Являются ли эквивалентными отношения а) параллельности прямых и б) перпендикулярности прямых?

3. Приведите пример четырех различных рефлексивных отношений на множестве .

4. Приведите пример трех различных отношений на множестве , не являющихся рефлексивными.

5. Приведите пример двух различных симметричных отношений и двух различных, не являющихся симметричными, на множестве .

6. Приведите пример двух различных транзитивных отношений и двух различных, не являющихся транзитивными, на множестве .

7. Приведите пример частичного порядка и пример отношения, не являющегося частичным порядком.

8. Приведите пример множества и двух различных эквивалентностей на нем.

9. Приведите пример множества и двух различных частичных порядков на нем.

10. Определите свойства следующих отношений, заданных на множестве действительных чисел (R)

а) R={(x,y)| x,yR и x - y<0},

в) R={(x,y)| x,yR и 2x 3y},

с) R={(x,y)| x,yR и |x| | y|}.

11. Найдите , , , для отношений

а) R={(x,y) | x,yN и x, делит y},

в) R={(x,y)| x,yR и x + y<0},

с) R={(x,y)| x,yR и 2x 3y}.

12. Докажите, что если отношения R₁ и R₂ рефлексивны, то рефлексивны следующие отношения , , , .

13. Докажите, что если отношения R₁ и R₂ симметричны, то симметричны следующие отношения , , , .

Рис. 2.5

14. Докажите, что если R эквивалентность, то есть также эквивалентность.

15. Докажите, что – эквивалентность тогда и только тогда, когда .

16. Для отношения, заданного матрицей, определить является ли оно отношением эквивалентности. Если является, то определить классы эквивалентности.

3. Функции, отображения и операции

Рассмотрим два множества X и Y. Если для каждого элемента указан элемент , то говорят, что между множествами X и Y установлено соответствие. Обозначим его через Г. Тогда Г состоит из множества упорядоченных пар (x, y), таких, что и y Y : Г . При этом совершенно необязательно, чтобы в сопоставлении участвовали все элементы множества X и Y.

Образом элемента x при соответствии Г называется множество Im(x), такое что

Im(x)={y (x,y) }.

Прообразом элемента y при соответствии Г называется множество

Coim(y)={x (x,y) }.

Областью значений соответствия Г называется множество

Областью определения соответствия Г называется множество .

Для каждого соответствия существует обратное соответствие , которое любому y Y сопоставляет x X, причем ={(y,x) (x,y) }.

Отображением (однозначным) называется такое соответствие, которое каждому х Х сопоставляет единственный элемент у Y . При отображении соответствие между х и у записывается в виде у = (x), a само отображение определяет запись : X Y, при этом Х называется областью определения отображения, Y – областью значений.

Два отображения : X Y , и : X Y равны, если для всех х Х, X =X ,Y =Y и = .

Отображение называется многозначным, если некоторым значениям х Х соответствуют подмножества Y Y, состоящие более чем из одного элемента.