6 Skládání relací a funkcí Vraťme se nyní k látce Lekce 3. Z jejího pokročilého obsahu jsme doposud velmi detailně probírali relace a jejich jednotlivé vlastnosti. Nyní se podívejme, jak lze relace mezi sebou „skládat", což je například základní technika práce s relačními databázemi. Je však i jiné místo, kde jste se zajisté se skládáním relací setkali - jedná se o skládání funkcí. Jak například spočítáte na kalkulačce výsledek složitějšího vzorce? c Stručný přehled lekce * Přehled základních vlastností funkcí. * Inverzní relace a skládání (binárních) relací, příklady. * Skládání funkcí (coby relací), speciálně aplikováno na permutace. * Induktivní definice množin a funkcí. Petr Hliněný, Fl MU Brno, 2012 1/33 Fl: IB000: Skládáni a Funkce Zopakování relací a funkcí • 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 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, 2012 3/33 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, 2012 4/33 Fl: IB000: Skládáni a Funkce 6.2 Inverzní relace a skládání relací Definice: Nechť R C A x B je binární relace mezi A a B. Inverzní relace k relaci R se značí R^1 a je definována takto: R-1 = {(b,a) | (a, 6) € R} i? je tedy relace mezi B a, A\ Petr Hliněný, Fl MU Brno, 2012 5/33 Fl: IB000: Skládáni a 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. (T1 = {(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, 2012 6/33 Fl: IB000: Skládáni a Funkce Definice skládání Definice 6.3. Složení (kompozice) relací R a S. Nechť RQAxBaSQBxC jsou binární relace. Složení relací R a S (v tomto pořadí!) je relace S o R C A x C definovaná takto:c S o R = {(a, c) I existuje b G B takové, že (a, b) G R, (b, c) G S} Složení relací čteme „R složeno s S" nebo (pozor na pořadí!) „S po R". Petr Hliněný, Fl MU Brno, 2012 7/33 Fl: IB000: Skládáni a Funkce Několik matematických příkladů skládání relací následuje zde. • J^'' *A = {a,b}, B = {1,2}, C = {X,Y}, * R = {(a, 1), (6,1), (6, 2)}, 5 = {(1,X)}, pak složením vznikne relace * 5ofí = {(a,I),(6,I)}. • Složením funkcí h(x) = x2 a /(x) = x + 1 na R vznikne funkce (foh)(x)=f(h(x)) = X2 + 1.E • Složením těchže funkcí „naopak" ale vznikne funkce (hof) (x) = h(f(x)) (x + 1)2. Poznámka: Nepříjemné je, že v některých oblastech matematiky (například v algebře při skládání zobrazení) se setkáme s právě opačným zápisem skládání, kdy se místo S o R píše R ■ S nebo jen RS. Petr Hliněný, Fl MU Brno, 2012 8/33 Fl: IB000: Skládáni a Funkce 6.3 Skládání relací „v praxi" Příklad 6.4. Skládání v relační databázi studentů, jejich předmětů a fakult. Mějme dvě binární relace - jednu R při r. studentům MU kódy jejich zapsaných předmětů, druhou S přiř. kódy předmětů jejich mateřským fakultám. R : student (učo) předmět (kód) předmět (kód) fakulta MU 121334 MA010 MA010 Fl 133935 M4135 S : IB000 Fl 133935 IA102 IA102 Fl 155878 M1050 M1050 PřF 155878 IB000 M4135 PřF Jakž těchto „tabulkových" relací zjistíme, kteří studenti majízapsané předměty na kterých fakultách (třeba na Fl)? c Jedná se jednoduše o složení relací S o R. V našem příkladě třeba: SoR ■ student (učo) fakulta MU 121334 Fl 133935 Fl 133935 PřF 155878 Fl 155878 PřF Petr Hliněný, Fl MU Brno, 2012 9/33 Fl: IB000: Skládáni a Funkce Zobecněné skládání relací Definice: (skládání relací vyšší arity): Mějme relace T C K\ x K2 x • • • x K\. a U C L\ x L2 x • • • x L i, přičemž pro nějaké m < min(fc,ľ) platí L\ = Kk-m+i,L2 = Kk-m+2, ■ ■ ■ 1 Lm = Kk- Pak relaci T lze složit s relací U na zvolených m složkách Li,... ,Lm („překrytí") s použitím Definice 6.3 takto: • Položme A = K\x• • • xKk-m, B = Lľx - ■ -xLm a C = Lm+Í x■ ■ ■ xLe. • Příslušné relace pak jsou * R = {(a, b) e A x B \ (ax,... ak^m, bx,... bm) g T} a * 5 = {(6, č) g -B x C j 6m,cm+i,... q) g f/}. • Nakonec přirozeně položme Č7 om T ~ 5 o i?, takže vyjde U omT = {(a, č) I ex. 6 e B, že (ai,.. .afc-m,&i, • • -&m) € T a (61,... ce) e U}. Schematicky pro snažší orientaci: T C U c Petr Hliněný, Fl MU Brno, 2012 Ä"l X • • • X Kk_mX Kfc-m+l X • • • X Kfc Li x---xLm xLm+1x---xLe -Kl X • • • X Kfc-m x x Lm+i X ■■■ X Li ---„--'---- >-v-' B C Fl: IB000: Skládání a Funkce Příklad 6.5. Skládání v relační databázi pasažérů a letů u leteckých společností. Podívejme se na příklad hypotetické rezervace letů pro cestující, relace T. Jak známo (tzv. codeshare), letecké společnosti si mezi sebou „dělí" místa v letadlech, takže různé lety (podle kódů) jsou ve skutečnosti realizovány stejným letadlem jedné ze společností. To zase ukazuje relace U. T : pasažér datum let datum let letadlo Petr 5.11. OK535 5.11. OK535 ČSA Pavel 6.11. OK535 U : 5.11. AF2378 ČSA Jan 5.11. AF2378 5.11. DL5457 ČSA Josef 5.11. DL5457 6.11. OK535 AirFrance Alena 6.11. AF2378 6.11. AF2378 AirFrance Ptáme-li se nyní, setkají se Petr a Josef na palubě stejného letadla? Případně, čí letadlo to bude? Odpovědi nám dá složení relací U o2T, jak je posáno výše. pasažér letadlo Petr Josef Pavel ČSA ČSA AirFrance □ Petr Hliněný, Fl MU Brno, 2012 11/33 Fl: IB000: Skládání a Funkce 6.4 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, 2012 12/33 Fl: IB000: Skládání 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 6.3. 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, 2012 13/33 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ť 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, 2012 14/33 Fl: IB000: Skládání a Funkce Reprezentace permutací jejich cykly Věta 6.6. 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.6 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, 2012 15/33 Fl: IB000: Skládání a Funkce Příklad 6.7. 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!) 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, 2012 16/33 Fl: IB000: Skládání a Funkce 6.5 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.8. 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, 02,..., afc £ M. c • Je dán soubor induktivních pravidel typu Jsou-li (libovolné prvky) x±,..., x^ 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. Poznámka: Vidíte podobnost této definice s uzávěrem relace? (Věta 5.10.) Petr Hliněný, Fl MU Brno, 2012 17/33 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}. Petr Hliněný, Fl MU Brno, 2012 18/33 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 bazický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číva 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, 2012 19/33 Fl: IB000: Skládání a Funkce Definice 6.9. 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, 2012 20/33 Fl: IB000: Skládání a Funkce Induktivní definice se „strukturální" indukcí Příklad 6.10. 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. - Jestliže x, y G SExp, pak také (x)o(y) a (x)©(y) jsou prvky SExp. n(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: 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 uvedených aritmetických výrazů? □ Petr Hliněný, Fl MU Brno, 2012 21/33 Fl: IB000: Skládání a Funkce Příklad 6.11. 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í 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). 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). 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, 2012 22/33 Fl: IB000: Skládání a Funkce