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? 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 Ai,--- ,Ak, 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. c • (Totální) funkce z množiny A do množiny B je relace / mezi A a B taková, že pro každé x 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, 2014 4/21 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, 2014 5/21 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, 2014 6/21 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, 2014 7/21 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, 2014 8/21 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, 2014 9/21 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 = ^{ajS) = a±. Proč tento proces skončí? Protože A je konečná a tudíž ke zopakování některého prvku dk+i musí dojít. Nadto je tt prostá, a proto nemůže nastat 7r(afc) = aj 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' = A\{a±,..., afc}, dokud nezůstane prázdná. V tomto indukčním kroku si musíme uvědomit, že tt omezené na nosnou množinu A' je stále permutací podle definice. □ Značení permutace jejími cykly: Nechť se permutace tt podle Věty 6.3 skládá z cyklů (di,..., cifc), (61,..., bi) až třeba (z±,..., zm). Pak zapíšeme 7t = ( (ai, ..., afe) (Ďi,..., bt) ... {z-í, ..., zm) ) . Petr Hliněný, Fl MU Brno, 2014 10/21 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 tt = (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!) c Postup skládání jsme použili následovný: * 1 se zobrazí v permutaci vpravo na 3 a pak vlevo na 4. c * 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, 2014 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.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. Petr Hliněný, Fl MU Brno, 2014 12/21 Fl: IB000: Skládání a Funkce 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ě. - 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, 2014 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, 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, 2014 14/21 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±, a2,..., £ M je určeno J-{a,i) = C{. c • Pro každé induktivní pravidlo typu "Jsou-li (libovolné prvky) x±,..., xi £ M, pak také f(x±,..., xi) G M" je definováno !F[ f{x\,. .., xi)) na základě hodnot T(x\),. .., ^F(xi).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 bazický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 ze („zkomolením") slova předchozího hráče. Výsledkem hry pak je hodnota-slovo posledního hráče. Petr Hliněný, Fl MU Brno, 2014 15/21 Fl: IB000: Skládání a Funkce Pro další 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 EXPRESSI0N1 -a EXPRESSI0N2 EXPRESSI0N1 -o EXPRESSI0N2 [-n] STRING STRING1 = STRING2 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 c No, poněkud 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 velmi špatně, ale přesto jde o pěknou ukázku z praktického života informatika. Petr Hliněný, Fl MU Brno, 2014 16/21 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 E = {0,1, 2, 3,4, 5, 6, 7, 8, 9, 0, ©, (,)}. Definujme množinu jednoduchých výrazů SExp C S* induktivně takto: - Dekadický zápis každého přirozeného čísla n je prvek SExp. c - Jestliže x,y G SExp, pak také (x) 0 (y) a (x) © (y) jsou prvky SExp. c - 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, c Pro přiřazení „významu", tj. sémantiky aritmetického výrazu, následně definujme funkci Val: SExp —> N induktivně takto: c - 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 („hodnotou") uvedených aritmetických výrazů? □ Petr Hliněný, Fl MU Brno, 2014 17/21 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. Naši indukci tedy povedeme podle „délky í 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í bazický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). nPodle 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). nTakž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, 2014 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 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. Ireflexivita a antisymetrie nejsou uzavíratelné vlastnosti, 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, 2014 19/21 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 RU {(x,x) | x G M}.c • Symetrický uzávěr R je přesně relace R= {(x,y) | (x,y) G R nebo (y, x) G i?}.c • Tranzitivní uzávěr R je přesně relace i?+ = U£i Tl{R), kde T je funkce, která pro každou binární relaci S vrátí relaci T(5) = S U {(x, z) j existuje y takové, že (x, y), (y, z) G S} a Tl = 7~ ° • • • ° Tje i-krát iterovaná aplikace funkce T■ c j • Reflexivní a tranzitivní uzávěr i? je přesně relace R* = Q+, kde Q je reflexivní uzávěr i?.c • Reflexivní, symetrický a tranzitivní uzávěr i? (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ží! (Zhruba řečeno, tranzitivní uzávěr aplikujeme coby poslední.) Petr Hliněný, Fl MU Brno, 2014 20/21 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ě nedává smysl. c • 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. Petr Hliněný, Fl MU Brno, 2014 21/21 Fl: IB000: Skládání a Funkce