6   Skládání relací a funkcí
Vraťme se nyn í k latce Lekce 3. Z jej ího pokročilého obsahu jsme doposud velmi detailně probírali relace a jejich jednotlive vlastnosti. Nyn í se pod ívejme, jak lze relace mezi sebou „skladať1, coZ je například zakladn í technika prace s relacn ími databazemi.
datum	let	letadlo		pasažér	datum	let			
5.11.	OK535	CSA		Petr	5.11.	OK535		pasažér	letadlo
5.11.	AF2378	ČSA	O	Pavel	6.11.	OK535	—	Petr	CSA
5.11.	DL5457	ČSA		Jan	5.11.	AF2378		Josef	ČSA
6.11.	OK535	AirFrance		Josef	5.11.	DL5457			
6.11.	AF2378	AirFrance		Alena	6.11.	AF2378			
Je vsak i jine m ísto, kde jste se zajiste se skladan ím relac í setkali - jedna se o skladan í funkc í. Jak například spoc ítate na kalkulacce výsledek slozitejs ího vzorce? c
StruCný přehled lekce
* Přehled zakladn ích vlastnost í funkc í.
* Inverzn í relace a skladan í (binarn ích) relací, příklady.
* Skladan í funkcí (coby relací), specialne aplikovano na permutace.
* Induktivn í definice mnoZin a funkcí.
_;tr Hliněný.  FI MU Brno__
FI: IBGGG: Skládání a Funkcě
r.
Zopakování relací a funkcí
• Relace mezi množinami Ai, • • • , Ak, pro k € N, je libovolná podmnožina kartézského součinu
Pokud Ai = • • • = 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 f mezi A a B taková, že pro každe x € A existuje práve jedno y € B takove, že (x,y) € f .c
* Množina A se nažývá definiční obor a množina B obor hodnot funkce f. Funkcím se take říká zobrazeni.
* Místo (x,y) € f píšeme obvykle f (x) = y. Zápis
říká, že f je funkce s def. oborem A a oborem hodnot B. c
• Pokud nasí definici funkce upravíme tak, že požadujeme pro každe x € A nejváse jedno y € B takove, že (x,y) € f, obdržíme definici parciální funkce ž A do B.
R C Ai x • • • x Ak .
f : A ^ B
Petr Hliněný,  FI MU Brno
FI: IB000: Skládáni a Funkce
r.
6.1   Vlastnosti funkcí
Definice: Funkce f : A — B je
- injektivni (nebo take prosta) prave když pro každe x,y € A, x = y plat í,
- surjektivní(nebo také „na") právě když pro každé y € B existuje x € A takové, že f (x) = y;c
- bijektivni (vžáj. jednoznačná) právě když je injektivn ía souc. surjektivn í.c
Ukážky vlastnost í funkc í.
• Funkce plus : N x N —> N je surjektivn í, ale nen í prosta.c
• Funkce g : Z — N dana předpisem
že f (x) = f (y);
je bijektivn í.
• Funkce 0 :0
• Funkce 0 :0
0 je bijektivn í.c
[a, b} je injektivn í, ale nen í surjektivn í.
'etr Hliněný,  FI MU Brno
FI: IB000: Skládáni a Funkce
r.
6.2   Inverzní relace a skládání relací
Definice: Necht R C A x B je binární relace mezi A a B. Inverzní relace k relaci R se znaCí R-1 a je definována takto:
(R 1 je tedy relace mezi B a A.)c
Příklady inverzí pro relace-funkce.
• Inverzí bijektivní funkce f (x) = x +1 na 7L je funkce f-1(x) = x — 1.c
• Inverzí proste funkce f (x) = ex na H je parcialní funkce f-1(x) = lnx.c
• Funkce g(x) = x mod 3 nen í prosta na N, a proto jej í inverzí je „jen" relace
g-1 = {(a, b) | a = b mod 3}.
Konkrétně g-1 = {(0, 0), (0, 3), (0, 6),..., (1,1), (1, 4),..., (2, 2), (2, 5),... }. c
Tvrzení 6.1. Mejme funkci f : A —> B. Pak její inverzní relace f 1 je
a) parciální funkce právě když f je prostá, c 6) funkce práve kdyz f je bijektivní.
R
-i
{(b, a) | (a,b) € R}
Důkaz vyplývá přímo z definic funkcé a invérzé rélacé.
□
3etr Hliněný,  FI MU Brno
FI: IB000: Skládáni a Funkce
Definice 6.2. Složení (kompozice) relací R a S.
Nechť R C A x B a S C B x C jsou binarn í relace. Složení relac í R a S (v ťomťo porad í !) je relace S o R C A x C definovana ťakťo:
S o R = {(o, c) | exisťuje b € B ťakove, ze (a, b) € R, (b, c) € S}c
Složen í relací cťeme „R složeno s S" nebo (pozor na pořad í!) „S po R". c
Príklady skladan í relac í.
• Je-li
* A = {o, b},   B = {1, 2},   C = {X},
* R = {(o, 1), (b, 1), (b, 2)},   S = {(1,X)}, pak složen ím vznikne relace
* S o R = {(o,X), (b, X)}. c
• Složen ím funkc í h(x) = x2 a f (x) = x +1 na H vznikne funkce
f o h (x) = f (h(x)) = x2 + 1.c
• Slozen ím ťechze funkc í „naopak" ale vznikne funkce hof (x) = h(f (x)) = (x+1 )2.
Poznámka: Nepríjemne je, ze v nekťerych oblasťech maťemaťiky (například v algebře pri skladan í zobrazen í) se seťkame s prave opacnym zapisem skladan í, kdy se m ísťo S o R p íse R • S nebo jen RS.
Petr Hliněný,  FI MU Brno__FI: IB000: Skládáni a Funkce
6.3   Skládání relací
„v praxi"
Príklad 6.3. Skládání v relační databázi studentu, jejich předmětů a fakult.
Mejme dve binární relace - jednu R přiřazující studentům MU kody jejich zapsaných předmetů, druhou S přiřazující kody předmetů jejich mateřským fakultám.
R :
student (učo)	předmět (kód)
121334	MA010
133935	M4135
133935	IA102
155878	M1050
155878	IB000
S :
předmět (kód)	fakulta MU
MA010	Fl
IB000	Fl
IA102	Fl
M1050	PřF
M4135	PřF
Jak z těchto „tabulkových" relací zjistíme, kteří studenti mají zapsané předměty na kterých fakultach (třeba na FI)? c
Petr Hlíně
FI MU Brno
FI: IB000: Skládání a Funkce
Jedná se jednoduše o složení relací S o R. V našem příkladě třeba:
S o R :
student (učo)	fakulta MU
121334	Fl
133935	Fl
133935	PřF
155878	Fl
155878	PřF
□
Petr Hlii
FI MU Brno
FI: IB000: Skládání a Funkce
r.
Zobecněné skládání relací
Fakt (skládání relací vySSí arity): Mejme relace T C K x K2 x • • • x Kk
a U C L1 x L2 x ••• x Li, priCemz pro nejake m < min(k,l) platí L1 = Kfc_m+i, L2 = Kk_m+2,..., Lm = Kk. nPak relaci T lze s/oz/ř s relací U na zvolených m sloZkách L1,..., Lm („prekrytí") s pouZitím Definice 6.2 takto:
• PoloZme A = K1 x • • • x Kk_m, B = L1 x • • • x Lm a C = Lm+1 x • • • x Ll.
• PřísluSne relace pak jsou
* R = {(a,b) € A x B | (au,.. .afc_m,č>1,.. .bm) € T} a
* S = {(b, C) € B x C | (61, . . .bm,Cm+1, . . .Či) € U}. C
• Nakonec prirozene poloZme U om T ~ S o R, takZe vyjde U om T =
{(a, c) | ex. 6 € B, Ze (ai,... afc_m ,6i,...6m) € T a (61,... 6m, cm+i,... ci) € U}.
Schematicky pro snaZsí orientaci:
T C  K1 x
x Kk_mx    Kk_m+1 x
x Kk
UC
L1 x
x Lm   x Lm+1 x • • • x Li
U om T C K1 x
x Kk_ m x
x Lm+1 x • • • x Li
'etr Hliněný,  FI MU Brno
B
FI: IB000: Skládáni a Funkce
Příklad 6.4. 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), letecke spolecnosti si mezi sebou „delí" místa v letadlech, takze různe lety (podle kódů) jsou ve skutečnosti realizovíny stejným letadlem jedne ze spolecnosti. 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 palube stejního letadla? Prípadne, čí letadlo to bude? Odpovedi ním dí zase slození relací U o2 T, jak je posíno
výše.
pasažér	letadlo
Petr Josef	ČSA ČSA
U 02 T :
Zkuste se zamyslet, lze tyto dvě relace skládat ještě jinak? Co by pak bylo významem? □
ětr Hliněný.  FI MU Brno
FI: IB000: Skládání a Funkce
6.4   Skládání funkcí, permutace
Fakt: Mejme žobražen í (funkce) f : A — B a g : B — C. Pak jejich složením coby relací v tomto porad í vznikne žobražen i (g o f) : A — C definovane
(g o f )(x) = g(f (x)) -c
Jak napríklad na bežne kalkulacce vypocteme hodnotu funkce sin2 x ? c Slož íme (v tomto pořad í) „elementarn í" funkce f (x) = sin x a g(x) = x2.
Jak bychom na „elementarn í" funkce rožložili aritmeticky vyraž 2log(x2 + 1) ? c Ve spravnem pořad í složíme funkce fi(x) = x2, f2(x) = x +1, f3(x) = log x a f4(x) = 2x. c
A jak bychom obdobne vyjadrili složen ím funkc í aritmeticky vyraž sin x + cos x ? Opet je odpoved' přímocara, vežmeme „elementarn í" funkce g1(x) = sin x a g2(x) = cos x, a pak je „slož íme" dalsí funkc í h(x, y) = x + y. c Vid íme vsak, že takto pojate „skladan í" už nežapada hladce do naseho formalismu skladan í relac í.
Petr Hliněný,  FI MU Brno__FI: IB000: Skládáni a Funkce
Skládání permutací
Definice: Nechť permutace n mnoziny {1,2,..., n} je urcena seřazen ím jej ích prvku (pi,...,Pn). Pak n je zaroveř bijekťivn ím zobrazen ím {1,...,n} — {1,... ,n} definovanym předpisem n (i) = pj. c
Tud íz lze permuťace skládat jako relace podle Definice 6.2. c
Poznámka: Vsechny permuťace mnoziny {1, 2,..., n} spolu s operac í skladan í ťvorí grupu, zvanou symeťricka grupa Sn.
Permuťacn í grupy (podgrupy symeťricke grupy) jsou velice duleziťe v algebře, neboť kazda grupa je vlasťne isomorfn í nekťere permuťacn í grupe. c
Př íkladem permuťace vyskyťuj íc ím se v programaťorske praxi je ťřeba zobrazen í i — mod n ("inkremenť"). nČasťo se ťřeba lze seťkať (aniz si ťo mnohdy
uvedomujeme) s permuťacemi pri indexaci prvku pol í.
3etr Hliněný,  FI MU Brno__FI: IB000: Skládáni a Funkce
V kontextu pohledu na funkce a jejich skladaní coby relací si zavedeme jiný, nazornejSí, zpusob zapisu permutací - pomocí jejich cyklu.
Definice: Necht n je permutace na mnozine A. Cyklem v n rozumíme posloupnost (ai, a2,..., ak) ruznych prvku A takovou, ze n(aj) = ai+i pro i = 1,2,..., k — 1 a n(ak) = ai.
Jak nazev napovída, v zapise cyklu (ai,a2,..., ak) není dulezite, kterym prvkem zacneme, ale jen dodrzení cyklickeho pořadí. Cyklus v permutaci muze mít i jen jeden prvek (zobrazeny na sebe).
Například permutace (5, 3,4, 8, 6,1, 7, 2) je zakreslena svymi cykly vyse.
FI: IB000: Skládání a Funkce
Jetr Hliněný.  FI MU Brno
Veta 6.5. Kazdou permutaci n na konečné množině A lze zapsat jako složení cyklu na disjunktních podmnožinéch (rozkladu) A. □
Důkaz: Vězměmě libovolný prvék ai € A a itěrujěmě zobrazení a2 = n(ai), a3 = n(a2), atd., az sé dostaneme „zpět" k ak+i = n(ak) = ai. ProC ténto procés skonCí? Protozě A jě koněCna a tud íz kě zopakovan í něktěrěho prvku ak+i musí dojít. Nadto jě n prosta, a proto němuzě nastat n(ak) = aj pro j > 1. Takto z ískamě prvn í cyklus (ai,..., ak). □
Induktivně pokracujěmě s hlědaním dalsích cyklu vě zbylě mnozině A \ {ai,..., ak}, dokud nězustaně prazdna. □ □
Značení pěrmutací cykly: Něcht sě pěrmutacě n podlě Věty 6.5 sklada z cyklu (ai,..., ak), (fy,..., fy) az třěba      ..., zm). Pak zapísěmě
n = ((ai,..., afc) (bi,..., fy)... (zi,..., Zm) )□ .
Primitivní psěudonahodně gěněratory v pocítacích itěrují z nahodněho pocatku pěr-mutaci danou vztahěm i ^ (i + p) mod q. Jě pochopitělně, zě tato pěrmutacě něsmí obsahovat kratkě cykly, lěpě řěčěno, měla by sě skladat z jědiněho (dlouhěho) cyklu.
Petr Hliněný,  FI MU Brno 13 FI: IB000: Skládání a Funkce
r.
Příklad 6.6. Ukázka skládání permutací daných svými cykly.
Vežmeme 7-prvkovou permutaci (5, 3, 4, 2, 6,1, 7). Ta se rožkládá na tři cykly (1, 5,6), (2,3,4) a (7). Jiná permutace (3,4, 5,6, 7,1,2) se skládá ž jedineho
cyklu (1, 3, 5, 7, 2, 4, 6). □
Nyní urcíme složení techto dvou permutací (žápisem cykly):
((1, 5, 6)(2, 3, 4)(7)) o ((1, 3, 5, 7, 2, 4, 6)) = ((1, 4)(2)(3, 6, 5, 7))
(Nežapomínejme, že první se ve složení aplikuje prava permutace!) □ Postup skladan í jsme pouřžili nasledovny: • 1 se žobraží v permutaci vpravo na 3 a pak vlevo na 4. □
• Nasledne 4 se žobraží na 6 a pak na 1. Tím „užavreme" první cyklus (1, 4).c
• Dale se 2 žobraží na 4 a pak hned žpet na 2, tj. ma samostatny cyklus. □
Zbyly cyklus (3, 6, 5, 7) urcíme analogicky.
□
Petr Hliněný,  FI MU Brno
FI: IB000: Skládáni a Funkce
6.5   Induktivní definice množin a funkcí
Přímým zobecnen ím rekurentn ích definic je nasleduj ící koncept. Definice 6.7. Induktivní definice mnoziny.
Jedna se obecne o popis (nejake) mnoziny M v nasleduj ícím tvaru:
• Je dano nekolik pevnych (bázických) prvku a1,a2,..., ak € M. c
• Je dan soubor induktivních pravidel typu
Jsou-li (libovolne prvky) x1,...,xg € M, pak take y € M. V tomto případe je y typicky funkc í y = /i(x1,..., xi). c
Pak nase induktivně definovaná množina M je urcena jako nejmensí (inkluz í) mnozina vyhovuj íc í temto pravidlum.
Vid íte podobnost teto definice s uzaverem relace? (Veta 5.8.) c
Pro nejblizs í příklad induktivn í definice se obrat íme na mnozinu vsech přirozenych c ísel.
- 0 € N
- Je-li i €Vl, pak take i +1 €Vl.
Pětr Hliněný.  FI MU Brno__FI: IB000: Skládáni a Funkcě
Pro každe y € N mužeme definovat jinou množinu My C N induktivne takto:
- y   €   My .
- Jestliže x € My a x + 1 je liche, pak x + 2 € My. Pak například M3 = {3}, nebo M4 = {4 + 2i | i € N}. □
Definice: Řekneme, že dana induktivní definice množiny M je jednoznačná, prave když každy prvek M lže odvodit ž bažickych prvku pomocí induktivních pravidel prave jedním žpusobem. □
Definujme množinu M C N induktivne takto:
- 2, 3 € M.
- Jestliže x, y € M a x < y, pak take x2 + y2 a x • y jsou prvky M.
Proc tato induktivní definice není jednožnacná? Například císlo 8 € M lže odvodit žpusobem 8 = 2 • (2 • 2), ale žaroveř žcela jinak 8 = 22 + 22.
V cem tedy spocíva duležitost jednožnacnych induktivních definic množin?
Petr Hlinený,  FI MU Brno
FI: IB000: Sklaádaánái a Funkce
r.
Definice 6.8. Induktivní definice funkce z induktivní mnoziny. Necht mnozina M je dína jednoznacnou induktivní definicí. Pak číkíme, ze funkce F : M — X je definovína induktivne (vzhledem k induktivní definici M), pokud je receno:
• Pro kazdy z bízickych prvku a\,a2,... ,ak € M je urceno F (aj) = Cj. c
• Pro kazde induktivní pravidlo typu
"Jsou-li (libovolné prvky) x\,... ,xg € M, pak také / (x\,... ,xe) € M"
Pro příklad sé podívejme třéba do manuálu unixového příkazu test EXPRESSION: EXPRESSION is true or false and sets exit status.    It is one of:
jé définovano
JF( /(xi,..., xi)) na zakladé hodnot F(xi),..., F(xi).c
! EXPRESSION
EXPRESSION is false
EXPRESSION1 -a EXPRESSION2 EXPRESSION1 -o EXPRESSION2 [-n] STRING STRING1 = STRING2
both EXPRESSI0N1 and EXPRESSI0N2 are true either EXPRESSI0N1 or EXPRESSI0N2 is true the length of STRING is nonzero the strings are equal
'etr Hliněný,  FI MU Brno
FI: IB000: Skládáni a Funkce
Induktivní definice se „strukturální" indukcí Príklad 6.9. Jednoduché aritmetické výražy
Nechť (abeceda) S = {0,1, 2, 3, 4, 5, 6, 7, 8, 9, 0, ©, (,)}. Definujme mnozinu jednoduchých váražU SExp C S* indukťivne ťakťo:
- Dekadicky zapis kazdeho přirozeneho císla n je prvek SExp.
- Jesťlize x,y € SExp, pak ťake (x) 0 (y) a (x) © (y) jsou prvky SExp. c
(Jak vid íme, d íky „zavorkovan í" je ťaťo indukťivn í definice jednoznacna.)
Pro „vyhodnocen í" vyrazu pak definujme funkci Val: SExp — N indukťivne:
- Bazicke prvky: Val(n) = n, kde n je dekadicky zapis přirozeneho císla n. c
- Prvn í indukťivn í pravidlo: Val((x) © (y)) = Val(x) + Val(y).
- Druhe indukťivn í pravidlo: Val((x) 0 (y)) = Val(x) • Val(y). c
(Tímťo zpusobem jsme nasim vyrazum vlasťne přiřadili jejich „vyznam", semanťiku.) □
Petr Hlinený,  FI MU Brno
FI: IB000: Sklaádaánái a Funkce
-N
Příklad 6.10.  Důkaz správnosti přiřazeného „významu" Val: SExp — N.
Veta. Pro kazdý výraz s € SExp je hodnota Val(s) číselně rovna vásledku vyhodnocení várazu s podle běžných zvyklostí aritmetiký.c
Matematickou indukcí: Na rožd íl od dříve probíraných příkladu žde nevid íme žadny celocíselny „parametr n", a proto si jej budeme muset nejprve definovat.c
Nasi indukci tedy povedeme podle „delky l odvožen í vyražu s" definovane jako pořcet aplikac í induktivn ích pravidel potřrebnych k odvožen í s € SExp.
Takto aplikovane matematicke indukci se casto říka štrukturálni indukce. c
Důkaz: V baži indukce overíme vyhodnocen í bažickych prvku, což jsou žde dekadižke žapisy přiroženych císel. Platí Val(n) = n, což skutecne odpovída žvyklostem aritmetiky. c
V indukcn ím kroku se pod ívame na vyhodnocen í Val((x) © (y)) = Val(x) + Val(y). Podle bežnych žvyklost í aritmetiky by hodnota Val((x) © (y)) mela byt rovna souctu vyhodnocen í vyražu x, což je podle indukcn ího předpokladu rovno Val(x) (x ma žřejme kratsí delku odvožen í), a vyhodnocen í vyražu y, což je podle indukřcn ího přredpokladu rovno Val(y). Takřže skuteřcnře Val((x)©(y)) = Val(x) + Val(y). Druhe pravidlo Val((x) 0 (y)) se doresí analogicky. G
Petr Hlinený,  FI MU Brno___FI: IB000: Skládáni a Funkce ^