4 Binární relace» Ekvivalence Na pojem relace velmi brzo narazí (snad) každý informatik při studiu relačních databází. Není to však jen tato oblast, ale i jiná místa informatiky, kde se relace skrývají či přímo explicitně objevují. Nejčastěji se takto setkáme s binárními relacemi, například vždy když rozdělujeme objekty podle „shodných" znaků (relace ekvivalence), nebo když objekty mezi sebou „srovnáváme" (relace uspořádání). Stručný přehled lekce * Reprezentace relací, tabulkou a grafem. * Základní vlastnosti binárních relací. * Relace ekvivalence, neboli rozklady množin. 3etr Hliněný, Fl MU Brno B000: Binární Relace Zopakování pojmu relace Definice 4.1. Relace mezi množinami A\, ■ ■ ■, A^, pro k € N, je libovolná podmnožina kartézského součinu R Q Ai x • • • x Ak .c Pokud Ai = • • • = Ak = A, hovoříme o k-ární relaci na A. c Takže binární relace R (pro k = 2) je RCAx A.c Příklady relací. • {(1, a), (2, a)} je relace mezi {1,2,3} a {a, b}. • {(í,2i) | í € N} je binární relace na N.d • {(hjji + j) \ h j G N} je ternární relace na N. • Relace „mít rychlejší počítač" je binární relací mezi studenty Fl. Petr Hliněný, Fl MU Brno 2 Fl: IB000: Binární 4.1 Reprezentace konečných relací Příklad 4.2. Tabulky relační databáze. 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}.d Dále definujeme tyto množiny („odvozené typy") • JMÉNO = ZNAK15, PŘÍJMENÍ = ZNAK20, • VEK = ČÍSLICE3, • ZAMESTNANEC ~ JMÉNO x PŘÍJMENÍ x VEK.c Relaci „typu" ZAMESTNANEC pak lze reprezentovat tabulkou: JMÉNO Jan Petr Pavel PŘÍJMENÍ Novák Vichr Zima VEK 42 28 26 D Definice: Relační databáze je konečná množina tabulek. Schéma databáze je (zjednodušeně řečeno) množina „typů" jednotlivých tabulek. Petr Hliněný, Fl MU Brno :IB000: Binární Relace 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) € 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 analýzy. Například mějme M = {a, b, c, d,e, /} a i? = {(a, 6), (6, c), (6, d), (6, e), (6, /), (d, c). (e, c), (/, c), (e, cř), (e, /), (/, 6)}, pak: V případě, že R je nekonečná nebo „velká", může být reprezentace R jejím grafem nepraktická (záleží pak na míře „pravidelnosti" R). Petr Hliněný, Fl MU Brno :IB000: Binární Relace 4.2 Vlastnosti binárních relací Definice 4.3. Nechť iž C M x M. Binární relace R je • reflexivní, právě když pro každé a € M platí (a, a) € ič; • ireflexivní, právě když pro každé a € M platí (a, a) ^ ič; ► symetrická, právě když pro každé a, b € M platí, že jestliže (a, 6) € ič, pak také (b,a) € ič; ► antisymetrická, právě když pro každé a,b € M platí, že jestliže (a, 6), (6, a) € ič, pak a = b; z 3etr Hliněný, Fl MU Brno_______________________________________IB000: Binární Relace ► tranzitivní, právě když pro každé a,b,c € M platí, že jestliže (a, b), (b, c) € R, pak také (a,c) € R. Následují dva základní typy binárních relací, R 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í). Poznámka: Pozor, může být relace symetrická i antisymetrická zároveň? aAno 3etr Hliněný, Fl MU Brno B000: Binární Relace Příklad 4.4. Několik příkladů relací definovaných v přirozeném jazyce. Buď M 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 tomu na celé mm); • (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;c • (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.n Příklad 4.5. Jaké vlastnosti mají následující relace? • Buď R C N x N definovaná takto (x, y) G R právě když x dělí y. ^(Částečné uspořádání, ale ne každá dvě čísla jsou porovnatelná.) • Buď ižCNxN definovaná takto (x, y) G R právě když x a y mají stejný zbytek po dělení číslem 5. ^(Ekvivalence.) Nechť F = {/ | / : N ^ N} je množina funkcí. Buď R C F x F definovaná takto (f, g) € R právě když f (x) < g{x) pro všechna x. (Antisymetrická a tranzitivní, ale ne reflexivní - není uspořádání.) a etr Hliněný, Fl MU Brno_______________________________________IBOOO: Binární Relace • 4.3 Relace ekvivalence • Relace fiCMxMje ekvivalence právě když R je reflexivní, symetrická a tranzitivní. Tyto tři vlastnosti je tedy třeba ověřit k důkazu toho, že daná relace i? je ekvivalence. • Jak vypadá graf ekvivalenceln • Neformálně řečeno: ekvivalence je relace R C MxM, taková, že (x, y) £ R právě když x a y jsou v nějakém smyslu „stejné". Petr Hliněný, Fl MU Brno 8 FHB000: Binární Relace Bud M množina všech studentů 1. ročníku Fl. Uvažme postupně relace R C M x M definované takto • (x, y) € R právě když x má stejnou výšku jako y;c • (x, y) € -R právě když x má stejnou barvu vlasů jako y;a • {x, y) € R právě když a;, y mají stejnou výšku a stejnou barvu vlasů;n • (x,y) € R právě když a;, y mají buď stejnou výšku nebo stejnou barvu vlasů. (Tato relace obecně není ekvivalence ! Proč?) Příklad 4.6. Buď R C N x N binární relace definovaná takto: (x, y) € R 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. D Příklad 4.7. Buď R binární relace mezi všemi studenty na přednášce Fl: IBOOO definovaná takto: (x, y) € R právě když x i y sedí v první lavici, a Proč se v tomto případě nejedná o relaci ekvivalence? □ 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.) □ 3etr Hliněný, Fl MU Brno_______________________________________IBOOO: Binární Relace 4.4 Rozklady a jejich vztah k ekvivalencím Definice 4.8. Rozklad. Buď M množina. Rozklad (na) M je množina podmnožin TV C 2M splňující násl. tři podmínky: • 0 ^TV (tj. každý prvek TV je neprázdná podmnožina M); • pokud A, B e TV, pak buď A = B nebo A n B = 0; Prvkům TV se také říká třídy rozkladu. • Buď M = {a, b, c, d}. Pak M = {{a}, {b, c}, {d}} je rozklad na M.c • Nechť A0 = {k € N | k mod 3 = 0}, Aľ = {k € N | k mod 3 = 1}, A2 = {k € N | A; mod 3 = 2}. Pak TV = {Aq, Ai,A2} je rozklad všech přirozených čísel N podle zbytkových tříd. • Každý rozklad TV na M jednoznačně určuje jistou ekvivalenci Rj^ na M. 3etr Hliněný, Fl MU Brno_________________________________________3000: Binární Relace Věta 4.9. Buď M množina a TV rozklad na M. Nechť R^ C M x M je relace na M definovaná takto (x, y) € Rßj- právě když existuje A e TV taková, že x,y G A. Pak Rßj- je ekvivalence na M. Důkaz: Dokážeme, že ič/v je reflexivní, symetrická a tranzitivní (Def. 4.3).c • Reflexivita: Buďa; € M libovolné. Jelikož TV je rozklad na M, musí existovat A e TV takové, že x € A (jinak spor se třetí podmínkou z Definice 4.8). Proto (x,x) € Rjif, tedy R^f je reflexivní.c • Symetrie: Nechť (x,y) € R^f. Podle definice iž/v" pak existuje A e TV taková, že x,y € A. To ale znamená, že také (y,x) € R^f podle definice Rjsí, tedy R^f je symetrická.u • Tranzitivita: Nechť (x,y),(y,z) € R^f. Podle definice R^f existují A,B£ TV takové, žex,y € A a y,z € B. Jelikož AnB ^ 0, podle druhé podmínky z Definice 4.8 platí A = B. Tedy x,z G A = B, proto (a;,2) € iž/v" podle definice R^f. D 3etr Hliněný, Fl MU Brno_________________________________________3000: Binární Relace Každá ekvivalence R na M jednoznačně určuje jistý rozklad M/R na M. Věta 4.10. Buď M množina a R ekvivalence na M. Pro každé x € M definujeme množinu [x]={yeM\ (x,y)eR}. Pak {[x] \ x £ M} je rozklad na M, který značíme M/R.c M Důkaz: Dokážeme, že M/R splňuje podmínky Definice 4.8 3etr Hliněný, Fl MU Brno 3000: Binární Relace • Pro každé [x] G M jR platí [x] ^ 0, neboť x G [a;], c • Necht [x], [y] G M/R. Ukážeme, že pokud [x] n [y] ^ 0, pak [x] = [y], c Jestliže [x] n [y] 7^ 0, existuje z G M takové, že z € [a;] a z G [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G R. Jelikož í? je symetrická a (y, z) G R, platí (z, y) G -R. Jelikož (a;, z), (z, y) G -R a R je tranzitivní, platí (a;, y) € -R. Proto také (y, a?) G -R (opět ze symetrie R). Nyní dokážeme, že [y] = [a;]: * ••[x] C [y]:" Nechť -y G [x]. Pak (x, v) G R podle definice [x]. Dále (y, x) G R (viz výše), tedy (y, v) G R neboť R je tranzitivní. To podle definice [y] znamená, že«€ [y].u * ••[y] C [x]:" Nechť v G [y]. Pak (y, v) G R podle definice [y]. Dále (x, y) G R (viz výše), tedy (x, v) G R neboť R je tranzitivní. To podle definice [x] znamená, že«€ [x].u • Platí U[íe]€M/äM = M, neboť x G [x] pro každé x G M. □ Petr Hliněný, Fl MU Brno 13 Fl: IBOOO: Binární Relace