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.0.  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 A\ = ■ ■ ■ = Ak = A, hovoříme o k-ární relaci na A. c Takže binární relace R (pro k = 2) je
fícAx A.c
Příklady relací.
•   {(1, a), (2, a)} je relace mezi {1,2,3} a {a, 6}.
•   {{i, 2.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.1. 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.2.    Nechť iž C M x M. Binární relace iž 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,b G M platí, že jestliže (a,6) € ič, pak také (6, a) € ič;
• antisymetrická,   právě   když   pro   každé   a, b   €    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ň? _Ano
3etr Hliněný,   Fl MU Brno
Fl: IB000: Binární Relace
r
Příklad 4.3. 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.4. 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ď ECNxN 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. a(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.5. 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.6. 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. □
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.7.  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 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 Hlinený,   Fl MU Brno                                 10                                     Fl: IB000: Binární Relace
Věta 4.8. 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 € TV taková, že x, y € A.
Pak Rßj- je ekvivalence na M.
Důkaz: Dokážeme, že ič/v je reflexivní, symetrická a tranzitivní (Def. 4.2).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.7). Proto (x,x) € Rjif, tedy R^f je reflexivní.c
•  Symetrie: Nechť (x,y) € R^f. Podle definice R^f pak existuje A e TV taková, že x,y € A. To ale znamená, že také (y,x) € iž/v" podle definice fíjv". tedy A/v" je symetrická.u
•  Tranzitivita: Nechť (x,y),(y,z) € iž/v"- Podle definice iž/v" existují A,B£ TV takové, žex,y G Aay,z G B. Jelikož AnB ^ 0, podle druhé podmínky z Definice 4.7 platí A = B. Tedy a;, 2 € A = £>, proto (x,z) € 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.9. 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.7.
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 j 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ž E je symetrická a (y, z) € R, platí (z, y) € -R. Jelikož (x, z), (z, y) € -R a E je tranzitivní, platí {x, y) G E. Proto také (y, a;) € E (opět ze symetrie E). 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 v G [y].c
*   ••[y] C [x]": Nechť -y G [y]. Pak (y, -y) G R podle definice [y]. Dále (x, y) (E í! (viz výše), tedy (x, v) G R neboť R je tranzitivní. To podle definice [x] znamená, že v G [x].u
M, neboť x G [x] pro každé x G M.                             □
P|atí U^eM/ßW
Petr Hliněný,   Fl MU Brno
Fl: IB000: Binární Relace