6   Funkce a skládání, Induktivní definice
Vraťme 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?
Na závěr látky o relacích a funkcích se stručně podíváme na problematiku induktivních definic a uzávěrů vlastností.
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 Ai,--- ,Ak, pro k G N, je libovolná podmnožina kartézského součinu
R C Ai x • • • x Ak . Pokud A\ = • • • = Ak = A, hovoříme o k-ární relaci R na A. c
• (Totální) funkce z množiny A do množiny B je relace / mezi A a B taková, že pro každé x <E A existuje právě jedno y G B takové, že (x, y) G /.c
* Množina A se nazývá definiční obor a množina B obor hodnot funkce /. Funkcím se také říká zobrazení.
* Místo (x,y) G / píšeme obvykle f(x) = y. Zápis
/: A^B
říká, že / je funkce s def. oborem A a oborem hodnot B. c
• Pokud naší definici funkce upravíme tak, že požadujeme pro každé x (z A nejvýše jedno y G B takové, že (x,y) G /, obdržíme definici parciální funkce z A do B.
Petr Hliněný, Fl MU Brno, 2013
2/20
Fl: IB000: Skládáni a Funkce
• Inverzní relace k binární relaci R se značí i?    a je definována takto:
R-1 = {(&, a) | (a, b) G i?}
i?    je tedy relace mezi B a A.
Petr Hliněný, Fl MU Brno, 2013
3/20
Fl: IB000: Skládáni 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í
f{x)rf{y)\
» surjektivní (nebo také „na") právě když pro každé y £ B existuje x (z A takové, že f{x) = y;
		
	—-	Y
bijektivní (vzáj. jednoznačná) právě když je injektivní a souč. surjektivníx
Petr Hliněný, Fl MU Brno, 2013
4/20
Fl: IB000: Skládáni a Funkce
Následují jiné ukázky vlastností funkcí.
• Funkce plus : N x N -> Nje surjektivní, ale není prostá.c
• Funkce g : 7L —> N daná předpisem
, . _ í — 2x — 1   jestliže x < 0. 9{-X) = \2x jinak
je bijektivníx
• Funkce 0 : 0 —> 0 je bijektivníx
• Funkce 0:0—^ {a,b} je injektivní, ale není surjektivníx
• Dokázali byste nalézt bijektivní funkci NxN-> N?
Petr Hliněný, Fl MU Brno, 2013
5/20
Fl: IB000: Skládáni a Funkce
Inverze funkce
Příklady inverzí pro relace-funkce.
• Inverzí bijektivní funkce f(x) = x + 1 na 7L je funkce f^1(x) = x — l.c
• Inverzí prosté funkce f(x) = ex na R je parciální funkce f^1(x) = Inx.
• Funkce g(x) = x mod 3 není prostá na N, a proto její inverzí je „jen" relace g^1 = {(a, b) | a = b mod 3}.
Konkr. g-1 = {(0, 0), (0, 3), (0, 6),... , (1,1), (1,4),... , (2, 2), (2, 5),... }.
c
Tvrzení 6.2. Mějme funkci f : A —> B. Pak její inverzní relace f^1 je
a) parciální funkce právě když f je prostá, c
b) funkce právě když f je bijektivní.
Důkaz vyplývá přímo z definic funkce a inverze relace. □
Petr Hliněný, Fl MU Brno, 2013
6/20
Fl: IB000: Skládáni a Funkce
6.2   Skládání funkcí, permutace
Fakt: Mějme zobrazení (funkce) f:A—>Bag:B—>C. Pak jejich složením coby relací v tomto pořadí vznikne zobrazení (g o /) : A —> C definované
(gof)(x)=g(f(x)).c
• Jak například na běžné kalkulačce vypočteme hodnotu funkce sin2x? Složíme (v tomto pořadí) „elementární" funkce f(x) — smx   g (x) — x2.
• Jak bychom na „elementární" funkce rozložili aritmetický výraz 21og(x2 + l)? c Ve správném pořadí složíme funkce fi(x) — x2, fzix) — x + 1, /b(x) — log x a
Ja{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 92(x) — cos x, a pak je „složíme" další funkcí h(x, y) — x + y. c
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, 2013
7/20
Fl: IB000: Skládáni a Funkce
Skládání permutací
Definice: Nechť permutace tt množiny {1,2,..., n} je určena seřazením jejích prvků (pi,... ,pn)- Pak tt je zároveň bijektivním zobrazením {l,...,n} —> {1,... , n} definovaným předpisem ir(i) = pi. c
Tudíž lze permutace skládat jako relace podle Definice 4.7. c
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á grupa je vlastně isomorfní některé permutační grupě, c
Příkladem permutace vyskytujícím se v programátorské praxi je třeba zobrazení 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í.
Petr Hliněný, Fl MU Brno, 2013
8/20
Fl: IB000: Skládáni 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ť tt je permutace na množině A. Cyklem v tt rozumíme posloupnost (di, ci2, ■ ■ ■, afc) různých prvků A takovou, že 7r(aj) = a^+i pro i = 1, 2,..., k — 1 a 7r(afc) = ai. c
• Jak název napovídá, v zápise cyklu (ai, ci2, ■ ■ ■, a,k) 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, 2013
9/20
Fl: IB000: Skládáni a Funkce
Reprezentace permutací jejich cykly
Věta 6.3. Každou permutaci tt na konečné množině A lze zapsat jako složení cyklů na disjunktních podmnožinách (rozkladu) A. c
Důkaz: Vezmeme libovolný prvek a± G A a iterujeme zobrazení 02 = 7r(ai), 03 = 7r(ci2), atd., až se dostaneme „zpět" k a^+i = ^{o-k) = ai- 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 tt prostá, a proto nemůže nastat 7r(afc) = a, pro j > 1. Takto získáme první cyklus (a±,..., a^). c
Induktivně pokračujeme s hledáním dalších cyklů ve zbylé množině A \ {ai,..., afc}, dokud nezůstane prázdná. □
Značení permutace jejími cykly: Nechť se permutace tt podle Věty 6.3 skládá z cyklů (di,..., a*;), (61,..., 6;) až třeba (zi,..., zm). Pak zapíšeme
7T = ( (ai, ..., afe) (Ďi,..., bt) ... {z-í, ..., zm) ) .
Petr Hliněný,  Fl MU Brno, 2013
10/20
Fl: IB000: Skládání a Funkce
Příklad 6.4. Ukázka skládání permutací daných svými cykly.
Vezměme 7-prvkovou permutaci ir — (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). c
Nyní určíme složení a o tt 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, c
* Zbylý cyklus (3,6,5,7) určíme analogicky.
Petr Hliněný,  Fl MU Brno, 2013
11/20
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.5. 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ů a±, 02,...,     £ M. c
• Je dán soubor induktivních pravidel typu
Jsou-li (libovolné prvky) x±,..., xi G M, pak také y G M. V tomto případě je y typicky funkcí y = fi(xi,... ,x^). c
Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující těmto pravidlům, c
Poznámka: Vidíte podobnost této definice s uzávěrem relace? (Věta 6.9.)
Petr Hliněný,  Fl MU Brno, 2013
12/20
Fl: IB000: Skládání a Funkce
• 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ě.
- 0 G N
- Je-li i G N, pak také i + 1 G N.
• Pro každé y G 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. c Pak například M3 = {3}, nebo M4 = {4 + 2i | i G N}, c
• 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, 2013 13/20 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, c
• 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á?   Napří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, 2013
14/20
Fl: IB000: Skládání a Funkce
Definice 6.6. 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 bazických prvků a±, ci2,...,     £ M je určeno J-{a,i) = C{. c
• Pro každé induktivní pravidlo typu
"Jsou-li (libovolné prvky) x±,...,    G M, pak také f(x±,..., xg) G M" je definováno
!F[ f{x\,. .., xi)) na základě hodnot T(x\),. .., T{xi).n
Pro příklad se podívejme třeba do manuálu unixového příkazu test EXPRESSION:
EXPRESSION is true or false and sets exit status.    It is one of: ! EXPRESSION EXPRESSION is false
EXPRESSI0N1 -a EXPRESSI0N2 both EXPRESSI0N1 and EXPRESSI0N2 are true EXPRESSI0N1 -o EXPRESSI0N2 either EXPRESSI0N1 or EXPRESSI0N2 is true
[-n] STRING the length of STRING is nonzero
STRING1 = STRING2 the strings are equal
Petr Hliněný,  Fl MU Brno, 2013
15/20
Fl: IB000: Skládání a Funkce
Induktivní definice se „strukturální" indukcí Příklad 6.7. Jednoduché aritmetické výrazy a jejich význam.
Nechť je dána abeceda £ — {0,1, 2, 3,4, 5, 6, 7, 8, 9, ©,©,(,)}. Definujme množinu jednoduchých výrazů SExp C E* 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)Q(y) a (x)(B(y) jsou prvky SExp.   (Jak vidíme, díky nucenému závorkování je tato induktivní definice jednoznačná.)
Tímto jsme aritmetickým výrazům přiřadili jejich „formu", tedy syntaxi, c
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. c
- První induktivní pravidlo: Val((x) © (y)) — Val(x) + Val(y).
- Druhé induktivní pravidlo: Val((x) 0 (y)) — Val(x) ■ Val(y). c
Co je tedy správným významem uvedených aritmetických výrazů? C
Petr Hliněný,  Fl MU Brno, 2013
16/20
Fl: IB000: Skládání a Funkce
Příklad 6.8.  Důkaz správnosti přiřazeného „významu" Val: SExp —>• N.
Věta. Pro každý výraz s g SExp je hodnota Val(s) číselně rovna výsledku vyhodnocení výrazu s 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 n", a proto si jej budeme muset nejprve definovat.c
Naši indukci tedy povedeme podle „délky l odvození výrazu s" definované jako počet aplikací induktivních pravidel potřebných k odvození s g SExp.
c
Důkaz: V bázi indukce ověříme vyhodnocení bázických prvků. Platí Val(n) — n, což skutečně odpovídá zvyklostem aritmetiky, c
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).   Takž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, 2013
17/20
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 Q 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 g /. Pak relace f]ieI Rí má vlastnost V.c
Fakt: Libovolná kombinace vlastností reflexivita, symetrie, tranzitivita je uzavíratelná vlastnost.
Antisymetrie není uzavíratelná vlastnost, c
Věta 6.9. 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 5 R na M majících vlastnost V existuje infimum Ry (vzhledem k množinové inkluzi), které samo má vlastnost V.
Tuto „nejmenší" relaci Ry s vlastností V nazýváme V-uzávěr relace R.
Petr Hliněný,  Fl MU Brno, 2013
18/20
Fl: IB000: Skládání a Funkce
Tvrzení 6.10. Nechť i? je binární relace na M. Pak platí následující poznatky.
• Reflexivní uzávěr i? je přesně relace R U {(x,x) | x £ M}x
• Symetrický uzávěr R je přesně relace
i?= | G i? nebo G
• Tranzitivní uzávěr R je přesně relace i?+ = U£i Tl{R), kde Tje funkce, která pro každou binární relaci S vrátí relaci
T(5) = S U {(x,z) | existuje y takové, že (x, y), (y, z) £ S*}
a 71 = 7~ ° ' • • ° Tje *-krát iterovaná aplikace funkce T■ c
• Reflexivní a tranzitivní uzávěr R je přesně relace R* = Q+, kde Q je reflexivní uzávěr R.n
• Reflexivní, symetrický a tranzitivní uzávěr R (tj. nejmenší ekvivalence ob-sáhující i?) je přesně relace (Q)+, kde Q je reflexivní uzávěr i?.
• Na pořadí aplikování uzávěrů vlastností záleží!
Petr Hliněný,  Fl MU Brno, 2013
19/20
Fl: IB000: Skládání a Funkce
Neformálně:
• F-uzávěr relace je vlastně daný induktivní definicí podle vlastnosti V. c
• Význam reflexivních a symetrických uzávěrů je z předchozího zřejmý, c
• 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 i? 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, c
• A jak bylo dříve řečeno, antisymetrický uzávěr relace prostě nemá smysl.
• Například buď R C N x N definovaná takto: R = {(i,i + 1) | i £ N}. Pak R* je běžné lineární uspořádání < přirozených čísel.
c
c
Petr Hliněný,  Fl MU Brno, 2013
20/20
Fl: IB000: Skládání a Funkce