4   Relace a funkce, Ekvivalence
Nyní si podrobně rozebereme matematický aparát relací a funkcí, kterým se v jejich abstraktní podobe moc pozornosti v drívejSí výuce nevenuje (na rozdíl od velmi naivního pohledu na mnoZiny a na „funkce" jako x + 1 ci sinx).
*>mt
^^^^ □
Přitom na pojem relace velmi brzo narazí kaZdý informatik při studiu dat a databází. Mimo to se nejcasteji setkate s binarními relacemi; například vzdy, kdyz rozdelujete objekty podle „shodnych" znaku (relace ekvivalence), nebo kdyz objekty mezi sebou „srovnívíte" (relace uspořádáni).
StruCný přehled lekce
* Co je relace a funkce. Reprezentace relací tabulkou a grafem.
* Zakladn í vlastnosti binarn ích relac í.
* Relace ekvivalence, j ím odpov ídaj íc í rozklady mnoZin.
Petr Hliněný,  FI MU Brno_1_FI: IB000: Binární Relace
4.1   Relace a funkce nad množinami
Vedle množin dalším důležitým základním „datovým typem" matematiky jsou relace, kterým vzhledem k jejich rozsahlemu použití v informatice venujeme významnou pozornost v teto i dvou příštích lekcích.
Definice 4.1. Relace mezi mnozinami Ai, • • • ,    , pro k € N, je libovolna podmnozina kartezskeho souánu
R C Ai x • • • x Ak .c
Pokud A1 = • • • = Afc = A, hovoříme o k-ární relaci R na A. c
Příklady relací.
• {(1, a), (2, a)} je relace mezi {1,2,3} a (a, b}.
• {(i, 2 • i) | i € N} je binarní relace na N.c
• + j) | i, j € N} je ternarní relace na N.
• {3 • i | i € N} je unarní relace na N.c
• Jaký význam vlastne maj í unarn í a nularn í relace na A?
Petr Hliněný,  FI MU Brno__: IB000: Binární Relace
r.
Funkce mezi množinami
Definice 4.2. (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ávě jedno y € B
takové, že (x, y) € f .c
Množina A se nažyva definiční obor a množina B obor hodnot funkce f.
Neformalne reCeno, ve funkci f je každe „vstupní" hodnote x přiražena jednožnaCne „výstupní" hodnota y. (V obecne relaci poCty „přiražených" dvojic neomežujeme.. .)
Petr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
Značení: Místo (x, y) € / píšeme obvykle /(x) = y.
Zápis / : A — B říká, že / je funkce s def. oborem A a oborem hodnot B.c Funkcím se take říká zobrazen í.
Příklady funkcí.
• Definujeme funkci / : N — N předpisem /(x) = x + 8.
Pak / = {(x, x + 8) | x € N}.n
• Definujeme funkci plus : N x N — N předpisem plus (i, j) = i + j. Pak plus = {(i, j, i + j) | i, j € N}.
Petr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
r.
Definice: Pokud naší definici funkce upravíme tak, že požadujeme pro každé x € A nejvýše jedno y € B takove, že (x,y) € f, obdržíme definici parciální funkce ž A do B .c
V parciainí funkci p nemuší být pro nektere „vstupní" hodnoty x funkční hodnota defi novana.
Pro nedefinovanou hodnotu používame žnak _L. c
Další příklady parciainích funkcí. • Definujeme parciainí funkci f \7l —> N předpisem
Tj. f = {(x, 3 + x) | x € N}. c
• Take funkce f : R — R dana bežným analytickým předpisem
/(V) = Vx
je jen parciain í - nen í defi novana pro x < 0.c
• Co je relace, přiražuj ící lidem v ČR jejich rodna d'šla?
'etr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
4.2   Reprezentace konečných relací
Příklad 4.3. Tabulky relační databáze.
Definujme následující množiny („elementární typy")
• ZNAK = {a, • • • , z, A, • • • , Z, mezera},
• CISLICE = {0,1, 2, 3, 4, 5, 6, 7, 8, 9}.n
Dále definujeme tyto množiny („odvožene typy")
• JMENO = ZNAK15,     PRIJMENI = ZNAK20,
• VEK = CISLICE3,
• ZAMESTNANEC - JMENO x PRIJMENI x VEK.c Relaci „typu" ZAMESTNANEC pak lže reprezentovat tabulkou:
JMENO	PRIJMENI	VEK
Jan	Novák	42
Petr	Vichr	28
Pavel	Zima	26
Stanislav	Novotný	52
□
Poznámka: Relační databáze je konečná množina tabulek. Sčhema databaze je (žjednoduSene řečeno) množina „typu" jednotlivých tabulek.
ětr Hliněný.  FI MU Brno
FI: IB000: Binární Relace
r.
Reprezentace binárních relací na množině
Značení: Binární relaci R C M x M lze jednoznačně znázornit jejím grafem:
• Prvky M znázorníme jako body v rovine.
• Prvek (a, b) € R znázorníme jako orientovanou hranu („šipku") z a do b. Je-li a = b, pak je touto hranou „smyčka" na a.c
Pozor, nejedna se o „grafy funkcí" zname z matematické analýzy.
Například mejme M = {a, b, c, d, e, f} a R = {(a, b), (b, c), (b, d), (b, e), (b, f), (d, c), (e, c), (f, c), (e, d), (e, f), (f, b)}, pak:
c
V případe, ze R je nekoneční nebo „velkí", muze být reprezentace R jejím grafem nepraktickí (zílezí pak na míře „pravidelnosti" R).
a
d
'etr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
Značení: Binírní relaci R C M x M lže jednožnacne žapsat take pomoci tabulky relace - matice typu M x M s hodnotami ž {0,1}.
í°	1	0	0	0	0
0	0	1	1	1	1
0	0	0	0	0	0
0	0	1	0	0	0
0	0	1	1	0	1
0	1	1	0	0	0
/
a
d
c
Petr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
4.3   Vlastnosti binárních relací Definice 4.4.   Necht R C M x M. Binární relace R je • reflexivní, práve když pro kazde a € M platí (a, a) € R;
• ireflexivní, právě když pro každé a € M platí (a, a) ^ ič;
« X . X □
• symetrická, právě když pro každé a, b € M platí, žě jěstližě (a,b) € i, pak také (b, a) € i;
• antisymetrická, právě když pro každé a, b  €  M platí, žě jěstližě
(a, b), (b, a) € i, pak a = b;
X
Petr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
•
□
• tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a, 6), (b, c) G R, pak také (a, c) G R.
Následují dva základní typy binárních relací; kde R je
• relace ekvivalence, prave kdyZ je R reflexivní, symetrická a tranzitivní;^
• částečné uspořádání, prave kdyZ je R reflexivní, antisymetricka a tranzitivní (Často říkame jen uspořádáníj.c
Poznámka: Pozor, mUZe byt relace symetricka i antisymetricka zaroven? Ano!
a
b
c
c
Petr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
-N
Příklad 4.5. Několik příkladů relací definovaných v přirozeném jazyce.
Bud' M množina vSěch studěntu 1. ročníku FI. Uvažmě postupně rělacě R C M x M děfinovaně takto
• (x, y) € R pravě když x a y majístějně rodně číslo;□
• (x,y) € R pravě když x ma stějnou výsku jako y (dějmě tomu na cělě mm)x
• (x, y) € R pravě když vyska x a y sě nělisí vícě jak o 2 mmx
• (x,y) € R pravě když x ma alěspoň takovou vysku jako yx
• (x,y) € R pravě když x ma jinou vysku něž y (dějmě tomu na cělě mm)x
• (x, y) € R pravě když x jě žamilovan(a) do yx
Príklad 4.6. Jake vlastnosti mají následující relace?
• Bud' R C N x N děfinovaní takto (x, y) € R prívě když x dělí yx (Cístěcně uspořádání, alě ně každí dvě císla jsou porovnatělní.)
• Bud' R C N x N děfinovaní takto (x, y) € R prívě když x a y mají stějní žbytěk po dělění císlěm 5. □(Ekvivalěncě.)
• Něcht F = {/ | f -N — N} jě množina funkcí. Bud' R C F xF děfinovaní takto (f,g) € R prívě když f (x) < g(x) pro vsěchna x. □(Antisymětrickí a tranžitivní, alě ně rěflěxivní- nění uspořídíní.) a
Petr Hliněný,  FI MU Brno__:I: IB000: Binární Relace „/
r
4.4   Relače ekvivalence
• Relace R C M x M je ekvivalence príve když R je reflexivní, symetrickí a tranžitivní. Tyto tri vlastnosti je tedy treba overit k dukažu toho, že daní relace R je ekvivalence.□
• Jak vypadí graf relace ekvivalence?^
• Neformílne receno: ekvivalence je relace R C M x M, takoví, že (x, y) G R príve když x a y jsou v nejakem smyslu „stejne".
8
Petr Hlinený,  FI MU Brn
FI: IB000: Binární Relace
Bud' M množina vsech studentu 1. ročníku FI. Uvažme postupne relace R C M x M definovane takto
• (x, y) € R prave když x ma stejnou vyčku jako y;c
• (x, y) € R prave když x ma stejnou barvu vlasu jako y;c
• (x, y) € R prave když x, y mají stejnou vysku a stejnou barvu vlasec
• (x, y) € R prave když x, y mají stejnou vysku nebo stejnou barvu vlasu.c (Tato relace obecne není ekvivalence ! Proč?)
Príklad 4.7. Buď R C N x N binarní relace definovana takto: (x, y) € R pra've kdyz |x — y| je dělitelné tremi.
V jakem smyslu jsou žde x a y „stejne"?   Davají stejny žbytek po delení tčemi.
□
Príklad 4.8. Buď R binarní relace mezi všemi studenty na přednašce FI: IB000 definovana takto: (x,y) € R prave když x i y sedí v první lavici. c
Proc se v tomto prípade nejedna o relaci ekvivalence? c
Protože není reflexivní pro studenty sedící v dalsích lavicích. (Takže si davejte
dobry požor na spravne pochopení definic.) □
Petr Hlinený,  FI MU Brnc_13___FI: IB000: Binární Relace
-N
4.5   Rozklady a jejich vztah k ekvivalencím
Definice 4.9. Rozklad mnoZiny. Necht: M je množina.
Rozklad (na) M je množina podmnožin N C 2M šplřující našl. tři podmínký:
• 0 €N (tj. každý prvek N je nepraždna podmnožina M);
• pokud A, B € N, pak bud' A = B nebo A n B = 0;
^ UasN A = M. Prvkum N še take díka trídy rozkladu.
• Bud' M = {a, b, c, d}. Pak N = {{a}, {b, c}, {d}} je rožklad na M .c
• Necht! Ao = {k € N | k mod 3 = 0}, Ai = {k € N | k mod 3 = 1},
A2 = {k € N | k mod 3 = 2}.
Pak N = {A0,A1,A2} je rožklad všech přirožených cíšel N podle žbýtkových tríd.c
• Každý rožklad N na M jednožnacne urcuje jištou ekvivalenci Rn na M.
3etr Hliněný,  FI MU Brno_FI: IB000: Binární Relace
Veta 4.10. Bud M množina a N rozklad na M. Necht RN C M x M je relace na M definovaná takto
(x, y) € Rn pra'vZ kdyZ existuje A € N taková, Ze x, y € A.
Pak Rn je ekvivalence na M .c
DUkaž: Dokazeme, ze Rn je reflexivn í, sýmetricka a tranzitivn i (Def. 4.4).c
• Reflexivita: Bud' x € M libovolne. Jelikoz N je rozklad na M, musí existovat A € N takove, ze x € A (jinak spor se tret í podm ínkou z Definice 4.9). Proto (x, x) € Rn, tedý Rn je reflexivn í.c
• Sýmetrie: Necht (x, y) € Rn. Podle definice Rn pak existuje A € N takova, ze x, y € A. To ale znamena, ze take (y, x) € Rn podle definice Rn , tedý Rn je sýmetricka.c
• Tranzitivita: Necht! (x, y), (y, z) € Rn. Podle definice Rn existuj í A, B € N takove, ze x, y € A a y, z € B. Jelikoz AnB = 0, podle druhe podm ínký z Definice 4.9 plat í A = B. Tedý x, z € A = B, proto (x, z) € Rn podle definice Rn .
□
Petr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
r.
Kazdí ekvivalence R na M jednoznacne urcuje jisty rozklad M/R na M.
Veta 4.11. Bud M množina a R ekvivalence na M. Pro každé x € M definujeme množinu
[x] = {y € M | (x, y) € R} . Pak {[x] | x € M} je rozklad na M, který žnačíme M/R.c
M
Důkaz: Dokízeme, ze M/R splňuje podmínky Definice 4.9.
Petr Hliněný,  FI MU Brno
FI: IB000: Binární Relace
M
Pro kazde [x] € M/R platí [x] = 0, nebol! x € [x].c
Necht [x], [y] € M/R. UkýZeme, ze pokud [x] n [y] = 0, pak [x] = [y]. c Jestlize [x] n [y] = 0, existuje z € M takove, ze z € [x] a z € [y]. Podle definice [x] a [y] to znamení, ze (x, z), (y, z) € R. Jelikoz R je symetrickí a (y, z) € R, platí (z, y) € R. Jelikoz (x, z), (z, y) € R a R je tranzitivní, platí (x, y) € R. Proto take (y, x) € R (opet ze symetrie R). Nyní dokízeme, ze [y] = [x]:
* m [x] C [y]": Nechť v € [x]. Pak (x, v) € R podle definice [x]. Dale (y, x) € R (viz vyse), tedy (y, v) € R nebot R je tranzitivní. To podle definice [y] znamení, ze v € [y].c
* m [y] C [x]": Necht v € [y]. Pak (y,v) € R podle definice [y]. Dale (x,y) € R (viz vyse), tedy (x, v) € R nebot R je tranzitivní. To podle definice [x] znamena, ze v € [x].c
Platí U[x]€m/R[x] = M, nebot! x € [x] pro kazde x € M. □
Petr Hlinený,  FI MU Brno__: IB000: Binární Relace