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

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

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

Функция или отображение (определенное как $ 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 $

Surctive / Onto function

Функция $ 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 $, является биективной функцией.

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

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

Следовательно, f инъективен .

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

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

Следовательно, f сюръективно .

Поскольку f одновременно сюръективен и инъективен , мы можем сказать, что f биективен .

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

Обратной к функции «один к одному» $ f: A \ rightarrow B $ является функция $ g: B \ rightarrow A $, обладающая следующим свойством:

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

Функция f называется обратимой , если существует ее обратная функция 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 $, найдите $ (туман) (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 $

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

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

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

  • Если f и g на, то функция $ (gof) $ также на.

  • Композиция всегда обладает ассоциативным свойством, но не обладает коммутативным свойством.