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?   Co 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, 2018
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 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 definičním oborem A a oborem hodnot B.
Petr Hliněný, Fl MU Brno, 2018
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, 2018
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, 2018
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, 2018
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, 2018
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, 2018
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, 2018
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 5, že (au .. .ak-m, 61,... 6m) G T a (61,... 6m,cm+i,... q) G í/} . Schematicky pro snadnější orientaci:
?7 C U omT C
\KX x • • • x Kfe_mx   Kk_m+1 x     x Kk		
	Li    x • • • x Lm    xLm+i x • • • x L£	
[^1 X • • • X Kfc-ml x                                            x Lm+i X • • • X L£ b              v              A           s-v-'          K /|		
Petr Hliněný, Fl MU Brno, 2018 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, 2018
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, 2018
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, 2018
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, 2018
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, í2{x) = x + 1, fe{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, 2018
14/18
Fl: IB000: Skládání a Funkce
■r
Skládání permutací
Definice: 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{.
Abychom postihli obě tyto podoby, budeme také používat zápis (^'^'"'jT )■ D 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—> 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, 2018
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ů.
□
• Například permutace (sf^g'si'n) Je vkreslena svými cykly výše.
• 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, g&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, 2018
16/18
Fl: IB000: Skládání a Funkce
■r
Reprezentace permutací jejich cykly
Věta 8.11. 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\ £ A a iterujeme zobrazení 0,2 = vr(ai), 0,3 = 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^) = aj 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 8.11 skládá z cyklů (ai,..., a^), (61,..., bi) až třeba (zi,..., zm). Pak zapíšeme
7t =
(<*i
dk) {bi
bi) ... (zi
Petr Hliněný, Fl MU Brno, 2018
17/18
Fl: IB000: Skládání a Funkce
■r
Příklad 8.12. Ukázka skládání permutací daných svými cykly.
Vezměme 7-prvkovou permutaci ty = (3,4,5,6,7,1,2), rozšířeně zapsanou s pomůckou jako (3 4      í'D- 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), neboli (5 3'42 617) > 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, 2018
18/18
Fl: IB000: Skládání a Funkce