4 Relace a funkce, Ekvivalence Nyní si podrobně rozebereme matematický aparát relací a funkcí, kterému se v jeho abstraktní podobě moc pozornosti ve středoškolské výuce nevěnuje - na rozdíl od naivního pohledu na množiny a na „funkce" ve významu analytických funkcí (jako x + 1 či sinx). Přitom na pojem relace velmi brzy narazí každý informatik už jen při studiu dat a databází a její abstraktní podobu bude potřebovat. Stručný přehled lekce * Co je relace a funkce. Reprezentace relací tabulkou a grafem. * Základní vlastnosti binárních relací. * Relace ekvivalence, jím odpovídající rozklady množin. Petr Hliněný, Fl MU Brno, 2012 1/33 Fl: IB000: Relace a funkce, Ekvivalence 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 mnohotvárnému použití v informatice věnujeme významnou pozornost v této i dvou příštích lekcích. Definice 4.1. Relace mezi množinami Ai,--- ,Ak, pro k g N, je libovolná podmnožina kartézského součinu R C A\ x • • • x Ak . Pokud A\ = • • • = Ak = A, hovoříme o k-ární relaci R na A. c Příklady relací. • {(1, a), (2, a), (2, b)} je relace mezi {1, 2, 3} a {a, b}. • {(i, 2 • i) | i g N} je binární relace na N.c • i + j) | í,j g N} je ternární relace na N. • {3 • i | i g N} je unární relace na N.c • Jaký význam vlastně mají unární a nulární relace na A? Petr Hliněný. Fl MU Brno. 2012 2/33 Fl: IB000: Relace a funkce. Ekvivalence Funkce mezi množinami Definice 4.2. (Totální) funkce z množiny A do množiny B je relace / mezi A a B taková, že pro každé x B říká, že / je funkce s def. oborem A a oborení hodnot B. Funkcím se také říká zobrazení. Príklady funkcí jsou třeba následující. • Definujeme funkci / : N —>■ N předpisem f (x) = x + 8. Pak / = {(x,x+ 8) | x G N}. • Definujeme funkci plus :NxN->N předpisem plus(i,j) = i + j. Pak plus = {(i, j, i + j) | i, J G N}. Petr Hliněný, Fl MU Brno, 2012 4/33 Fl: IB000: Relace a funkce. Ekvivalence Parciální funkce Definice: Pokud naši Definici 4.2 upravíme tak, že požadujeme pro každé x (z A nejvýše jedno y G B takové, že (x, y) G /, obdržíme definici parciální funkce z A do B.d V parciální funkci / nemusí být pro některé „vstupní" hodnoty x funkční hodnota definována (viz například f (2) v uvedeném obrázku). Pro nedefinovanou hodnotu používáme znak _L. Petr Hliněný, Fl MU Brno, 2012 5/33 Fl: IB000: Relace a funkce, Ekvivalence Nasleduje několik príkladu parciálních funkcí. Definujeme parciální funkci / : 7L —> N předpisem 3 + x jestliže x > 0. _L jinak. Tj. / = {(x,S + x) ieN}.c Také funkce / : R —> R daná běžným analytickým předpisem f(x) = \ogx je jen parciální - není definována pro x < Ox Co je relace, přiřazující lidem v ČR jejich (česká) rodná čísla? Petr Hliněný, Fl MU Brno, 2012 6/33 Fl: IB000: Relace a funkce, Ekvivalence 4.2 Reprezentace konečných relací Ukládání dat — především sleduje vztahy mezi objekty (stejně jako relace). ~> relační databáze jako obecná ukázka použití relace. Příklad 4.3. Tabulka relační databáze prezentuje obecnou relaci. Definujme následující množiny („elementární typy") • ZNAK — {a, ■ ■ ■ , z, A, ■ ■ ■ , Z, mezera}, • ČÍSLICE = {0,1, 2,3,4,5, 6,7, 8,9}.n Dále definujeme tyto množiny („odvozené typy") • JMÉNO = ZNAK15, PŘÍJMENÍ = ZNAK20, VEK = ČÍSLICE3, • ZAMESTNANEC „e" JMÉNO x PŘÍJMENÍ x VEK.□ Relaci „typu" ZAMESTNANEC pak lze reprezentovat tabulkou: JMÉNO PŘÍJMENÍ VEK Jan Novák 42 Petr Vichr 28 Pavel Zima 26 Stanislav Novotný 52 Z Petr Hliněný, Fl MU Brno, 2012 7/33 Fl: IB000: Relace a funkce, Ekvivalence 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 rovině. • Prvek (a, b) G 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, nejedná se o „grafy funkcí" známé z matematické analýzy, c Například mějme M — {a, b, c, d, e, /} a R — {(a, a), (a, b), (b, c), (b, d), (b, e), (b, /). {d, c), (e, c), (/, c), (e, ď), (e, /), (/, b)}, pak: c V případě, že M je nekonečná nebo „velká", může být reprezentace i? jejím grafem nepraktická (záleží také na míře „pravidelnosti" R). Petr Hliněný. Fl MU Brno. 2012 8/33 Fl: IB000: Relace a funkce. Ekvivalence Značení: Binární relaci i? C M x M lze jednoznačně zapsat také pomocí matice relace - matice A typu M x M s hodnotami z {0,1}. a •—1=- a A i 0 0 0 b 0 0 1 1 1 1 c 0 0 0 0 0 0 d 0 0 1 0 0 0 e 0 0 1 1 0 1 f 1 1 0 0 0/ = A Petr Hliněný, Fl MU Brno, 2012 9/33 Fl: IB000: Relace a funkce, Ekvivalence 4.3 Vlastnosti binárních relací Definice 4.4. Nechť R C M x M. Binární relace i? je • reflexivní, právě když pro každé a G M platí (a, a) G i?; • ireflexivní, právě když pro každé a G M platí (a, a) 0 R; • symetrická, právě když pro každé a, b G M platí, že jestliže (a, 6) G R, pak také (6, a) G i?; a • antisy■metrická, právě když pro každé a,b G M platí, že jestliže Petr Hliněný, Fl MU Brno, 2012 10/33 Fl: IB000: Relace a funkce, Ekvivalence • tranzitivní, právě když pro každé a, b, c G M platí, že jestliže (a, b), (6, c) G fí, pak také (a, c) G i?. a 6 c c Následují dva základní typy binárních relací; kde i? je • relace ekvivalence, právě když je R reflexivní, symetrická a tranzitivní;:: • částečné uspořádání, právě když je R reflexivní, antisymetrická a tranzitivní (často říkáme jen uspořádá ní).c Pozor, může být relace symetrická i antisymetrická zároveň? nAno! Petr Hliněný, Fl MU Brno, 2012 11/33 Fl: IB000: Relace a funkce, Ekvivalence Ukázkové binární relace Příklad 4.5. Několik příkladů relací definovaných v přirozeném jazyce. Nechť M je množina všech studentů 1. ročníku Fl. Uvažme postupně relace R C M x M definované takto • (x, y) G R právě když x a y mají stejné rodné číslo;c • (x,y) G R právě když x má stejnou výšku jako y (dejme t. na celé mm);c • (x, y) G R právě když výška x a y se neliší více jak o 2 mm;c • (x,y) G R právě když x má alespoň takovou výšku jako y;n • (x, y) G R právě když x má jinou výšku než y (dejme tomu na celé mm);c • (x, y) G R právě když x je zamilován(a) do y.c Které z nich tedy jsou ekvivalencí nebo uspořádáním? □ Petr Hliněný, Fl MU Brno, 2012 12/33 Fl: IB000: Relace a funkce, Ekvivalence Příklad 4.6. Jaké vlastnosti mají následující relace? • Buď ÍJCNxN definovaná takto (x,y) G R právě když x dělí y.c (Částečné uspořádání, ale ne každá dvě čísla jsou porovnatelná.) c • Bud' ÍJCNxN definovaná takto (x,y) G R právě když x a y mají stejný zbytek po dělení číslem 5. (Ekvivalence.) c • Nechť F = {/ | / : N —> N} je množina funkcí. Bud' R C FxF definovaná takto (f,g) G R právě když f(x) < g(x) pro všechna x. (Ireflexivní, antisymetrická a tranzitivní, ale ne reflexivní - není uspořádáním.) Petr Hliněný, Fl MU Brno, 2012 13/33 Fl: IB000: Relace a funkce, Ekvivalence 4.4 Relace ekvivalence • Podle Definice 4.4 je relace R C M x M ekvivalence právě když R je reflexivní, symetrická a tranzitivní. Tyto tři vlastnosti tedy musí být splněny a ověřeny k důkazu toho, že daná relace i? je ekvivalence.c • Jak vypadá graf relace ekvivalence?:: • Neformálně řečeno; ekvivalence je relace R C MxM, taková, že (x,y) 6 R právě když x a y jsou v nějakém smyslu „stejné". Značení. V případě relace ekvivalence se někdy lze setkat s pojmenováním jako ~ či místo R. Místo (x,y) £ i? se pak píše x y. Petr Hliněný, Fl MU Brno, 2012 14/33 Fl: IB000: Relace a funkce, Ekvivalence Další ukázkové binární relace Příklad 4.7. Nechť M je množina všech studentů 1. ročníku Fl. Uvažme postupně relace R C M x M a zkoumejme, zda se jedná o ekvivalence: • (x,y) 6 R právě když x má stejnou výšku jako y;n • (x,y) £ R právě když x má stejnou barvu vlasů jako y;c • (x,y) G i? právě když x,y mají stejnou výšku a stejnou barvu vlasů;c • (x,y) G i? právě když x,y mají stejnou výšku nebo stejnou barvu vlasů.c U kterého body se nejedná o relaci ekvivalence a proč? c Je to poslední případ, kdy není splněna tranzitivita! □ Tvrzení 4.8. Nechť R, S jsou dvě relace ekvivalence na stejné množině M. Pak jejich průnik R n S je opět relací ekvivalence. Petr Hliněný, Fl MU Brno, 2012 15/33 Fl: IB000: Relace a funkce, Ekvivalence Příklad 4.9. Necht C N x N je binární relace definovaná takto: (x, y) G fl právě když \x — y\ je dělitelné třemi. V jakém smyslu jsou zde x a y „stejné"? Dávají stejný zbytek po dělení třemi. □ Příklad 4.10. Bud R binární relace mezi všemi studenty na přednášce Fl: IB000 definovaná takto: (x, y) £ fl právě když x i y sedí v první lavici. Už na „první pohled" jde o relaci symetrickou a tranzitivní. Proč se v tomto případě nejedná o relaci ekvivalence? c Protože není reflexivní pro studenty sedící v dalších lavicích. (Takže si dávejte dobrý pozor na správné pochopení definic.) □ Petr Hliněný, Fl MU Brno, 2012 16/33 Fl: IB000: Relace a funkce, Ekvivalence 4.5 Rozklady a jejich vztah k ekvivalencím Definice 4.11. Rozklad množiny. Nechť M je množina. Rozklad (na) M je množina podmnožin M C 2M splňující násl. tři podmínky: • 0 0 M (tj. každý prvek M je neprázdná podmnožina M); • pokud A,B&J\Í, pak buď A = B nebo A n B = 0; Prvkům A/" se také říká třídy rozkladu. • Buď M = {a, b, c, d}. Pak N = {{a}, {b, c}, {d}} je rozklad na Mx • Nechť A0 = {k G N | k mod 3 = 0}, Ax = {k G N | mod 3 = 1}, A2 = {k G N j mod 3 = 2}. Pak A/" = {Ao,Ai,A2J je rozklad všech přirozených čísel N podle zbytkových tříd.c Každý rozklad M na M jednoznačně určuje jistou ekvivalenci Rj\f na M: Petr Hliněný, Fl MU Brno, 2012 17/33 Fl: IB000: Relace a funkce, Ekvivalence * Věta 4.12. Necht M je množina a M rozklad na M. Necht C M x M je relace na M definovaná takto (x, y) G Rj\f právě když existuje A G M taková, že x, y G A. Pak Rj\f je ekvivalence na M.c Důkaz: Dokážeme, že Rj\f je reflexivní, symetrická a tranzitivní (Def. 4.4).c • Reflexivita: Buď x G M libovolné. Jelikož M je rozklad na M, musí existovat A G M takové, že x G A (jinak spor se třetí podmínkou z Definice 4.11). Proto (x, x) G Rj\f, tedy Rj\f je reflexivníx • Symetrie: Nechť (x,y) G Rj\f. Podle definice Rj\f pak existuje A G M taková, že x,y G A. To ale znamená, že také (y,x) G Rj\f podle definice .R/V, tedy Rj\f je symetrická.c • Tranzitivita: Nechť (x, y), (y, z) G -R/v"- Podle definice Rj\f existují A, B G M takové, že x, y G A a y, z G B. Jelikož AnB ^ 0, podle druhé podmínky z Definice 4.11 platí A = B. Tedy x, z ) e R podle definice [x]. Dále (y, x) G i? (viz výše), tedy (y, v) e i? neboť R je tranzitivní. To podle definice [y] znamená, že f e [y].c * «[y] C [x]": Nechť v e [y]. Pak (y,f) G i? podle definice [y]. Dále (x,y) G i? (viz výše), tedy (x, v) G i? neboť R je tranzitivní. To podle definice [x] znamená, že f G [x].c • Platí U^Jgm/äN = M, neboť x g [x] pro každé x g M. □ Petr Hliněný, Fl MU Brno, 2012 20/33 Fl: IB000: Relace a funkce, Ekvivalence