Алгебра и теориячисел. Толстиков А.В.
Курс 1. Семестр 1. Практическое занятие 2. Отношения эквивалентности и порядка. Отображения
.
Теоретические вопросы
Отношение эквивалентности. Классы эквивалентности и их свойства. Фактор множество и разбиение и связь между ними. Отношения порядка, строгого порядка, линейного порядка, упорядоченное множество, линейно упорядоченное множество, максимальный и минимальный элементы множества, ограниченное множество. Наибольший и наименьший элементы. Функциональные отношения. Отображения. область определения отображения, область значений отображения, равенство отображения, композиция отображений и ее свойства, единичное отображения, график отображения, граф отображения. Виды отображений. Отображения на (сюръективное отображение), взаимно-однозначное отображение в (инъекция), взаимно-однозначное отображение на (биекция). Взаимно обратные отображения. Обратное отображение и условие его существования.
Задачи для решения на занятии и дома
1. Для каждого и следующих бинарных отношений, на множестве найти область определения, область значений, изобразить его график, установить свойства (рефлексивность, симметричность, антисимметричность, транзитивность):
a) xr y Û | x | = | y |; b) xr y Û x 2 + y 2 =4; с) xr y Û x 2 = y; d) xr y Û x = y 2;
e) xr y Û xy ³ 0; f) xr y Û x = tg y; g) xr y Û x - y =3 k, k Î Z; h) xr y Û [ x ] = [ y ].
2. Докажите, что для любых трех бинарных отношений r, s, t, определенных на множестве, справедлив ассоциативный закон: 
.
3. Для каждого из бинарных отношений из 5 найти обратное бинарное отношение.
4. Для данных бинарных отношений r и s на множестве A = {1, 2, 3, 4} написать таблицы отношений 
, 
, r -1, s -1 и построить их графы.
a) r = {(a, b) Î A 2 | a + b - четное число}, s = {(a, b) Î A 2 | a M b }; b) r = {(a, b) Î A 2 | a > b }, s = {(a, b) Î A 2 | (a - b) M 2};
a) r = {(a, b) Î A 2 | a - b = 1}, s = {(a, b) Î A 2 | ab > 7}.
5. Найти композиции и бинарных отношений r и s, определенных на множестве R:
a) xr y Û x 2 = y xr y Û | x | £ | y |, xs y Û x 2 + y 2 =4; b) xr y Û xy > 0; xs y Û x - y =0; c) xr y Û | x | = | y |, xr y Û x 2 +2 y = 5.
6. Ввести во множестве пар линейно упорядоченного множества линейный порядок.
1. Пусть A = {1, 2, 3, 4, 5}, B = {1, 2, 3, 4}. Для каждого из данных бинарных отношений f установить является ли оно отображением множества A в B? Найти E (f). Построить граф f. Установить вид отображения f. Если f не является отображением, то сузить f так, чтобы сужение стало отображением.
a) f = {(1, 1), (2, 1), (3, 2), (4, 1), (5, 3)}; b) f = {(1, 1), (4, 2), (5, 1), (3, 3), (2, 4)}; c) f = {(3, 2), (4, 2), (5, 1), (3, 3), (2, 3), (1, 4)}; c) f = {(1, 3), (2, 4), (5, 3), (3, 2), (4, 1)}; d) f = {(1, 3), (3, 4), (5, 3), (4, 2), (4, 3).
2. Для каждого из данных бинарных отношений f установить является ли оно отображением множества R в R? Найти E (f). Построить график. Установить вид отображения f. Если f не является отображением, то сузить f так, чтобы сужение стало отображением.
a) f = {(x, y)Î R 2| x × y = 1}; b) f = {(x, y)Î R 2| y 3= x 2 - 2 xy -7}; c) f = {(x, y)Î R 2| y = 2sin(2x - 1} -1; d) f = {(x, y)Î R 2| y = 2arcctgx}; e) f = {(x, y)Î R 2| | y |= | x |}; f) f = {(x, y)Î R 2| y = x3 + 1}.
3. Докажите, что каждое бинарное отношение f является отображением. Найти E (f) и образ множества f (A). Является ли f сюръекцией? Является ли f инъекцией?
a) f = {(x, y)Î R 2| y = 2arcctgx}, A = [0, 1]; b) f = {(x, y)Î R 2| y = - x 3 + 1}, A = [-2, 1]; c) f = {(x, y)Î R 2| y = 2cos x +1}, A = [0, p/2]; d) f = {(x, y)Î R+ ´ R | y = ln x }, A = (0, e 2); e) f = {(x, y)Î R 2| y = 2 x - 1 - 3}, A = [1, 2].
4. Для данных множеств X и Y построить такие отображения f, g, h, e X ® Y, что f - не инъекция, не сюръекция, g - инъекция, но не сюръекция, h - сюръекция, но не инъекция, e - биекция.
a) X = Y = R; b) X = R +È{0}, Y = R; c) X = R +, Y = R +; d) X = R, Y = (0, 1); e) X = [0, 1], Y = (1, 2); c) X = (0, 2), Y = R.
5. Для данных отображений f и g R ® R найти композиции 
, 
.
a) f: x ® sin2 x, g: x ® arctg x; b) f: x ® x 2 + 1, g: x ® x 3 + 1; c) f: x ® 2 x, g: x ® log4(| x | +1); d) f: x ® x 2, g: x ® cos x; e) f: x ® tg2 x, g: x ® arctg x.
1.4.6. Для каких отображений f существует обратное отображение f -1. Найти f -1, построить графики f и f -1. Если обратное отображение f -1 не существует, то так сузить X и Y, чтобы f стало обратимым.
a) f: x ® sin2 x, X = Y = R; b) g: x ® arctg x, X = Y = R; c) f: x ® x 3 + 1, X = Y = R; d) f: x ® 2 x; X = Y = R; e) f: x ® log4(| x | +1); X = Y = R; f) f: x ® 1/ x; X = Y = R \{0}; g) f: x ® (x - 1)/(x +2), X = R \{-2}, Y = R.
7. Пусть X = R 2, Y = R 2 , f - преобразование симметрии плоскости x O y относительно оси O y, g - преобразование гомотетии плоскости x O y с центром в начале координат и коэффициентом k =2. Найти образы множества при преобразованиях f, g, , .
a) A = {(x, y)Î R 2| 2 x - 3 y = 6}; b) A = {(x, y)Î R 2| (x - 3)2+ (y - 1)2 = 4}; c) A = {(x, y)Î R 2| y = (x - 4)2}.
8. Пусть A = {1, 2, 3}, B = {1, 2}. a) Перечислить все отображения множества A в B. Сколько среди них сюръекций? b) Перечислить все отображения множества B в A. Сколько среди них инъекций? c) Перечислить все отображения множества A в A. Сколько среди них биекций?
9. Пусть | A | = m, | B | = n.
a) Сколько существует различных отображений множествами A в B?
b) При каких n и m существует инъекции A в B? Сколько существует различных инъекций?
c) При каких n и m существует биекции A в B? Сколько существует различных биекций A в B?
d) При каких n и m существует обратимые отображения A в B? Сколько существует различных обратимых отображений A в B?
e) При каких n и m существует сюръекции A в B? Сколько существует различных сюръекций*?
1.4.10. Постройте алгоритм, который позволяет по матрице бинарного отношения определить является оно отображением и установить вид отображения.
1.4.11. Постройте алгоритм, который позволяет создавать случайную матрицу бинарного отношения, имеющего заданный вид.
Задание на дом: Учить тему отображения.