8 Skládání relací a funkcí Látku o relacích zakončíme poznatky o obracení a skládání relací mezi sebou. Kde jste se již intuitivně setkali se skládáním funkcí-jak například spočítáte na kalkulačce výsledek složitějšího vzorce? A jinde? nCo třeba relační databáze? Stručný přehled lekce * Inverze a skládání relací v obecném pojetí. Praktické použití. * Přehled základních vlastností funkcí. * Skládání funkcí (coby relací), speciálně aplikováno na permutace. Petr Hliněný, Fl MU Brno, 2020 1/18 Fl: IB000: Skládání a Funkce 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. 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 definičním oborem A a oborem hodnot podmnožinou B. Petr Hliněný, Fl MU Brno, 2020 2/18 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. Petr Hliněný, Fl MU Brno, 2020 3/18 Fl: IB000: Skládání a Funkce Inverze a skládání relací Ve výkladu se nyní vrátíme k obecnému pojetí relací mezi dvěma množinami. Definice: Nechť R C A x B je binární relace mezi A a B. Inverzní relace k relaci R se značí R~x a je definována takto: R-1 = {(6, a) | (a, 6) 6 iž} iž: -i iž 1 je tedy relace mezi B a A. Petr Hliněný, Fl MU Brno, 2020 4/18 Fl: IB000: Skládání a Funkce Definice skládání Definice 8.1. Složení (kompozice) relací R a S. Nechť RCAxBaSCBxC 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) existuje b £ S takové, že (a, 6) £ iž, (6, c) £ £} Složení relací čteme „R složeno s S" nebo (pozor na pořadí!) „5 po iž". Petr Hliněný, Fl MU Brno, 2020 5/18 Fl: IB000: Skládání a Funkce ■r Několik matematických příkladů skladaní relací nasleduje zde. • Je~'' *A = {a,b}, B = {1,2}, C = {X,Y}, * R = {(a, 1), (b, 1), (b, 2)}, S = {(l,X)}, pak složením vznikne relace * SoR = {(a,X),(b,X)}. □ • Složením funkcí h(x) = x2 a f (x) = x + 1 na R vznikne funkce (f o h) (x) =f(h(x)) = x2 + l.u • Složením těchže funkcí „naopak" ale vznikne funkce (h o f) (x) = h(f (x)) = (x + lf.u Poznámka: Nepříjemné je, že v některých oblastech matematiky (například v algebře při skladaní 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, 2020 6/18 Fl: IB000: Skládání a Funkce r Tvrzení 8.2. Nechť RCAxBaSCBxC jsou binární relace. Pak inverzí složené relace S o R je relace A B R: C :S vy (SoR)-1 = DB"1 o S"1. -1_ o-l Petr Hliněný, Fl MU Brno, 2020 7/18 Fl: IB000: Skládání a Funkce 8.2 Praktické použití skládání Příklad 8.3. Skladaní v relační databázi studentů, jejich předmětů a fakult. Mějme dvě binární relace - jednu R přiř. 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 z těchto „tabulkových" relací zjistíme, kteří studenti mají zapsané předměty na kterých fakultách (třeba na Fl)? 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, 2020 8/18 Fl: IB000: Skládání 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 Kk a U C Li x Z/2 x • • • x Lč, přičemž pro nějaké m < min(fc,^) platí Li = Ä&_m+i, L2 = Kk_m+2, • • • 5 — íífe- ^Pak relaci T lze s/oz/ŕ s relací Č7 na zvolených m složkách Li,... ,Lm („překrytí") s použitím Definice 8.1 takto: • Položme A = K\ x • • • xKk_m, B = L\ x • • • xLm a C = Lm+i x • • • xl^. • Příslušné relace pak jsou * R = b) G A x B I (ai,... a^_m, 61,... 6m) G T} a * S = {(b,Č) e B x C \ (6i,...6m,cm+i,...Q) G f/}. □ • Nakonec přirozeně položme U omT ~ S o R, takže vyjde U omT — {(a, č) I ex. 6 G B, že (ai,.. . afc_m, 61,... 6m) G T a (61,... 6m,cm+i,... q) G í/} . Schematicky pro snadnější orientaci: ?7 C U om T C |iTi x • • • x Kk_mx Kk_m+1 x • • • x Kk L\ x • • • x Lm xLm+i x • • • x L£ [^1 x • • • x Kk_m\ x x Lm+i x • • • x L£ Petr Hliněný, Fl MU Brno, 2020 9/18 Fl: IB000: Skládání a Funkce Příklad 8.4. Skládání v relační databázi pasažérů a letů u let. 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 CSA 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 popsáno výše. pasažér letadlo Petr Josef Pavel CSA ČSA AirFrance □ Petr Hliněný, Fl MU Brno, 2020 10/18 Fl: IB000: Skládání a Funkce r 8.3 Vlastnosti funkcí Definice 8.5. 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, 2020 11/18 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í.c • Funkce 0:0—^ {a, b} je injektivní, ale není surjektivní.c Příklad 8.6. Dokázali byste nalézt jednoduše (tj. „hezky") vypočitatelnou bi-jektivní funkci N N x N ? t Příklad 8.7. Pro ja/ce hodnoty parametru a, 6 je funkce f (x) = ax3+3x2+bx+l z R c/o R injektivní či surjektivní? Petr Hliněný, Fl MU Brno, 2020 12/18 Fl: IB000: Skládání a Funkce Inverze funkce Inverze funkce je dána definicí inverze relace z Oddílu 8.1. 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í 8.8. 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í 8.9. 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, 2020 13/18 Fl: IB000: Skládání a Funkce 8.4 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, 2020 14/18 Fl: IB000: Skládání a Funkce Skládání permutací Značení: Nechť permutace ty množiny {1,2, je určena seřazením jejích prvků jako (pi,P25 • • • ,Pn)- Pak ty je zároveň bijektivním zobrazením {1,... , n} —> {1,..., n} definovaným předpisem ty{i) = p{. Permutace lze skládat jako relace (funkce) podle Definice 8.1 a platí následující: Tvrzení 8.10. Mějme permutace ty a a množiny {1,2, Pak jejich složení a o ty je opět permutací množiny {1,2,..., n}. Poznámka: Všechny permutace množiny {l,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í. Abychom postihli obě tyto podoby, budeme také zapisovat □ Petr Hliněný, Fl MU Brno, 2020 15/18 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ů. □ • V zápise cyklu permutace přirozeně 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). □ Definice: Nechť tv je permutace na množině A. Cyklem v tv rozumíme posloupnost (ai, a,2,... , a*;) různých prvků A takovou, že Tv{ai) = a^+i pro i = 1, 2,... , k — 1 a 7r(a&) = a\. Petr Hliněný, Fl MU Brno, 2020 16/18 Fl: IB000: Skládání a Funkce ■r Reprezentace permutací jejich cykly Věta 8.11. Každou permutaci tv 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\ £ A a iterujeme zobrazení a2 — 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 ti 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 tv 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 8.11 skládá z cyklů (ai,..., a^), ..., bi) až třeba (zi,..., zm). Pak zapíšeme 7T = (<*i Petr Hliněný, Fl MU Brno, 2020 17/18 Fl: IB000: Skládání a Funkce Příklad 8.12. Ukázka skládání permutací daných svými cykly. Vezměme 7-prvkovou permutaci zadanou seřazením ty = (3,4,5,6,7,1,2), neboli rozšířeně zapsanou jako (3456712)- Ta se skládá z jediného cyklu (1,3,5,7,2,4,6). Jiná permutace daná seřazením a = (5, 3,4, 2,6,1, 7), neboli (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, 2020 18/18 Fl: IB000: Skládání a Funkce