Соответствия и функции

1. Дискретная математика

2.

Соответствия и функции
Соответствием множеств А и В
называется подмножество G такое, что G A B.
Если (a, b) G, то говорят, что
“b соответствует a при соответствии G”.
Область определения соответствия G –
множество пр1 G A.
Область значений соответствия G –
множество пр2 G B.

3.

• Соответствие G называется всюду
(полностью) определенным – если пр1 G =
А (в противном случае – частично
определенное соответствие).
• Соответствие G называется
сюрьективным, если пр2 G = B.

4.

• Образ элемента a в множестве B при
соответствии G – это множество всех
элементов b B которые соответствуют
a A.
Прообраз элемента b в множестве А при
соответствии G – это множество всех a A,
которым соответствует b B .
• Образом множества C пр1 G называется
объединение образов всех элементов С.

5.

• Прообразом множества D пр2 G
называется объединение прообразов всех
элементов D.
• Соответствие G называется
функциональным (однозначным)
соответствием, если образом любого
элемента из пр1 G является единственный
элемент из пр2 G.

6.

• Соответствие G называется инъективным
соответствием, если прообразом любого
элемента из пр2 G является единственный
элемент из пр1 G.
• Соответствие F является функцией типа
F : A B , если оно функционально
(однозначно) F ( a ) b.

7.

• Соответствие G является отображением
множества А в множество В, если оно
функционально и полностью определено.
• Соответствие G является взаимно
однозначным, если оно:
1) всюду определено; 2) сюрьективно;
3) функционально; 4) инъективно.

8.

• Преобразованием множества А
называется отображение типа A A.
• Функция типа A1 A2 ... An B называется
n-местной функцией ( f (a1 , a2 ,..., an ) b).
• Соответствие H A B называется
обратным к G A B , если Н таково, что
(b, a) H (a, b) G.

9.

• Если соответствие, обратное к функции
f : A B является функциональным, то оно
называется функцией, обратной к f, ( f 1 ).
• Пусть дана функция f : A B.
Соответствие ( f 1 ) является функцией
тогда и только тогда, когда f инъективна, и
является отображением тогда и только
тогда, когда f инъективна и сюрьективна
(т.е. биективна).

10.

• Утверждение: Для функции f : A B
существует обратная функция ( f 1 ) тогда и
только тогда, когда f является
взаимнооднозначным соответствием между
своей областью определения и областью
значений.

11.

• Пусть даны функции f : A → B и g : B → C
• Функция h : A → C называется композицией
функций f и g, если h( x) g ( f ( x)), x ∈ A
(обозначение h f g ). Часто говорят, что
h получена подстановкой f в g.

12.

f :A B
Для многоместных функций
и g : B n C возможны различные варианты
подстановки f в g, задающие функции
различных типов. Например, при
m 3 и n 4 функция B A3 B 2 C
имеет 6 аргументов и.
m
h g (b1 , f (a1 , a2 , a3 ), b3 , b4 )

13.

• Для множества многоместных функций
m
m
f
:
A
→ A возможны
f
:
A
→
A
,
,
типа 1
n
любые подстановки функций друг в друга,
а также любые переименования
аргументов.
• Например, переименование x3 в x2 из
функции четырёх аргументов порождает
функцию трёх аргументов:
1
n
f ( x1 , x2 , x2 , x4 ) f ( x1, x2 , x4 )

14.

• Функция, полученная из функций f1 , , f n
некоторой подстановкой их друг в друга и
переименованием аргументов, называется
суперпозицией функций f1 , , f n .
• Выражение, задающее эту суперпозицию и
содержащее функциональные знаки, скобки
и символы аргументов, называется
формулой.

15. Взаимно однозначные соответствия и мощность множеств

• Утверждение (о взаимно однозначном
соответствии равномощных множеств):
Если между конечными множествами А и В
существует взаимно однозначное
соответствие, то А В.

16.

• Этот факт:
• 1) позволяет установить равенство
мощностей двух множеств, не вычисляя
мощностей этих множеств;
• 2) дает возможность вычислить мощность
множества, установив его взаимно
однозначное соответствие с множеством,
мощность которого известна или легко
вычисляется.