Пример 1. 1. Функции и отображения

Лекция 4. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

ФУНКЦИИ И ОТОБРАЖЕНИЯ

1. Функции и отображения.

Функции и отображения

Функцией называется функциональное соответствие. Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция имеет тип А®В (обозначается f: А ® В). Каждому элементу а из области определения функция f ставит в соответствие элемент b из области значений. Это обозначается f(а) = b. Элемент а - аргумент функции, элемент b - значение функции на а.

Отображением А в В называется всюду определенная функция f: А ® В. Отображением А на В называется всюду определенное и при этом сюръективное функциональное соответствие f: A ® B.

Отображение типа А ® А часто называют преобразованием множества А. Функция типа

А ® А, являющаяся отображением А на A, называется перестановкой на А

Таблица 1

	Обязательное свойство
Соответствие	функциональное	всюду определенное	сюръективное
Функция Отображение А в В Отображение А на В	+ + +	+ +	+

Функции f и g равны, если:

• их области определения - одно и то же множество А,

• для любого а Î А f (а) = g (а).

Функция типа f: А ₁´ А ₂´ … ´ А_п ® В называется п-местной. В этом случае принято считать, что функция имеет п аргументов: f (а ₁, …, а_n) = b, где а ₁ Î А ₁, …, а_n Î А_n, b Î B.

Пусть дано соответствие G Í A ´ В. Тогда соответствие H Í В ´ А называется обратным к G (обозначается G ^-1), если H таково, что (b, а) Î Н тогда и только тогда, когда (a, b) Î G.

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

Пусть даны функции f:A ® B и g:B ® C. Функция h:А ® С называется композицией функций f и g (обозначается f ◦ g), если имеет место равенство h (х) = g (f (x)), где х Î А.

Часто говорят, что функция h получена подстановкой f в g. Для многоместных функций f: А^т ® В, g: Вⁿ ® С возможны различные варианты подстановки f в g, дающие функции различных типов. Например, при т = 3 и п = 4 функция h = g (x ₁, f (у ₁, у ₂, у ₃), x ₃, x ₄) имеет шесть аргументов и тип В ´ A ³ ´ B ² ® С.

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

Способы задания функции:

• графиком;

• таблицей;

• формулой, описывающей функцию как суперпозицию других (исходных) функций;

• рекурсивной вычислительной процедурой.

Например, функция f (x) = 1 × 2 × 3 ×... × (х -1) × х = х! описывается рекурсивной вычислительной процедурой, задаваемой следующими правилами: 1) f (0) = 1; 2) f (х +1) = f (х) × (x +1).

Пример 1

Таблица выигрышей лотереи устанавливает соответствие G между парами чисел из N ´ N = N ²(серия, номер выигравшего билета) и множеством выигрышей М, т.е. G Í N ²´ M. Является ли заданное соответствие функцией, и если - да, то какой?

Ø Соответствие G Í N ²´ M, задаваемое таблицей выигрышей, является функциональным, так как для каждой указанной пары из N ²(серии, номера билета) определен конкретный (единственный) выигрыш из М. Таким образом, данное соответствие есть двухместная функция f: N ´ N ® М. Функция такого типа, не всюду определена, значит не является отображением. Более того, как правило, число выигравших билетов (мощность области определения пр₁ f) больше перечня наименований выигрышей (мощности области значений пр₂ f), поэтому данная функция не обладает единственностью прообраза. В силу сказанного f не является взаимно однозначным соответствием.

Таким образом, таблица выигрышей лотереи определяет функцию f: N ´ N ® М, которая не является отображением и тем более - взаимно однозначным соответствием.