Informatyka MIMUW

Funkcje

Ten fragment wykładu przypomina poznany już wcześniej materiał. Służy jedynie ustaleniu terminologii i notacji.

Funkcja o dziedzinie $X$ i przeciwdziedzinie $Y$ to dowolna relacja $f \subseteq X \times Y$ taka, że:

• $\forall x\in X \ \exists y \in Y \ \ \langle x,y \rangle\in f$

• $\forall x\in X \ \forall y_1,y_2\in Y \ \ (\langle x,y_1 \rangle\in f \wedge \langle x,y_2 \rangle\in f) \to y_1=y_2$

Pierwszy warunek mówi, że każdy element dziedziny ma jakąś wartość przypisaną funkcją $f$. Drugi, że taka wartość jest co najwyżej jedna (dowolne dwie są bowiem równe). W skrócie oba warunki możemy zapisać łącznie jako

$\forall x\in X \ \exists! y \in Y \ \ \langle x,y \rangle\in f,$

gdzie kwantyfikator $\exists!$ oznacza istnieje dokładnie jeden.

• Ważne jest
  • wykorzystanie wszystkich elementów dziedziny: każdemu elementowi dziedziny ...
  • i jednoznaczność: jest przyporządkowany dokładnie jeden element przeciwdziedziny,
• nie wyklucza to sytuacji, gdy np. dwóm elementom dziedziny przyporządkowany jest ten sam element przeciwdziedziny,
• nie każdy element przeciwdziedziny musi być wykorzystany, tzn. mogą istnieć takie elementy przeciwdziedziny, które nie są przyporządkowane żadnemu elementowi dziedziny,
• dziedzina i przeciwdziedzina mogą być tym samym zbiorem.

Notacja:

• Piszemy $f : X \longrightarrow Y$ lub $X \stackrel{f}{\longrightarrow} Y$ na oznaczenie funkcji o nazwie $f$, której dziedziną jest zbiór $X$, a przeciwdziedziną zbiór $Y$.
  • elementy dziedziny nazywamy argumentami funkcji
  • elementy przeciwdziedziny im przyporządkowane nazywamy wartościami funkcji.
• Piszemy $f(x) = y$ lub $f : x \mapsto y$ na oznaczenie tego, że funkcja $f$ elementowi $x$ przyporządkowuje element $y$
  • mówimy wtedy, że $y$ jest wartością funkcji $f$ na argumencie $x$.
• Często podaje się przepis na funkcję, wykorzystując
  • operacje arytmetyczne: $f(x) = 3x + 7$
  • lub inne powszechnie znane funkcje $g(x) = 2\sin(x)\cos(x)$.
• W powyższych przykładach dziedziny i przeciwdziedziny można się domyślić (zapewne liczby rzeczywiste), ale dla ścisłości powinno się je podać, np. $f : \mathbb{R} \longrightarrow \mathbb{R}$.

Przykłady funkcji

Najczęściej będziemy się zajmowali funkcjami, które działają na liczbach (dziedziną i przeciwdziedziną będą zbiory liczbowe, np. $\mathbb{N}, \mathbb{R}$), ale można mówić o funkcjach na różnych zbiorach.

• $f : \mathbb{N} \ni n \mapsto 2n \in \mathbb{N}$,
  • jest zwartym zapisem, że $f$ jest funkcją postaci $f : \mathbb{N} \longrightarrow \mathbb{N}$
    daną przepisem $f(n) = 2n$
  • jako przeciwdziedzinę określiliśmy zbiór liczb naturalnych,
    ale w istocie wartościami tej funkcji są tylko liczby parzyste
• $g : \mathbb{N} \longrightarrow \mathbb{R}, \ g(n) = n/2$,
  • określenie $g : \mathbb{N} \longrightarrow \mathbb{N}$ nie byłoby tu prawidłowe, gdyż wartość $n/2$ nie zawsze jest liczbą naturalną
• $h : \mathbb{N} \longrightarrow {\{ {13} \}\ }, \ h(n) = 13$,
  • to też jest poprawnie określona funkcja, mimo że niezbyt frapująca (tzw. funkcja stała)
• $f : \mathbb{N} \longrightarrow \mathbb{N}, \ f(n) = (1 + 3 + 5 + ... + (2n+1))^n$.
  • takie określenie też jest poprawne, choć nie od razu widać, ile to jest
• $g : \mathbb{R} \ni x \mapsto \sin\frac{x}{\pi}\in \mathbb{R}$ jest całkiem poprawną funkcją.
• $h : \mathbb{R} \ni x \mapsto \sin\frac{\pi}{x}\in \mathbb{R}$,
  • to określenie (mimo, że podobne do poprzedniego) jest błędne:
    nie da się policzyć wartości $h(0)$;
    należałoby więc napisać np. $h : \mathbb{R}-{\{ {0} \}\ } \longrightarrow \mathbb{R}$
• ${\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^*$,
  • to funkcja określona na słowach nad alfabetem dwuelementowym ${\{ {0,1} \}\ }$
  • każdemu słowu przypisuje to słowo rozszerzone na końcu o symbol $1$
• $d: {\{ {0,1} \}\ }^* \longrightarrow \mathbb{N}, \ d(w) =$ długość słowa $w$

Wielomian to funkcja:

$x \mapsto a_nx^n + a_{n-1}x^{n-1} + \ldots + a_2x^2 + a_1 x + a_0$
gdzie

• liczby $a_n, a_{n-1}, \ldots, a_1,a_0$ zwane są współczynnikami wielomianu
  • mówimy więc o wielomianach o współczynnikach
    • naturalnych - jeśli $a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{N}$
    • całkowitych - jeśli $a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Z}$
    • wymiernych - jeśli $a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Q}$
    • rzeczywistych - jeśli $a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{R}$
  • liczba $n$ zwana jest stopniem wielomianu, ale tylko o ile $a_n \neq 0$.

Surjekcje, injekcje i bijekcje

Surjekcja to funkcja $f : X \longrightarrow Y$ spełniająca warunek

$\forall y\in Y \ \exists x\in X \ \ f(x) = y$

• Intuicyjnie, funkcja jest surjekcją, jeśli jej cała przeciwdziedzina jest wykorzystana, tzn. każdy jej element jest wartością funkcji dla jakiegoś elementu dziedziny,
• surjekcje często są nazywane funkcjami "na",
• piszemy też wtedy $f : X ↠ Y$.

Przykład

Funkcja $\mathbb{R} \ni x \mapsto x^3 \in \mathbb{R}$ jest surjekcją.
Funkcja $\mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q}$ nie jest surjekcją.
Funkcja $\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}$ nie jest surjekcją.
Funkcja $\mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q}$ jest surjekcją.
Funkcja $\mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z}$ jest surjekcją.
Funkcja $\mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z}$ jest surjekcją.
Funkcja $\mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Q}$ nie jest suriekcją.
Funkcja $\mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R}$ nie jest surjekcją.
Funkcja ${\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^*$ nie jest suriekcją.
Funkcja ${\{ {0,1} \}\ }^* \ni w \mapsto d(w) \in \mathbb{N}$ jest suriekcją.

Injekcja to funkcja $f : X \longrightarrow Y$ spełniająca warunek:

$\forall x_1,x_2 \in X \ \ x_1\neq x_2 \to f(x_1)\neq f(x_2)$

• Intuicyjnie, funkcja jest injekcją, jeśli różnym elementom dziedziny funkcja przyporządkowuje różne elementy przeciwdziedziny,
• injekcje często są nazywane funkcjami różnowartościowymi,
• piszemy też wtedy $f : X \hookrightarrow Y$.

Przykład

Funkcja $\mathbb{R} \ni x \mapsto x^3 \in \mathbb{R}$ jest injekcją.
Funkcja $\mathbb{R} \ni x \mapsto x^2 \in \mathbb{R}$ nie jest injekcją.
Funkcja $\mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z}$ jest injekcją.
Funkcja $\mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z}$ nie jest injekcją.
Funkcja $\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}$ jest injekcją.
Funkcja $\mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q}$ jest injekcją.
Funkcja $\mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R}$ nie jest injekcją.
Funkcja ${\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^*$ jest injekcją.
Funkcja ${\{ {0,1} \}\ }^* \ni w \mapsto d(w) \in \mathbb{N}$ nie jest injekcją.

Bijekcja to funkcja, która jest jednocześnie surjekcją i injekcją.

Przykład

Funkcja $\mathbb{R} \ni x \mapsto x^3 \in \mathbb{R}$ jest bijekcją.
Funkcja $\mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q}$ nie jest bijekcją.
Funkcja $\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}$ nie jest bijekcją.
Funkcja $\mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q}$ jest bijekcją.
Funkcja $\mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z}$ jest bijekcją.
Funkcja $\mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z}$ nie jest bijekcją.
Funkcja $\mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Q}$ nie jest bijekcją.
Funkcja ${\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^*$ nie jest bijekcją.
Funkcja ${\{ {0,1} \}\ }^* \ni w \mapsto d(w) \in \mathbb{N}$ nie jest bijekcją.

Funkcje odwrotne

Traktując funkcję $f : X \longrightarrow Y$ jako relację $f \subseteq X \times Y$ (zbiór par), możemy rozważać relację $f^{-1}$ odwrotną do $f$.

Kiedy ta relacja jest funkcją?

• ponieważ $f^{-1}$ ma spełniać warunek, że każdy element dziedziny $f^{-1}$ (tzn. zbioru $Y$) ma przypisaną jakąś wartość, oznacza to, że sama funkcja $f$ wyczerpuje wszystkie elementy przeciwdziedziny, a zatem, że $f$ jest surjekcją,
• nadto $f^{-1}$ ma przypisywać dokładnie jeden taki element, czyli że każdy element z $Y$ jest przypisany poprzez $f$ jednemu elementowi z $X,$ a zatem $f$ musi być injekcją.

A zatem: funkcja posiada funkcję odwrotną, wtedy i tylko wtedy, gdy jest bijekcją.

• Nieformalnie tworzenie funkcji odwrotnej polega na odwracaniu strzałek.
• Gdyby $f$ nie była surjekcją, to przy próbie odwrócenia strzałek niektóre elementy zbioru $Y$ nie miałyby przyporządkowanego żadnego elementu z $X$.
• Gdyby zaś $f$ nie była injekcją, to przy próbie odwrócenia strzałek niektóre strzałki byłyby "rozdwojone".

Przykład

• Funkcja $f : \mathbb{R} \ni x \mapsto 2x \in \mathbb{R}$ jest bijekcją, a zatem posiada funkcję odwrotną. Tę funkcję odwrotną można wyliczyć: skoro $y = f(x) = 2x$, to $f^{-1}(y) = x = y/2$. Zatem $f^{-1} : \mathbb{R} \ni x \mapsto x/2 \in \mathbb{R}$.
• Funkcja $\mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z}$ nie jest injekcją. Nie posiada więc funkcji odwrotnej.
• Funkcja $\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}$ nie jest surjekcją. Nie posiada więc funkcji odwrotnej. Ale rozważając tę funkcję z przeciwdziedziną $\mathbb{P}$ będącą zbiorem liczb parzystych, tzn. $\mathbb{N} \ni x \mapsto 2x \in \mathbb{P}$ staje się ona bijekcją i posiada funkcję odwrotną $\mathbb{P} \ni x \mapsto x/2 \in \mathbb{N}$.
• Funkcja $\mathbb{R} \ni x \mapsto x^2 \in \mathbb{R}$ nie jest ani injekcją ani surjekcją. Nie posiada więc funkcji odwrotnej. Surjektywność można by "uratować", rozważając

$f : \mathbb{R} \ni x \mapsto x^2 \in [0, +\infty).$

Wciąż jednak brakowałoby injektywności. Ograniczając jednak, tę funkcję do liczb nieujemnych, tzn. traktując ją jako:

$f|_{[0, +\infty)}: [0, +\infty) \ni x \mapsto x^2 \in [0, +\infty),$

staje się już bijekcją, więc posiada funkcję odwrotną, którą jest

$[0, +\infty) \ni x \mapsto \sqrt{x} \in [0, +\infty).$

Składanie funkcji

Złożenie funkcji $f : X \longrightarrow Y$ i funkcji $g : Y \longrightarrow Z$ to funkcja

$gf: X \longrightarrow Z$

określona dla wszystkich argumentów $x \in X$ jako $(gf)(x) = g(f(x))$.

• Nieformalnie - najpierw obliczamy wartość funkcji $f$ dla elementu $x$,
  a następnie obliczamy wartość funkcji $g$ dla wyniku tego obliczenia; czyli "idziemy dalej wzdłuż następnej strzałki"

$X \longrightarrow Y \longrightarrow Z$

• Piszemy $gf$ (a nie $fg$) na oznaczenie złożenia, w którym najpierw obliczana jest wartość funkcji $f$, a potem funkcji $g$.
• W praktyce, przy złożeniu $gf$, dziedzina funkcji $g$ nie musi być tym samym zbiorem, co przeciwdziedzina funkcji $f$ - wystarczy, by była większa.

Przykład

• Niech $f : \mathbb{N} \ni n \mapsto n + 2 \in \mathbb{N}$ i $g : \mathbb{N} \ni n \mapsto 3n \in \mathbb{N}$. Wówczas dla $gf : \mathbb{N} \longrightarrow \mathbb{N}$ mamy $(gf)(n) = g(f(n)) = g(n + 2) = 3(n + 2)= 3n+6$ a dla $fg : \mathbb{N} \longrightarrow \mathbb{N}$ mamy $(fg)(n) = f(g(n)) = f(3n) = 3n + 2$.

Morał: złożenia $fg$ i $gf$ to (na ogół) różne funkcje.

• Niech $f : \mathbb{R} \ni x \mapsto \sin 3x \in \mathbb{R}$ i $g : \mathbb{R} \ni x \mapsto (x + \pi)^2 \in\mathbb{R}$. Wówczas złożenie $fg: \mathbb{R} \longrightarrow \mathbb{R}$ dane jest wzorem

$(fg)(x) = f(g(x)) = f((x + \pi)^2) = \sin(3(x + \pi)^2).$

Morał: Nie zawsze da się łatwo wyliczyć przepis na funkcję złożoną.

• Gdy $f : X \longrightarrow Y$ jest bijekcją, to istnieje funkcja odwrotna $f^{-1} : Y \longrightarrow X$. Jeśli złożymy $f^{-1} f$, to uzyskamy funkcję $X \longrightarrow X$, która "nic nie robi":

$(f^{-1} f)(x) = f^{-1}(f(x)) = x.$

Taka funkcja zwana jest identycznością na zbiorze $X$ i oznaczana $id_X$. Podobnie - składając $f f^{-1} : Y \longrightarrow Y$, otrzymamy identyczność na zbiorze $Y$.

Widzieliśmy, że nie zawsze $fg = gf$.

Obserwacja 3.1

Dla funkcji $X \stackrel{h}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z \stackrel{f}{\longrightarrow} W$ zachodzi $f(gh) = (fg)h$. <

Obserwacja 3.2

Nadto dla $X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z$ mamy:

• Jeśli $f, g$ są surjekcjami, to $gf$ jest surjekcją.
• Jeśli $f, g$ są injekcjami, to $gf$ jest injekcją.
• Jeśli $f, g$ są bijekcjami, to $gf$ jest bijekcją.
• Pierwsza i trzecia z powyższych własności nie zachodzą, jeśli dziedzina funkcji $g$ jest większa niż przeciwdziedzina funkcji $f$.

Przykład

Zbadaj czy dla funkcji $X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z$ zachodzi:

• jeśli $gf$ jest surjekcją, to $f$ jest surjekcją
• jeśli $gf$ jest surjekcją, to $g$ jest surjekcją
• jeśli $gf$ jest injekcją, to $f$ jest injekcją
• jeśli $gf$ jest injekcją, to $g$ jest injekcją

Funkcje wielu zmiennych

• Funkcja dwóch zmiennych to funkcja, której dziedziną jest zbiór par (zamiast pojedynczych elementów).
• Piszemy np. $f : X \times Y \longrightarrow Z$.
• Zatem funkcja taka każdej parze $(x,y)\in X \times Y$ przyporządkowuje dokładnie jeden element $f(x,y) \in Z$.
• Podobnie można zdefiniować funkcje trzech i więcej zmiennych.

Przykład

Przykładem funkcji dwóch zmiennych są działania arytmetyczne:

• $\mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto x+y \in \mathbb{R}$
• $\mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto x-y \in \mathbb{R}$
• $\mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto xy \in \mathbb{R}$
• $\mathbb{R} \times \mathbb{R}-{\{ {0} \}\ } \ni (x,y) \mapsto \frac{x}{y} \in \mathbb{R}$
• $\mathbb{N} \times \mathbb{N} \ni (x,y) \mapsto x^y \in \mathbb{N}$

a także konkatenacja (sklejenie) słów

• $X^* \times X^* \ni (v,w) \mapsto vw \in X^*$, gdzie $vw$ oznacza słowo (krotkę) powstałe z doklejenia słowa $w$ na końcu słowa $v$.