Дискретная математика - Функции

А Functionназначает каждому элементу набора ровно один элемент связанного набора. Функции находят свое применение в различных областях, таких как представление вычислительной сложности алгоритмов, подсчет объектов, изучение последовательностей и строк, и многие другие. Третья и последняя глава этой части освещает важные аспекты функций.

Функция - Определение

Функция или отображение (определяемое как $ f: X \ rightarrow Y $) - это отношение между элементами одного набора X и элементами другого набора Y (X и Y - непустые множества). X называется доменом, а Y называется доменом функции 'f'.

Функция 'f' - это отношение на X и Y такое, что для каждого $ x \ in X $ существует единственный $ y \ in Y $, такой что $ (x, y) \ in R $. «x» называется прообразом, а «y» - изображением функции f.

Функция может быть один к одному или многие к одному, но не один ко многим.

Инъективная / Индивидуальная функция

Функция $ f: A \ rightarrow B $ является инъективной или взаимно однозначной, если для каждого $ b \ in B $ существует не более одного $ a \ in A $, такое что $ f (s) = t $ .

Это означает функцию f инъективно, если из $ a_1 \ ne a_2 $ следует $ f (a1) \ ne f (a2) $.

пример

$ f: N \ rightarrow N, f (x) = 5x $ инъективно.
$ f: N \ rightarrow N, f (x) = x ^ 2 $ инъективно.
$ f: R \ rightarrow R, f (x) = x ^ 2 $ не является инъективным, поскольку $ (- x) ^ 2 = x ^ 2 $

Сюръективная функция / функция

Функция $ f: A \ rightarrow B $ сюръективна (на), если изображение f равно ее диапазону. Эквивалентно, для каждого $ b \ in B $ существует некоторый $ a \ in A $ такой, что $ f (a) = b $. Это означает, что для любого y в B существует некоторый x в A такой, что $ y = f (x) $.

пример

$ f: N \ rightarrow N, f (x) = x + 2 $ сюръективно.
$ f: R \ rightarrow R, f (x) = x ^ 2 $ не является сюръективным, поскольку мы не можем найти действительное число с отрицательным квадратом.

Биективный / индивидуальный корреспондент

Функция $ f: A \ rightarrow B $ биективна или взаимно однозначно соответствует тогда и только тогда, когда f является одновременно инъективным и сюръективным.

Проблема

Докажите, что функция $ f: R \ rightarrow R $, определенная как $ f (x) = 2x - 3 $, является биективной функцией.

Explanation - Мы должны доказать, что эта функция инъективна и сюръективна.

Если $ f (x_1) = f (x_2) $, то $ 2x_1 - 3 = 2x_2 - 3 $ и это означает, что $ x_1 = x_2 $.

Следовательно, f есть injective.

Здесь $ 2x - 3 = y $

Итак, $ x = (y + 5) / 3 $, который принадлежит R, и $ f (x) = y $.

Следовательно, f есть surjective.

поскольку f оба surjective и injective, мы можем сказать f является bijective.

Обратная функция

В inverse взаимно однозначно соответствующей функции $ f: A \ rightarrow B $, является функция $ g: B \ rightarrow A $, обладающая следующим свойством:

$ f (x) = y \ Leftrightarrow g (y) = x $

Функция f называется invertible, если существует обратная к нему функция g.

пример

Функция $ f: Z \ rightarrow Z, f (x) = x + 5 $, обратима, поскольку она имеет обратную функцию $ g: Z \ rightarrow Z, g (x) = x-5 $.
Функция $ f: Z \ rightarrow Z, f (x) = x ^ 2 $ не является обратимой, поскольку она не взаимно однозначна, поскольку $ (- x) ^ 2 = x ^ 2 $.

Состав функций

Две функции $ f: A \ rightarrow B $ и $ g: B \ rightarrow C $ могут быть составлены для получения композиции $ gof $. Это функция от A до C, определяемая формулой $ (gof) (x) = g (f (x)) $

пример

Пусть $ f (x) = x + 2 $ и $ g (x) = 2x + 1 $, найдите $ (fog) (x) $ и $ (gof) (x) $.

Решение

$ (туман) (x) = f (g (x)) = f (2x + 1) = 2x + 1 + 2 = 2x + 3 $

$ (gof) (x) = g (f (x)) = g (x + 2) = 2 (x + 2) + 1 = 2x + 5 $.

Следовательно, $ (fog) (x) \ neq (gof) (x) $

Некоторые факты о композиции

Если f и g взаимно однозначны, то функция $ (gof) $ также взаимно однозначна.
Если f и g включены, то функция $ (gof) $ также включена.
Композиция всегда обладает ассоциативным свойством, но не обладает коммутативным свойством.