Раздел 5. Отображения. Подстановки.
Тема 5.1 Отображения и их свойства.
Пусть XY – произвольные множества, если каждому элементу x из множества X (x ∈ X) ставится в соответствие элемент y ∈ Y, то говорят, что на множестве X задано отображение со значениями во множестве Y.
Пусть: X→Y либо f(x) = y.
Множество X – называется областью определения.
Множество Y – область прибытия.
Областью значений отображения f: X→Y называется множество f(X), состоящее из y ∈ Y, такого что y= f(x) для x ∈ X
f(X)={y| y ∈ Y, y= f(x), для x ∈ X }
Область значения всегда является подмножеством Y, но не всегда совпадает с ним f(X)≤Y
Существуют следующие способы задания отображений:
аналитический, то есть когда отображение задается в виде формулы;
словесный – описанием с помощью слов;
табличный
x |
|
|
y |
|
|
графический (график , диаграмма)
Свойства:
Отображение f: X→Y называется сюръекцией, если область прибытия совпадает с областью значений, то есть f(X)=Y или если для любого y ∈ Y J x ∈ X, такой что f(x)=y
X Y
Отображенное f: X→Y называется инъекцией, если для любых
,
таких что 
выполняется что значения соответствовать
этим аргументам не будут совпадать
А
если для 
X Y X Y
не
является инъекцией
Отображение f=X→Y называется биекцией, если оно является сюръекцией и инъекцией, или для любого элемента y ∈ Y существует и притом единственный x ∈ X, такой, что f(x)=y.
X
Y
Биекция также называется взаимно-однозначным отображением.
Самостоятельная работа №11.
Тема 5.2 Композиция отображений и обратное отображение.
Пусть f: X→Y а g:Y→Z, тогда композицией (произведением) отображений f и g называется новое отображение обозначается
g
f:
X→Z,
при этом выполняется
(g
f)(x)=g(f(x))
Свойства:
1.
композиция
отображений не коммутативно.
Пусть
,
2.
- ассоциативность.
Отображение
f:
X→Y
является биекцией тогда обратным
отображением, когда
такое что
Тема 5.3 Подстановки. Обратные подстановки. Формула количества подстановок.
Взаимооднозначное отображение множества {1,2,3, …,n} на само себя называется подстановкой n чисел, где n – степень подстановки.
Обычно подстановку записывают в виде двух строк, заключенных в скобки. При этом в первой строке аргументы (первые координаты), а во второй строке в соответствующие им образы (вторые координаты).
Общая формула количества подстановок:
Если степень подстановки =n – то количество подстановок: n!
Из всех подстановок выделяют так называемую тождественную подстановку.
Если
подстановка
имеет
вид
,
то симметричная ей подстановка
получается если поменять местами строки
подстановки
Произведением
подстановок
и
называется новая подстановка
,
полученная путем применения сначала
подстановки
,
затем подстановки
.
Свойства:
1.
- произведение подстановок не коммутативно;
2.
3.
Подстановка называется четной, если общее число инверсий в ее строках, есть число четное, в противном случае подстановка называется нечетной.
Два числа образуют инверсию, если меньшее из них находиться правее большего.
Общее число инверсий определяют следующим образом:
определяем число инверсий для первой строки: для каждого числа подсчитываем количество чисел, меньше чем оно и стоящих правее его.
определяем число инверсий для второй строки: для каждого числа подсчитываем количество чисел, меньше чем оно и стоящих правее его.
складываем полученные значения.
1.
2.
3.
9
– нечетное, следовательно
– нечетная подстановка.
Циклом
называется такая подстановка, каждый
элемент
переходит
в элемент
,
переходит
в элемент
,
…,
переходит
в элемент
,
переходит
в элемент
Цикл длины два называется транспозицией.
Любую подстановку можно представить в виде произведения независимых циклов.
Цикл длины один разрешается опускать в разложении подстановки в виде произведений.
Обозначим m – число независимых циклов: m=3.
Декрементом (d) называется разность n – m, где n – степень подстановки, m – количество независимых циклов. Четность подстановки совпадает с четностью ее декремента:
-
нечетная подстановка.
Методика решения уравнений с подстановками:
1.
,
где
- известные подстановки, х
– неизвестная подстановка.
2.
,
где
-
известные подстановки, х
– неизвестная подстановка
3.
