6   Funkce a skládání, Induktivní definice
Vratme se nyní k látce Lekce 4 z pohledu funkcí a jejich skládání a inverzí.
Kde jste se již intuitivně se skládáním funkcí setkali - jak například spočítáte na kalkulačce výsledek složitějšího vzorce? A jinde?
Na závěr látky o relacích a funkcích se stručně podíváme na problematiku induktivních definic množin a funkcí a uzávěrů vlastností relací. □
Stručný přehled lekce
* Přehled základních vlastností funkcí, inverze.
* Skládání funkcí (coby relací), speciálně aplikováno na permutace.
* Induktivní definice množin a funkcí; uzávěry vlastností relací.
Relace a funkce, zopakování
• Relace mezi množinami Al,---        pro k G N, je libovolná podmnožina kartézského součinu
R C Ai x A2 x • • • x Ak .
Pokud A\ — A2 — • • • = Ak — A, hovoříme o k-ární relaci R na A.
• (Totální) funkce z množiny A do množiny B je relace / mezi A b B taková, že pro každé x G A existuje právě jedno y G B takové, že (x, y) G /.
* Množina A se nazývá definiční obor a množina B obor hodnot funkce /. Funkcím se také říká zobrazení
* Místo G / píšeme obvykle f(x) = y. Zápis / : A ^ B říká, že / je funkce s def. oborem A a oborem hodnot B.
Petr Hliněný, Fl MU Brno, 2016
2/21
Fl: IB000: Skládání a Funkce
Pokud naší definici funkce upravíme tak, že požadujeme pro každé x G A nejvýše jedno y G B takové, že (x, y) G /, obdržíme definici parciální funkce z A do B.
AxS
□
Inverzní relace k binární relaci iž se značí R 1 a je definována takto:
i?-1 = {(6, o) | (a, 6) G i?}
Petr Hliněný, Fl MU Brno, 2016
3/21
Fl: IB000: Skládání a Funkce
6.1   Vlastnosti funkcí
Definice 6.1. Funkce (případně parciální funkce) / : A —> B je
• injektivní(nebo také prostá) právě když pro každé x,y G A, x ^ y platí
fix) + f (y);
•—	-5>-	
	...........................^	
surjektivní(nebo také „na") právě když pro každé y G B existuje x G A takové, že f (x) = y\
bijektivní (vzáj. jednoznačná) právě když je injektivní a souč. surjektivní.c
^>-
Petr Hliněný, Fl MU Brno, 2016
4/21
Fl: IB000: Skládání a Funkce
■r
Následují jednoduché ukázky vlastností funkcí.
• Funkce plus : N x N —> N je surjektivní, ale není prostá.
• Funkce g : Z —> N daná předpisem
—2x — 1   jestliže x < 0,
2x jinak
#0)
je bijektivní.n
Funkce 0:0 —^ 0 je bijektivní.n
Funkce 0:0—^ {a, b} je injektivní, ale není surjektivní.c
Příklad 6.2. Dokázali byste nalézt jednoduše (tj. „hezky") vypočítate!nou bijektivní funkci ľ\     N x N? □
□
Příklad 6.3. Pro jaké hodnoty parametru a, b je funkce f (x) = ax3+3x2+bx z R do R in jektivn í či surjektivn í?
Petr Hliněný, Fl MU Brno, 2016
5/21
Fl: IB000: Skládání a Funkce
Inverze funkce
Inverze funkce je dána definicí inverze relace z Oddílu 4.4.
Příklady inverzí pro běžné funkce:
• Inverzí bijektivní funkce f(x) — x + 1 na Z je funkce = x — l.c
• Inverzí prosté funkce f(x) — ex na R je parciální funkce = lnx.c
• Funkce g(x) — x mod 3 není prostá na N, a proto její inverzí je „jen" relace
g~l — {(a, 6) | a = 6 mod 3}.
Konkrétně g'1 ={(0,0), (0,3), (0,6),..., (1,1), (1,4),..., (2,2), (2,5),... }.□
Tvrzení 6.4. Mějme funkci f : A —> B. Pak její inverzní relace /_1 je
a) parciální funkce právě když f je prostá,
b) funkce právě když f je bijektivní
Tvrzení 6.5. Je-li inverzní relace /_1 funkce f taktéž parciální funkcí, tak platí = x pro všechna x z definičního oboru.
Petr Hliněný, Fl MU Brno, 2016
6/21
Fl: IB000: Skládání a Funkce
6.2   Skládání funkcí, permutace
Fakt: Mějme funkce (zobrazení) f:A—>Bag:B—>C. Pak jejich složením coby relací v tomto pořadí vznikne zobrazení [g o /) : A     C definované
(90 f)(x) := g(f(x)).
• Jak například na běžné kalkulačce vypočteme hodnotu funkce sin2 xl Složíme (v tomto pořadí) „elementární" funkce f(x) = sin x a g{x) = x2.
• Jak bychom na „elementární" funkce rozložili aritmetický výraz 21og(x2 + 1) ? 1 Ve správném pořadí složíme funkce fi(x) = x2, J2{x) = x + 1, f^{x) = log x a f±(x) = 2x.
• A jak bychom obdobně vyjádřili složením funkcí aritmetický výraz sin x + cos x ? Opět je odpověď přímočará, vezmeme „elementární" funkce gi(x) = sin x a #2(^) = cosx, a pak je „složíme" další funkcí h(x, y) = x + y.
Vidíme však, že takto pojaté „skládání" už nezapadá hladce do našeho zjednodušeného formalismu skládání relací.
Petr Hliněný, Fl MU Brno, 2016
7/21
Fl: IB000: Skládání a Funkce
Skládání permutací
Definice: Nechť permutace tv množiny {1,2,..., n} je určena seřazením jejích prvků (pi,...,Pn)- Pak ty je zároveň bijektivním zobrazením {l,...,n} —>> {1,... , n} definovaným předpisem ty(í) = p{.
Tudíž lze permutace skládat jako relace podle Definice 4.7.
Poznámka: Všechny permutace množiny {1,2, ...,n} spolu s operací skládání tvoří grupu, zvanou symetrická grupa Sn.
Permutační grupy (podgrupy symetrické grupy) jsou velice důležité v algebře, neboť každá konečná grupa je vlastně isomorfní některé permutační grupě.
Příkladem permutace vyskytujícím se v programátorské praxi je třeba zobrazení i i—> (i+1) mod n ("inkrement"). Často se třeba lze setkat (aniž si to mnohdy uvědomujeme) s permutacemi při indexaci prvků polí. □
Pro formální úplnost výkladu o permutacích si ještě uvedeme jednoduché:
Tvrzení 6.6. Mějme permutace tt a a množiny {1,2,..., n}. Pak jejich složení a o 7T je opět permutací množiny {1,2,..., n}.
Petr Hliněný, Fl MU Brno, 2016
8/21
Fl: IB000: Skládání a Funkce
Cykly permutací
V kontextu pohledu na funkce a jejich skládání coby relací si zavedeme jiný, názornější, způsob zápisu permutací - pomocí jejich cyklů.
Definice: Nechť tv je permutace na množině A. Cyklem v tv rozumíme posloupnost (ai, g&2, ..., a&) různých prvků A takovou, že Tv{ai) = a^+i pro i = 1, 2,... , k — 1 a 7r(a&) = a\.
• Jak název napovídá, v zápise cyklu (ai, ..., a&) není důležité, kterým prvkem začneme, ale jen dodržení cyklického pořadí. Cyklus v permutaci může mít i jen jeden prvek (zobrazený na sebe).
• Například permutace (5, 3,4,8, 6,1, 7, 2) je zakreslena svými cykly výše.
Petr Hliněný, Fl MU Brno, 2016
9/21
Fl: IB000: Skládání a Funkce
Reprezentace permutací jejich cykly
Věta 6.7. Každou permutaci ty na konečné množině A lze zapsat jako složení cyklů na disjunktních podmnožinách (rozkladu) A.
Důkaz: Vezmeme libovolný prvek a\ G A a iterujeme zobrazení 0,2 = vr(ai), as = 7r(a2), atd., až se dostaneme „zpět" k a^+i = vr(a^) = a\. Proč tento proces skončí? Protože A je konečná a tudíž ke zopakování některého prvku afc+i musí dojít. Nadto je ty prostá, a proto nemůže nastat 7ľ(a^) = dj pro j > 1. Takto získáme první cyklus (ai,..., a^).
Induktivně pokračujeme s hledáním dalších cyklů ve zbylé množině A' — A\{a\,..., dk}, dokud nezůstane prázdná. V tomto indukčním kroku si musíme uvědomit, že ty omezené na nosnou množinu A' je stále permutací podle definice. □
Značení permutace jejími cykly: Nechť se permutace ty podle Věty 6.7 skládá z cyklů (ai,..., a^), (61,..., bi) až třeba (zi,..., zm). Pak zapíšeme
7T = ( (ai,..., afe) (61,..., 6/) ... (zi,..., Zm) ) .
Petr Hliněný, Fl MU Brno, 2016
10/21
Fl: IB000: Skládání a Funkce
Příklad 6.8. Ukázka skládání permutací daných svými cykly.
Vezměme 7-prvkovou permutaci ty = (3,4, 5, 6, 7,1, 2). Ta se skládá z jediného cyklu (1,3,5,7,2,4,6). Jiná permutace a = (5,3,4,2,6,1,7) se rozkládá na tři cykly (1,5,6), (2,3,4) a (7). □
Nyní určíme složení a o ty těchto dvou permutací (už přímo v zápisu cykly):
«1,5,6><2,3,4)<7)) o ((1,3,5,7,2,4,6)) = «1,4)<2)(3,6,5, 7)) (Nezapomínejme, že první se ve složení aplikuje pravá permutace!)
Postup skládání jsme použili následovný:
* 1 se zobrazí v permutaci vpravo na 3 a pak vlevo na 4.
* Následně 4 se zobrazí na 6 a pak na 1. Tím „uzavřeme" první cyklus (1,4).c
* Dále se 2 zobrazí na 4 a pak hned zpět na 2, tj. má samostatný cyklus.
* Zbylý cyklus (3,6,5,7) určíme analogicky.
Petr Hliněný, Fl MU Brno, 2016
11/21
Fl: IB000: Skládání a Funkce
6.3   Induktivní definice množin a funkcí
Přímým zobecněním dřívějších rekurentních definic je následující koncept. Definice 6.9. Induktivní definice množiny.
Jedná se obecně o popis (nějaké) množiny M v následujícím tvaru:
• Je dáno několik pevných {bázických) prvků ai, a2,..., a& G M.
• Je dán soubor induktivních pravidel typu
Jsou-li (libovolné prvky) xi,... ,xt G M, pak také y G M. V tomto případě je y typicky funkcí y = fi(xi,..., xt).
Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující těmto pravidlům.
Petr Hliněný, Fl MU Brno, 2016
12/21
Fl: IB000: Skládání a Funkce
■r
Několik ukázek. ..
• Pro nejbližší příklad induktivní definice se obrátíme na množinu všech přirozených čísel, která je formálně zavedena následovně.
- o e N
- Je-li i G N, pak také i + 1 G N.
or^Tir^T2r^T3r^Í4r^
Pro každé y E N můžeme definovat jinou množinu My C N induktivně:
- y e My
- Jestliže x G My a x + 1 je liché, pak x + 2 G My. □ Pak například M3 = {3}, nebo M4 = {4 + 2i | i G N}. □
Dalším příkladem induktivní definice je už známé zavedení výrokových formulí z Oddílu 1.5. Uměli byste teď přesně říci, co tam byly bázické prvky a jaká byla induktivní pravidla?
Petr Hliněný, Fl MU Brno, 2016
13/21
Fl: IB000: Skládání a Funkce
Jednoznačnost induktivních definic
Definice: Řekneme, že daná induktivní definice množiny M je jednoznačná, právě když každý prvek M lze odvodit z bázických prvků pomocí induktivních pravidel právě jedním způsobem.
• Definujme například množinu M C N induktivně takto:
- 2,3 G M
- Jestliže x, y G M a x < y, pak také x2 + y2 a x • y jsou prvky M. Proč tato induktivní definice není jednoznačná? nNapříklad číslo 8 G M lze odvodit způsobem 8 = 2 • (2 • 2), ale zároveň zcela jinak 8 = 22 + 22.
• V čem tedy spočívá důležitost jednoznačných induktivních definic množin? Je to především v dalším možném využití induktivní definice množiny jako „základny" pro odvozené vyšší definice, viz následující.
Petr Hliněný, Fl MU Brno, 2016
14/21
Fl: IB000: Skládání a Funkce
Definice 6.10. Induktivní definice funkce z induktivní množiny. Nechť množina M je dána jednoznačnou induktivní definicí. Pak říkáme, že funkce T : M       X je definována induktivně (vzhledem k induktivní definici M), pokud je řečeno:
• Pro každý z bázických prvků ai, 0,2,...,    G M je určeno F{ai) = C{.
• Pro každé induktivní pravidlo typu
"Jsou-li (libovolné prvky) xi,..., X£ G M, pak také /(xi,..., a^) G M" je definováno
^( • • • 5 ^)) na základě hodnot T(x\),..., ^(cc^.c
Ilustrujme si induktivní definici funkce dětskou hrou na „tichou poštu". Definičním oborem je řada sedících hráčů, kde ten první je bázickým prvkem a každý následující (mimo posledního) odvozuje hráče sedícího hned za ním jako další prvek hry.
Hodnotou bázického prvku je první (vymyšlené) posílané slovo. Induktivní pravidlo pak následujícímu hráči přiřazuje slovo, které je odvozeno („zkomolením") ze slova předchozího hráče. Výsledkem hry pak je hodnota-slovo posledního hráče.
Petr Hliněný, Fl MU Brno, 2016
15/21
Fl: IB000: Skládání a Funkce
■r
Pro další příklad se podívejme třeba do manuálu unixového příkazu test
No, problematická je otázka jednoznačnosti této definice - jednoznačnost není vynucena (jen umožněna) syntaktickými pravidly, jinak je pak dána nepsanými konvencemi implementace příkazu.
To je pochopitelně z matematického hlediska špatně, ale přesto jde o pěknou ukázku z praktického života informatika.
EXPRESSION:
EXPRESSION is true or false ( EXPRESSION ) ! EXPRESSION
EXPRESSI0N1 -a EXPRESSI0N2 EXPRESSI0N1 -o EXPRESSI0N2 [-n] STRING STRING1 = STRING2
and sets exit status.    It is one of: EXPRESSION is true EXPRESSION is false
both EXPRESSI0N1 and EXPRESSI0N2 are true either EXPRESSI0N1 or EXPRESSI0N2 is true the length of STRING is nonzero the strings are equal
□
Petr Hliněný, Fl MU Brno, 2016
16/21
Fl: IB000: Skládání a Funkce
Induktivní definice se „strukturální" indukcí
Příklad 6.11. Jednoduché aritmetické výrazy a jejich význam.
Nechť je dána abeceda £ = {0,1, 2, 3,4, 5,6, 7, 8, 9, 0, ©, (,)}. Definujme množinu jednoduchých výrazů SExp C X* induktivně takto:
- Dekadický zápis každého přirozeného čísla n je prvek SExp.
- Jestliže x,y G SExp, pak také (x) 0 (y) a (x) © (y) jsou prvky SExp.
- Jak vidíme,  díky  nucenému  závorkování je tato induktivní definice jednoduchých výrazů (nikoliv jejich „hodnot") jednoznačná.
Tímto jsme aritmetickým výrazům přiřadili jejich „formu", tedy syntaxi.
Pro přiřazení „významu", tj. sémantiky aritmetického výrazu, následně definujme funkci Val: SExp —>> N induktivně takto:
- Bázické prvky: Val(n) = n, kde n je dekadický zápis přirozeného čísla n.
- První induktivní pravidlo: Val((x) © (y)) = Val(x) + Val(y).
- Druhé induktivní pravidlo: Val((x) 0 (y)) = Val(x) • Val(y). □
Co je pak „správným významem" (hodnotou) uvedených aritmetických výrazů?
□
Petr Hliněný, Fl MU Brno, 2016
17/21
Fl: IB000: Skládání a Funkce
Příklad 6.12.  Důkaz správnosti přiřazeného „významu" Val: SExp —> N.
Věta. Pro každý výrazu G SExp je hodnota Val(a) číselně rovna výsledku vyhodnocení výrazu a podle běžných zvyklostí aritmetiky
Matematickou indukcí: Na rozdíl od dříve probíraných příkladů zde nevidíme žádný celočíselný „parametr rí\ a proto si jej budeme muset nejprve definovat.
Naši indukci tedy povedeme podle „délky i odvození výrazu a" definované jako počet aplikací induktivních pravidel potřebných k odvození a G SExp.
□
Důkaz: V bázi indukce ověříme vyhodnocení bázických prvků. Platí Val(n) = n, což skutečně odpovídá zvyklostem aritmetiky.
V indukčním kroku se podíváme na vyhodnocení Val((x) © (y)) = Val(x) + Val(y). Podle běžných zvyklostí aritmetiky by hodnota Val((x) © (y)) měla být rovna součtu vyhodnocení výrazu x, což je podle indukčního předpokladu rovno Val(x) (x má zřejmě kratší délku odvození), a vyhodnocení výrazu y, což je podle indukčního předpokladu rovno Val(y). iTakže skutečně Val((x) © (y)) = Val(x) + Val(y).
Druhé pravidlo Val((x) 0 (y)) se dořeší analogicky. □
Petr Hliněný, Fl MU Brno, 2016
18/21
Fl: IB000: Skládání a Funkce
6.4   Uzávěry relací
Definice: Buď V (nějaká) vlastnost binárních relací. Řekneme, že V je uzavíratelná, pokud splňuje následující podmínky:
• Pro každou množinu M a každou relaci R C M x M existuje alespoň jedna relace S C M x M, která má vlastnost V a pro kterou platí R C S.
• Nechť / je množina a nechť Ri C M x M je relace mající vlastnost V pro každé i E I. Pak relace        Ri má vlastnost V.n
Fakt: Libovolná kombinace vlastností reflexivita, symetrie, tranzitivita je uzavíratelná vlastnost.
Ireflexivita a antisymetrie nejsou uzavíratelné vlastnosti.
Věta 6.14. Necht V je uzavíratelná vlastnost binárních relací Buď M množina a R libovolná binární relace na M. Pak pro množinu všech relací S D R na M majících vlastnost V existuje infimum Ry (vzhledem k množinové inkluzi), které samo má vlastnost V.
Tuto infimální relaci Ry s vlastností V nazýváme V-uzáver relace R.
Petr Hliněný, Fl MU Brno, 2016
19/21
Fl: IB000: Skládání a Funkce
Tvrzení 6.15. Nechť R je binární relace na M. Pak platí následující poznatky.
• Reflexivní uzávěr R je přesně relace R U {(x, x) | x G M}.c
• Symetrický uzávěr R je přesně relace
R= {{x, y) | (z, y) G R nebo (y, x) G #}.□
• Tranzitivní uzávěr R je přesně relace R+ = U£i Tl(R), kde T je funkce, která pro každou binární relaci S vrátí relaci
T(S) =/SU{(x,z)    existuje y takové, že (x, y), (y, z) G 5}
a Tz = To • • • o T je z-krát iterovaná aplikace funkce T.
v-v-✓ j
z
• Reflexivní a tranzitivní uzávěr i? je přesně relace R* = Q+, kde Q je reflexivní uzávěr R.z
• Reflexivní, symetrický a tranzitivní uzávěr i? (tj. nejmenší ekvivalence ob-sáhující R) je přesně relace kde Q je reflexivní uzávěr Rx
Poznámka: Na pořadí aplikování uzávěrů vlastností záleží! Zhruba řečeno, tranzitivní uzávěr aplikujeme coby poslední.
Petr Hliněný, Fl MU Brno, 2016
20/21
Fl: IB000: Skládání a Funkce
Neformálně:
• V^-uzávěr relace je vlastně daný induktivní definicí podle vlastnosti V.
• Význam reflexivních a symetrických uzávěrů je z předchozího zřejmý.
• Význam tranzitivního uzávěru R+ je následovný:
Do R+ přidáme všechny ty dvojice (x,z) takové, že v R se lze „dostat po šipkách" z x do z. Nakreslete si to na papír pro nějakou jednoduchou relaci, abyste význam tranzitivního uzávěru lépe pochopili. □
Například buď JJCNxN definovaná takto: R = + 1) | i G N} Pak R+ je běžné ostré lineární uspořádání < přirozených čísel.
A jak bylo dříve řečeno, antisymetrický uzávěr relace prostě nedává smysl
Petr Hliněný, Fl MU Brno, 2016
21/21
Fl: IB000: Skládání a Funkce