Практическое занятие №6. Отображения и отношения

Цель занятия:	1.	изучить виды и суперпозиции отображений; виды отношений, заданные на множествах;
	2.	получить навыки в вычислении декартового произведения.

Элементы теории

 

Пусть X и Y - два множества. Если каждому элементу x множества X поставлен в соответствие некоторый элемент f(x) множества Y, то говорят, что задано отображение f из множества X в множество Y.   Обозначение: f: X ® Y.

При этом, если   f(x) = y, то элемент y называется образом элемента x при отображении f, а элемент x называется прообразом элемента y при обратном отображении f ^-1.

 

Отображение f: X ® Y является сюръективным, если каждый элемент yÎY имеет хотя бы один прообраз.

 

Отображение f: X ® Y называется инъективным, если для любого элемента yÎY существует не более одного прообраза. Если отображение f сюръективно и инъективно одновременно, то оно называется биективным (взаимно однозначным соответствием).

 

Пусть f: X ® Y и g: Y ® Z - два отображения. Зададим правило h, применение которого к элементу x из X состоит в том, что мы применяем к x правило f, затем к результату f(x) применяем второе правило g, получая в итоге g(f(x)). То есть h(x) = g(f(x)). Полученное отображение h: X ® Z называют композицией отображений g и f и обозначают h = g ° f. Тогда g ° f(x) = g(f(x)).

Декартово произведение двух множеств А и В - множество упорядоченных пар <a, b> таких, что aÎA и bÎB. Мощность декартова произведения равна произведению мощностей исходных множеств.

Бинарное отношение множеств А и В - подмножество декартового произведения А на В. Область определения отношения (левая область отношения) - множество всех первых элементов пар отношения. Область значений отношения (правая область отношения) - множество всех вторых элементов пар отношения.

Рефлексивное отношение на множестве А - отношение, которое справедливо для каждого элемента множества А как отношение этого элемента к самому себе. Например =, ³ - рефлексивные, ¹, > - нерефлексивные.

Симметричное отношение - отношение, результат которого не меняется при перестановке операндов.

Транзитивное отношение на множестве А - такое отношение, из справедливости которого для первого и второго операнда и справедливости для второго и третьего операнда следует справедливость этого отношения для первого и третьего операндов, при условии, что все операнды являются любыми элементами множества А.

Отношение эквивалентности - отношение, являющееся одновременно рефлексивным, симметричным и транзитивным.    

Класс эквивалентности R - набор элементов множества, для которых эквивалентное отношение R будет давать одинаковый результат.

 

Примеры выполнения заданий

1. Для отображения f: {0,1,3,4} ® {2,5,7,8}, заданного рисунком, найдите f({0,3}), f({1,3,4}), f ^– 1 (2), f ^– 1 ({2,5}), f ^–1 ({5,8}).   Решение: f ({0,3}) = {5, 8};              f ({1,3,4}) = {5, 7};              f ^- 1 (2) = {Æ};              f ^- 1 ({2,5}) = {3, 4};                f ^- 1 ({5,8}) = {0, 3, 4}

0           2   1           5   3           7   4           8

2. Выясните, к какому типу относится заданное отображение f:

A = {a, b, c}; B = {2, 4, 6, 8}; f: a ® 2; b ® 4; b ® 6; c ® 8;  

Решение: находим образы: y = f (x):   f (a) = 2; f (b) = {4, 6}; f (c) =8

Находим прообразы: x = f ^--1 (y): f ^-1 (2) = a; f ^-1 (4) = b; f ^-1 (6) = b; f ^-1 (8) = c;

Все элементы В имеют прообразы, значит f – сюрьективно.

Т.к элементы 4 и 6 имеют равные прообразы, то f – неинъективно,

 Следовательно, заданное отображение не является биективным.

3. Пусть f: {1,2,3,5} ® {0,1,2}, g: {0,1,2} ® {3,7,9,13}, h: {3,7,9,13} ® {1,2,3,5} – отображения, показанные на рисунке:

 

f: 1             0   2             1   3             2    5

g: 0              3   1              7   2              9                 13

h: 3              1   7              2   9              3   13             5

 

Нарисуйте композиции отображений:

 

а) g(f); б) h(g); в) h(f (g));

 

Решение:

 

а) f (g); 1               3   2               7   3               9   5            13

б) g(h; 0 )       1   1              2   2              3                 5

в) h(f); 3              0   7              1   9              2   13

в) h(f(g)); 3              3   7              7   9              9   13          13

4.Установите биективное отображение между множеством
A={1, 6, 11, 16, 21,...} и натуральным рядом чисел.

Решение: поставим в соответствие элементу натурального ряда "n" n↔1+5(n-1), т.е. a_n=1+5(n-1) ÎA

Задания для самостоятельного выполнения

 

1. Для отображения f: {10,20,30,40} ® {а,б,в,г}, заданного рисунком, найдите f({10,40}), f({10,20,30}), f - 1(б), f - 1 ({а,в}), f - 1 ({б,в,г}).

 

0) 10         а   20         б   30         в   40        г	1) 10         а   20         б   30         в   40        г	2) 10         а   20         б   30         в   40        г	3) 10         а   20         б   30         в   40        г	4) 10         а   20         б   30         в   40        г
5) 10         а   20         б   30         в   40        г	6) 10         а   20         б   30         в   40        г	7) 10         а   20         б   30         в   40       г	8) 10         а   20         б   30         в   40       г	9) 10         а   20         б   30         в   40       г

2.Найдите декартово произведение множеств С = А ´ В:

0) A={1,2,3}; В={7,8,9};	1) A={2,3,4,9}; В={1,7};
2) A= {1,7}; В ={2,4,6,8}	3) A={3,5,10}; В={2,8,9};
4) A={2,3,4,5}; В ={6,10}	5) A={5,6}; В={1,7,9,2};
6) A={10,1,2}; В={1,2,8};	7) A={10,11,12}; В={2,8,9};
8) A={6,9}; В={1,2,3,5};	9) A={2,3,5,6}; В={9,12};

3. Вычислите мощность множеств:

0) В={xÎN | x£41,  x–квадрат числа} A={xÎR | (x^2 + x +1)×(x^2–x–6)=0}	1) В={xÎN | x – делитель 40} A={xÎR | (x^2 – x –2)×(x^2–x–20)=0}
2) В={xÎN | x – делитель 81} A={xÎR |(x^2+x –2)×(x^2–7x +6)=0}	3) В={xÎN |x£51, x–квадрат числа} A={xÎR |(x^2–3x–4)×(x^2–9x+20)=0}
4) В={xÎN |x£65, x–квадрат числа} A={xÎR |(x^2–6x+5)×(x^2–x–12)= 0}	5) В={xÎN | x – делитель 54} A={xÎR |(x^2–5x–6)×(x^2–5x+4) = 0}
6) В={xÎN | x – делитель 36} A={xÎR |(x^2+3x–4)×(x^2+x–12)=0}	7) В={xÎN |x£64, x–квадрат числа} A={xÎR|(x^2+4x–5)×(x^2–7x+12)= 0}
8) В={xÎN |x£78, x–квадрат числа} A={xÎR |(x^2–3x+2)×(x^2–4x–5)= 0}	9) В={xÎN | x – делитель 32} A={xÎR | (x^2–5x+6)×(x^2+x–20)= 0}

4. Пусть A = {1, 2, 3}. Установите, является ли каждое из приведенных ни­же отношений R, заданных на множестве А, отношением эквивалентности.

а) R₁ = {(2,2), (1,1), (1,2)};

б) R₂ = {(1,1), (2,2), (3,3)};

в) R₃= {(1,1), (2,2), (3, 3), (1,2), (2,1), (3,1), (1, 3),(3,2),(2,3)};

г) R₄ = {(1,1),(2,2),(3,3),(1,2),(3,2),(2,1)};

д) R₅ = {(1,1),(1,2),(3,3),(2,2),(3,2),(2,3),(2,1)};

е) R₆ = {(1,1),(1,3),(2,3),(1,2),(3,2),(2,1)};