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.
Petr Hliněný,   Fl MU Brno                                  1
Fl: IB000: Binární 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, 6}.
•   {(í,2i) | i € N} je binární relace na N.d
•   {(hjji + j) \ hj 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í Relace
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
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.
________tr Hliněný.   Fl MU Brno ____________________________________I: 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   ____________________________________I: 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 G M platí (a, a) ^ ič;
► symetrická, právě když pro každé a, 6 € M platí, že jestliže (a, b) € ič, pak také (6, a) € ič;
• antisymetrická,   právě   když   pro   každé   a,b   G    M   platí,   že jestliže
(a, 6), (6, a) € ič, pak a = b;
3etr Hliněný,   Fl MU Brno
Fl: 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
Fl: IB000: Binární Relace
r
Příklad 4.4. Několik příkladů relaci 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
Petr Hliněný.   Fl MU Brn<____________________________________  Fl: 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 Brn(
rl: IB000: Binární Relace
r.
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ž x, y mají stejnou výšku a stejnou barvu vlasů;c
•   (x,y) € iž právě když x,y mají stejnou výšku nebo stejnou barvu vlasů.n (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 Brn____________________________________   Fl: IBOOO: Binární Relaci
r
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í nasi, 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 5 = 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 | A; 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 Hlinený,   Fl MU Brno                                 10                                     Fl: IB000: 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 Petr Hliněný,   Fl MU Brno                                 11                                     Fl: IB000: 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
Fl: IBOOO: 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 Hlinený,   Fl MU Brno                                 13                                     Fl: IB000: Binární Relace