- •М а т е м а т и к а дискретная математика
- •Содержание
- •Предисловие
- •1. Разбор типичных задач
- •Элементы теории множеств Множества. Операции над множествами
- •Отображения. Инъективные и сюръективные отображения
- •Отношение эквивалентности
- •Элементы теории кодирования
- •10100.00000.01010.10011.01011.11100.10010.00101.10010.
- •00110.00101.01001.10000.01000.00000.11001.1.
- •00110.00101.01001.10000.01000.00000.11001.1.
- •Решение.
- •1.3. Элементы теории графов. Поиск путей в графе
- •Решение
- •X: 9331 4359 7162 5571 8352;
- •Решение.
- •Решение.
- •Решение.
- •Решение.
- •Решение.
- •Решение.
- •Решение.
- •Задачи о раскраске графа
- •Вопросы к экзамену
- •Основная
- •Дополнительная
Отображения. Инъективные и сюръективные отображения
Если указан закон, сопоставляющий каждому элементу множества А единственный элемент множества В, то говорят, что имеется однозначное отображение АВ.
Отображение АВ называется инъективным, если разные элементы множестваA переходят в разные элементы множества B: если а в, то .
Отображение АВ называется сюръективным, если каждый элемент множества В имеет свой прообраз в множестве А.
Если отображение одновременно инъективное и сюръективное, то оно называется биективным.
1. Пусть f: RR задано формулой f(x) = x2-1 (рис.3). Определить, является ли отображение f инъективным, сюръективным, биективным.
Область определения функции – R, область значений функции – [-1;+).
f – отображение. Если (х,у) f и (х,z) f , то y = z, так как (x,y)f, т.е. y = x2-1, (x,z)f, т.е. z = x2-1.
Найдутся х1, х2R, такие что х1 х2, но: f(x1) = f(x2), например, пусть х1 = 1, х2 = -1, тогда f(x1) = 0 и f(x2) = 0, т.е. х1 х2, а f(x1) = f(x2). Таким образом, это неинъективное отображение.
Так как область значений функции [1;+ ) не совпадает сR, то отображение несюръективно.
2. Пусть f: RR задано формулой f(x) = x4. Является ли отображение инъективным, сюръективным?
Поскольку х1=2R, х2 = -2R, f(2) = f(-2) = 16, т.е. х1 х2, а f(x1) = f(x2), то отображение неинъективно.
Для любого xR не существует f(х), такого что f(х) = -16, так как х4 -16, поэтому отображение несюръективно.
3. Пусть отображение f: [0;+)[0;+) задано формулойf(x)=x2. Является ли оно инъективным, сюръективным?
Для любых х1, х2[0;+), х1 х2, f(x1)=x12, f(x2)=x22, но f(x1) f(x2), т.е для каждого х существует единственное f(x), следовательно, f(х) - инъективное отображение.
Для каждого значения f(x)[0;+) найдётся х[0;+), поэтомуf(х) - сюръективное отображение.
из 1. и 2. следует, что отображение биективно.
Отношение эквивалентности
Всякое подмножество Г декартова произведения АхА называется отношением на множестве А.
Отношение Г называют рефлексивным, если aГа для всех aA.
Отношение Г называют симметричным, если аГbbГа.
Отношение Г называют транзитивным, если аГb, bГааГс.
Если отношение рефлексивно, симметрично, транзитивно, то оно называется отношением эквивалентности.
1. Проверить, является ли D отношением эквивалентности на R, если D={(x;y)| sin x = sin y}.
D – рефлексивно, так как для любого R ()D, т.е. для любого xR имеем sin x = sin x.
D – симметрично, так как для любой пары (,)D имеем ()D, т.е. для любых R из (x,y)D следует, что sin x = sin y, тогда и sin y = sin x, следовательно, (y,x)D.
D – транзитивно, так как для любых а,b,cR из того что ()D и ()D следует, что ()D, т. е. если (x,y)D, то sinx=siny, если (y,z)D, то sin y = sin z, тогда sin x=sin z, следовательно, (x,z) D.
Из 1., 2., 3. следует, что D – отношение эквивалентности на R (где R – множество действительных чисел).
2. Упражнение. Выяснить, является ли отношением эквивалентности, если ху = {(x,y)| x = 3y}.