Petr Hliněný, FI MU Brno 1 FI: IB000: Skládání a Funkce
6 Vlastnosti funkcí a Skládání relací6 Vlastnosti funkcí a Skládání relací
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.
datum let letadlo
5.11. OK535 ČSA
5.11. AF2378 ČSA
5.11. DL5457 ČSA
6.11. OK535 AirFrance
6.11. AF2378 AirFrance

pasažér datum let
Petr 5.11. OK535
Pavel 6.11. OK535
Jan 5.11. AF2378
Josef 5.11. DL5457
Alena 6.11. AF2378
=
pasažér letadlo
Petr ČSA
Josef ČSA
. . . . . .
2
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? 2
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ý, FI MU Brno 2 FI: IB000: Skládání a Funkce
Zopakování relací a funkcí
* Relace mezi množinami A1,    , Ak, pro k  , je libovolná podmnožina
kartézského součinu
R  A1 ×    × Ak .
Pokud A1 =    = Ak = A, hovoříme o k-ární relaci R na A. 2
* (Totální) funkce z množiny A do množiny B je relace f mezi A a B taková,
že pro každé x  A existuje právě jedno y  B takové, že (x, y)  f.2
 Množina A se nazývá definiční obor a množina B obor hodnot funkce f.
Funkcím se také říká zobrazení.
 Místo (x, y)  f píšeme obvykle f(x) = y. Zápis
f : A  B
říká, že f je funkce s def. oborem A a oborem hodnot B. 2
* Pokud naší definici funkce upravíme tak, že požadujeme pro každé x  A
nejvýše jedno y  B takové, že (x, y)  f, obdržíme definici parciální
funkce z A do B.
Petr Hliněný, FI MU Brno 3 FI: IB000: Skládání a Funkce
6.1 Vlastnosti funkcí6.1 Vlastnosti funkcí
Definice: Funkce f : A  B je
­ injektivní (nebo také prostá) právě když pro každé x, y  A, x = y platí,
že f(x) = f(y);2
­ surjektivní (nebo také ,,na ) právě když pro každé y  B existuje x  A
takové, že f(x) = y;2
­ bijektivní (vzáj. jednoznačná) právě když je injektivní a souč. surjektivní.2
Ukázky vlastností funkcí.
* Funkce plus : ×    je surjektivní, ale není prostá.2
* Funkce g :   daná předpisem
g(x) =
-2x - 1 jestliže x < 0,
2x jinak
je bijektivní.2
* Funkce  :    je bijektivní.2
* Funkce  :   {a, b} je injektivní, ale není surjektivní.
Petr Hliněný, FI MU Brno 4 FI: IB000: Skládání a Funkce
6.2 Inverzní relace a skládání relací6.2 Inverzní relace a skládání relací
Definice: Nechť R  A × 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, b)  R}
(R-1 je tedy relace mezi B a A.)2
Příklady inverzí pro relace­funkce.
* Inverzí bijektivní funkce f(x) = x + 1 na je funkce f-1
(x) = x - 1.2
* Inverzí prosté funkce f(x) = ex
na  je parciální funkce f-1
(x) = ln x.2
* Funkce g(x) = x mod 3 není prostá na , 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), . . .}. 2
Tvrzení 6.1. Mějme funkci f : A  B. Pak její inverzní relace f-1 je
a) parciální funkce právě když f je prostá, 2
b) funkce právě když f je bijektivní.
Důkaz vyplývá přímo z definic funkce a inverze relace. 2
Petr Hliněný, FI MU Brno 5 FI: IB000: Skládání a Funkce
Definice 6.2. Složení (kompozice) relací R a S.
Nechť R  A × B a S  B × C jsou binární relace. Složení relací R a S
(v tomto pořadí!) je relace S  R  A × C definovaná takto:
S  R = {(a, c) | existuje b  B takové, že (a, b)  R, (b, c)  S}2
Složení relací čteme ,,R složeno s S nebo (pozor na pořadí!) ,,S po R . 2
Příklady skládání relací.
* Je-li
 A = {a, b}, B = {1, 2}, C = {X},
 R = {(a, 1), (b, 1), (b, 2)}, S = {(1, X)},
pak složením vznikne relace
 S  R = {(a, X), (b, X)}. 2
* Složením funkcí h(x) = x2
a f(x) = x + 1 na  vznikne funkce
f  h (x) = f(h(x)) = x2
+ 1.2
* Složením těchže funkcí ,,naopak ale vznikne funkce hf (x) = h(f(x)) = (x+1)2
.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  R píše R  S nebo jen RS.
Petr Hliněný, FI MU Brno 6 FI: IB000: Skládání a Funkce
6.3 Skládání relací ,,v praxi6.3 Skládání relací ,,v praxi
Příklad 6.3. 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řazující studentům MU kódy jejich zapsaných
předmětů, druhou S přiřazující kódy předmětů 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 FI
IB000 FI
IA102 FI
M1050 PřF
M4135 PřF
2
Jak z těchto ,,tabulkových relací zjistíme, kteří studenti mají zapsané předměty
na kterých fakultách (třeba na FI)? 2
Jedná se jednoduše o složení relací S  R. V našem příkladě třeba:
S  R :
student (učo) fakulta MU
121334 FI
133935 FI
133935 PřF
155878 FI
155878 PřF 2
Petr Hliněný, FI MU Brno 7 FI: IB000: Skládání a Funkce
Zobecněné skládání relací
Fakt (skládání relací vyšší arity): Mějme relace T  K1 × K2 × . . . × Kk
a U  L1 × L2 × . . . × L, přičemž pro nějaké m < min(k, ) platí L1 =
Kk-m+1, L2 = Kk-m+2, . . . , Lm = Kk. 2Pak relaci T lze složit s relací U na
zvolených m složkách L1, . . . , Lm (,,překrytí ) s použitím Definice 6.2 takto:
* Položme A = K1×. . .×Kk-m, B = L1×. . .×Lm a C = Lm+1×. . .×L.
* Příslušné relace pak jsou
 R = {(a, b)  A × B | (a1, . . . ak-m, b1, . . . bm)  T} a
 S = {(b, c)  B × C | (b1, . . . bm, cm+1, . . . c)  U}. 2
* Nakonec přirozeně položme U m T  A  B, takže vyjde U m T =
(a, c) | ex. b  B, že (a1, . . . ak-m, b1, . . . bm)  T a (b1, . . . bm, cm+1, . . . c)  U .
Schematicky pro snažší orientaci:
T  K1 × . . . × Kk-m× Kk-m+1 × . . . × Kk
U  L1 × . . . × Lm ×Lm+1 × . . . × L
U m T  K1 × . . . × Kk-m
A
×
B
× Lm+1 × . . . × L
C
Petr Hliněný, FI MU Brno 8 FI: IB000: Skládání 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), 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
Petr 5.11. OK535
Pavel 6.11. OK535
Jan 5.11. AF2378
Josef 5.11. DL5457
Alena 6.11. AF2378
U :
datum let letadlo
5.11. OK535 ČSA
5.11. AF2378 ČSA
5.11. DL5457 ČSA
6.11. OK535 AirFrance
6.11. AF2378 AirFrance
2
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á zase složení relací U 2 T, jak je posáno
výše.
U 2 T :
pasažér letadlo
Petr ČSA
Josef ČSA
. . . . . .
2
Zkuste se zamyslet, lze tyto dvě relace skládat ještě jinak? Co by pak bylo
významem? 2
Petr Hliněný, FI MU Brno 9 FI: IB000: Skládání a Funkce
6.4 Skládání funkcí, permutace6.4 Skládání funkcí, permutace
Fakt: Mějme zobrazení (funkce) f : A  B a g : B  C. Pak jejich složením
coby relací v tomto pořadí vznikne zobrazení (g  f) : A  C definované
(g  f)(x) = g(f(x)) .2
* Jak například na běžné kalkulačce vypočteme hodnotu funkce sin2
x ? 2
Složíme (v tomto pořadí) ,,elementární funkce f(x) = sin x a g(x) = x2
. 2
* Jak bychom na ,,elementární funkce rozložili aritmetický výraz 2 log(x2
+ 1) ? 2
Ve správném pořadí složíme funkce f1(x) = x2
, f2(x) = x + 1, f3(x) = log x a
f4(x) = 2x. 2
* 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 g1(x) = sin x a
g2(x) = cos x, a pak je ,,složíme další funkcí h(x, y) = x + y. 2
Vidíme však, že takto pojaté ,,skládání už nezapadá hladce do našeho formalismu
skládání relací.
Petr Hliněný, FI MU Brno 10 FI: IB000: Skládání a Funkce
Skládání permutací
Definice: Nechť permutace  množiny [1, n] je určena seřazením jejích prvků
(p1, . . . , pn). Pak  je zároveň bijektivním zobrazením [1, n]  [1, n] definovaným
předpisem (i) = pi. 2
Tudíž lze permutace skládat jako relace podle Definice 6.2. 2
Poznámka: Všechny permutace množiny [1, 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ě. 2
Příkladem permutace vyskytujícím se v programátorské praxi je třeba zobrazení
i  (i+1) mod n ("inkrement"). 2Často se třeba lze setkat (aniž si to mnohdy
uvědomujeme) s permutacemi při indexaci prvků polí.
Petr Hliněný, FI MU Brno 11 FI: IB000: Skládání a Funkce
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ů.
s s
s
s s
ss
s
.
.
1 5
6
2 3
48
7
2
Definice: Nechť  je permutace na množině A. Cyklem v  rozumíme posloupnost
a1, a2, . . . , ak různých prvků A takovou, že (ai) = ai+1 pro
i = 1, 2, . . . , k - 1 a (ak) = a1. 2
Jak název napovídá, v zápise cyklu a1, a2, . . . , ak 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ý, FI MU Brno 12 FI: IB000: Skládání a Funkce
Věta 6.5. Každou permutaci  na konečné množině A lze zapsat jako složení
cyklů na disjunktních podmnožinách (rozkladu) A. 2
Důkaz: Vezmeme libovolný prvek a1  A a iterujeme zobrazení a2 = (a1),
a3 = (a2), atd., až se dostaneme ,,zpět k ak+1 = (ak) = a1. Proč tento
proces skončí? Protože A je konečná a tudíž ke zopakování některého prvku
ak+1 musí dojít. Nadto je  prostá, a proto nemůže nastat (ak) = aj pro
j > 1. Takto získáme první cyklus a1, . . . , ak . 2
Induktivně pokračujeme s hledáním dalších cyklů ve zbylé množině A \
{a1, . . . , ak}, dokud nezůstane prázdná. 2 2
Značení permutací cykly: Nechť se permutace  podle Věty 6.5 skládá z cyklů
a1, . . . , ak , b1, . . . , bl až třeba z1, . . . , zm . Pak zapíšeme
 = ( a1, . . . , ak b1, . . . , bl . . . z1, . . . , zm )2 .
Primitivní pseudonáhodné generátory v počítačích iterují z náhodného počátku permutaci
danou vztahem i  (i + p) mod q. Je pochopitelné, že tato permutace nesmí
obsahovat krátké cykly, lépe řečeno, měla by se skládat z jediného (dlouhého) cyklu.
Petr Hliněný, FI MU Brno 13 FI: IB000: Skládání a Funkce
Příklad 6.6. Ukázka skládání permutací daných svými cykly.
Vezměme 7-prvkovou permutaci (5, 3, 4, 2, 6, 1, 7). Ta se rozklá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á z jediného
cyklu 1, 3, 5, 7, 2, 4, 6 . 2
Nyní určíme složení těchto dvou permutací (zápisem cykly):
( 1, 5, 6 2, 3, 4 7 )  ( 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!) 2
Postup skládání jsme použili následovný:
* 1 se zobrazí v permutaci vpravo na 3 a pak vlevo na 4. 2
* Následně 4 se zobrazí na 6 a pak na 1. Tím ,,uzavřeme první cyklus 1, 4 .2
* Dále se 2 zobrazí na 4 a pak hned zpět na 2, tj. má samostatný cyklus. 2
* Zbylý cyklus 3, 6, 5, 7 určíme analogicky.
2
Petr Hliněný, FI MU Brno 14 FI: IB000: Skládání a Funkce
6.5 Induktivní definice množin a funkcí6.5 Induktivní definice množin a funkcí
Přímým zobecněním rekurentních definic je následující koncept.
Definice 6.7. 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ů a1, a2, . . . , ak  M. 2
* Je dán soubor induktivních pravidel typu
Jsou-li (libovolné prvky) x1, . . . , x  M, pak také y  M.
V tomto případě je y typicky funkcí y = fi(x1, . . . , x). 2
Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí)
množina vyhovující těmto pravidlům.
Vidíte podobnost této definice s uzávěrem relace? (Věta 5.7.) 2
Pro nejbližší příklad induktivní definice se obrátíme na množinu všech přirozených čísel.
­ 0  
­ Je-li i  , pak také i + 1  .
Petr Hliněný, FI MU Brno 15 FI: IB000: Skládání a Funkce
Pro každé y   můžeme definovat jinou množinu My   induktivně takto:
­ y  My.
­ Jestliže x  My a x + 1 je liché, pak x + 2  My.
Pak například M3 = {3}, nebo M4 = {4 + 2i | i  }. 2
Definice: Řekneme, že daná induktivní definice množiny M je jednoznačná,
právě když každý prvek M lze odvodit z bázových prvků pomocí induktivních
pravidel právě jedním způsobem. 2
Definujme množinu M   induktivně takto:
­ 2, 3  M.
­ Jestliže x, y  M a x  y, pak také x2 + y2 a x  y jsou prvky M.
Proč tato induktivní definice není jednoznačná? 2Například číslo 8  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?
Petr Hliněný, FI MU Brno 16 FI: IB000: Skládání a Funkce
Definice 6.8. Induktivní definice funkce z induktivní množiny.
Nechť množina M je dána jednoznačnou induktivní definicí. Pak říkáme, že
funkce F : M  X je definována induktivně (vzhledem k induktivní definici
M), pokud je řečeno:
* Pro každý z bázických prvků a1, a2, . . . , ak  M je určeno F(ai) = ci. 2
* Pro každé induktivní pravidlo typu
"Jsou-li (libovolné prvky) x1, . . . , x  M, pak také f(x1, . . . , x)  M"
je definováno
F( f(x1, . . . , x) ) na základě hodnot F(x1), . . . , F(x).2
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
EXPRESSION1 -a EXPRESSION2 both EXPRESSION1 and EXPRESSION2 are true
EXPRESSION1 -o EXPRESSION2 either EXPRESSION1 or EXPRESSION2 is true
[-n] STRING the length of STRING is nonzero
STRING1 = STRING2 the strings are equal
......
Petr Hliněný, FI MU Brno 17 FI: IB000: Skládání a Funkce
Induktivní definice se ,,strukturální indukcí
Příklad 6.9. Jednoduché aritmetické výrazy
Nechť (abeceda)  = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, , , (, )}. Definujme množinu
jednoduchých výrazů SExp   induktivně takto:
­ Dekadický zápis každého přirozeného čísla n je prvek SExp.
­ Jestliže x, y  SExp, pak také (x)  (y) a (x)  (y) jsou prvky SExp. 2
(Jak vidíme, díky ,,závorkování je tato induktivní definice jednoznačná.)
Pro ,,vyhodnocení výrazu pak definujme funkci Val : SExp   induktivně:
­ Bázické prvky: Val(n) = n, kde n je dekadický zápis přirozeného čísla n. 2
­ První induktivní pravidlo: Val((x)  (y)) = Val(x) + Val(y).
­ Druhé induktivní pravidlo: Val((x)  (y)) = Val(x)  Val(y). 2
(Tímto způsobem jsme našim výrazům vlastně přiřadili jejich ,,význam , sémantiku.)
2
Petr Hliněný, FI MU Brno 18 FI: IB000: Skládání a Funkce
Příklad 6.10. Důkaz správnosti přiřazeného ,,významu Val : SExp  .
Věta. Pro každý výraz s  SExp je hodnota Val(s) číselně rovna výsledku
vyhodnocení výrazu s podle běžných zvyklostí aritmetiky.2
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.2
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  SExp.
Takto aplikované matematické indukci se často říká strukturální indukce. 2
Důkaz: V bázi indukce ověříme vyhodnocení bázických prvků, což jsou zde
dekadizké zápisy přirozených čísel. Platí Val(n) = n, což skutečně odpovídá
zvyklostem aritmetiky. 2
V indukčním kroku se podíváme na vyhodnocení Val((x)  (y)) = Val(x) +
Val(y). Podle 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)  (y)) se dořeší analogicky. 2