4 Binárni 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í). 'etr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace 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 IB000 "Úv. Inf.": Binární Relace Zopakování pojmu relace ^ Definice 4.1. Relace mezi množinami A\,- ■ ■, Ak, pro k G N, je libovolná podmnožina kartézského součinu R C Ai x • • • x Ak . Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Zopakování pojmu relace Definice 4.1. Relace mezi množinami A\> • ■ •, Ak, pro k G N, je libovolná podmnožina kartézského součinu RC Ai x ■■■ x Ak. Pokud A\ = • • • = Ak = A, hovoříme o k-ární relaci na A. Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Zopakování pojmu relace Definice 4.1. Relace mezi množinami A\> • ■ •, Ak, pro k G N, je libovolná podmnožina kartézského součinu RC Ai x ■■■ x Ak. Pokud A\ = • • • = Ak = A, hovoříme o k-ární relaci na A. Takže binární relace R (pro k = 2) je RCAxA. Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Zopakování pojmu relace Definice 4.1. Relace mezi množinami A\,- ■ ■, Ak, pro k G N, je libovolná podmnožina kartézského součinu R C Ai x • • • x Ak . Pokud A\ = ■ ■ ■ = Ak = A, hovoříme o k-ární relaci na A. Takže binární relace R (pro Ar = 2) je RCAxA. Příklady relací. • {(1, a), (2, a)} je relace mezi {1, 2,3} a {a, 6}. • {(i, 2.i) | i G N} je binární relace na N. Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Zopakování pojmu relace Definice 4.1. Relace mezi množinami A\,- ■ ■, Ak, pro k G N, je libovolná podmnožina kartézského součinu R C Ai x • • • x Ak . Pokud A\ = ■ ■ ■ = Ak = A, hovoříme o k-ární relaci na A. Takže binární relace R (pro Ar = 2) je RCAxA. Příklady relací. • {(1, a), (2, a)} je relace mezi {1, 2,3} a {a, 6}. • {(i, 2.i) | i G N} je binární relace na N. • {(hj,i + j) \hj€ IN} 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 "Úv. Inf.": 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}. Petr Hliněný, Fl MU Brno "Úv. Inf.": 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ále definujeme tyto množiny („odvozené typy") • JMÉNO = ZNAK15, PŘÍJMENÍ = ZNAK20, • VEK = ČÍSLICE3, • ZAMESTNANEC = JMÉNO x PŘÍJMENÍ x VEK. Petr Hliněný, Fl MU Brno 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ále definujeme tyto množiny („odvozené typy") • JMÉNO = ZNAK15, PŘÍJMENÍ = ZNAK20, • VEK = ČÍSLICE3, • ZAMESTNANEC = 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 Petr Hliněný, Fl MU Brno "Úv 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ále definujeme tyto množiny („odvozené typy") • JMÉNO = ZNAK15, PŘÍJMENÍ = ZNAK20, • VEK = ČÍSLICE3, • ZAMESTNANEC = 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 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ěnv. Fl MU Brno IB000 "Uv. Inf.": 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) 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. Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Reprezentace binárních relaci na množme 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. Pozor, nejedná se o „grafy funkcí" známé z analýzy. Například mějme M = {a, b, c, d,e,f} a R = {(a, 6), (6, c), (6, d), (6, e), (6, /), (d, c), (e, c), (/, c), (e, d), (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ěnv. Fl MU Brno IB000 "Úv. Inf.": Binární Relace 4.2 Vlastnosti binárních relací Definice 4.3. Nechť Ä C M x M. Binární relace R je • reflexivní, právě když pro každé a G M platí (a, a) G -R; Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace 4.2 Vlastnosti binárních relací Definice 4.3. Nechť Ä C M x M. Binární relace R je • reflexivní, právě když pro každé a G M platí (a, a) G -R; ireflexivní, právě když pro každé a e M platí (a, a) ^ ič; Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace 4.2 Vlastnosti binárních relací Definice 4.3. Nechť Ä C M x M. Binární relace R je • reflexivní, právě když pro každé a G M platí (a, a) G -R; 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) G R, pak také (6, a) G R; Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace 4.2 Vlastnosti binárních relací Definice 4.3. Nechť Ä C M x M. Binární relace R je • reflexivní, právě když pro každé a G M platí (a, a) G -R; • ireflexivní, právě když pro každé a G M platí (a, a) ^ ič; <^ <& • symetrická, právě když pro každé a, 6 G M platí, že jestliže (a, 6) G -R, pak také (6, a) G -R; • antisymetrická, právě když pro každé a, 6 G M platí, že jestliže (a, 6), (6, a) G R, pak a = b; <áfe> Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace 4.2 Vlastnosti binárních relací Definice 4.3. Nechť Ä C M x M. Binární relace R je • reflexivní, právě když pro každé a G M platí (a, a) G -R; • ireflexivní, právě když pro každé a G M platí (a, a) ^ ič; <^ <& • symetrická, právě když pro každé a, 6 G M platí, že jestliže (a, 6) G -R, pak také (6, a) G -R; • antisymetrická, právě když pro každé a, 6 G M platí, že jestliže (a, 6), (6, a) G R, pak a = b; <áfe> Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace ► tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a, b), (b, c) G R, pak také (a,c) G R. Petr Hliněný, Fl IB000 "Uv. Inf.": Binární Relace ► tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a, b), (b, c) G R, pak také (a,c) G R. Následují dva základní typy binárních relací, R je • relace ekvivalence, právě když je R reflexivní, symetrická a tranzitivní; Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace • tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a, b), (b, c) G R, pak také (a,c) G -R. a 6 c 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í). Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace • tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a, b), (b, c) G R, pak také (a,c) G -R. a 6 c 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ň? Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace ► tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a, b), (b, c) G R, pak také (a,c) G 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! Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace ► tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a, b), (b, c) G R, pak také (a,c) G 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! Petr Hliněný, Fl MU Brno "Úv. Inf.": 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; Petr Hliněný, Fl MU Brno IBOOO "Úv. Inf.": 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; • (x, y) G R právě když x má stejnou výšku jako y (dejme tomu na celé mm); Petr Hliněný, Fl MU Brno IBOOO "Úv. Inf.": Binární Relace Přiklad 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; • (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; Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Přiklad 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; • (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; • (x, y) G R právě když x má alespoň takovou výšku jako y; Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Přiklad 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; • (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; • (x, y) G R právě když x má alespoň takovou výšku jako y; • (x, y) G R právě když x má jinou výšku než y (dejme tomu na celé mm); Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Přiklad 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; • (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; • (x, y) G R právě když x má alespoň takovou výšku jako y; • (x, y) G R právě když x má jinou výšku než y (dejme tomu na celé mm); • (x, y) G R právě když x je zamilován(a) do y. Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Přiklad 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; • (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; • (x, y) G R právě když x má alespoň takovou výšku jako y; • (x, y) G R právě když x má jinou výšku než y (dejme tomu na celé mm); • (x, y) G R právě když x je zamilován(a) do y. Příklad 4.5. Jaké vlastnosti mají následující relace? • Buď ižCNxN definovaná takto (x, y) e R právě když x dělí y. Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Přiklad 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; • (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; • (x, y) G R právě když x má alespoň takovou výšku jako y; • (x, y) G R právě když x má jinou výšku než y (dejme tomu na celé mm); • (x, y) G R právě když x je zamilován(a) do y. Příklad 4.5. Jaké vlastnosti mají následující relace? • Buď ižCNxN 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. Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace Přiklad 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; • (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; • (x, y) G R právě když x má alespoň takovou výšku jako y; • (x, y) G R právě když x má jinou výšku než y (dejme tomu na celé mm); • (x, y) G R právě když x je zamilován(a) do y. Příklad 4.5. Jaké vlastnosti mají následující relace? • Buď ižCNxN 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 (/,#) G -R právě když /(#) < g(a;) pro všechna x. Petr Hliněný, Fl MU Brno IBOOO "Úv. Inf.": 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; • (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; • (x, y) G R právě když x má alespoň takovou výšku jako y; • (x, y) G R právě když x má jinou výšku než y (dejme tomu na celé mm); • (x, y) G R právě když x je zamilován(a) do y. Příklad 4.5. Jaké vlastnosti mají následující relace? • Buď ižCNxN 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 (/,#) G -R právě když /(#) < g(a;) pro všechna sc. (Antisymetrická a tranzitivní, ale ne reflexivní - není uspořádání.) D Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": 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 R je ekvivalence. Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": 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 R je ekvivalence. • Jak vypadá graf ekvivalence? Petr Hliněný, Fl MU Brno "Úv. Inf.": 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 R je ekvivalence. • Jak vypadá graf ekvivalence? # • Neformálně řečeno: ekvivalence je relace R C MxM, taková, že (x,y) G R právě když x a y jsou v nějakém smyslu „stejné". Petr Hliněný, Fl MU Brno "Úv. Inf.": Binární Relace 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 má stejnou výšku jako y; Petr Hliněný, Fl MU Brno 9 IBOOO "Uv. Inf.": Binární Relace 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 má stejnou výšku jako y; • (x, y) G R právě když x má stejnou barvu vlasů jako y; Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace 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 má stejnou výšku jako y; • (x, y) G R právě když x má stejnou barvu vlasů jako y; • (x, y) G R právě když x, j/ mají stejnou výšku a stejnou barvu vlasů; Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace 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 má stejnou výšku jako y; • (x, y) G R právě když x má stejnou barvu vlasů jako y; • (x, y) G R právě když x, j/ mají stejnou výšku a stejnou barvu vlasů; • (x, y) G -R právě když x, y mají buď stejnou výšku nebo stejnou barvu vlasů. Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace 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 má stejnou výšku jako y; • (x, y) G R právě když x má stejnou barvu vlasů jako y; • (x, y) G R právě když x, j/ mají stejnou výšku a stejnou barvu vlasů; • (x, y) G -R právě když x, 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) G -R právě když \x — y\ je dělitelné třemi. V jakém smyslu jsou zde x a y „stejné"? Petr Hliněný, Fl MU Brno IB000 "Úv. Inf.": Binární Relace 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 má stejnou výšku jako y; • (x, y) G R právě když x má stejnou barvu vlasů jako y; • (x, y) G R právě když x, j/ mají stejnou výšku a stejnou barvu vlasů; • (x, y) G -R právě když x, 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) G -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 IBOOO definovaná takto: (x, y) G R právě když x i y sedí v první lavici. Petr Hliněný, Fl MU Brno IBOOO "Úv. Inf.": Binární Relace 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 má stejnou výšku jako y; • (x, y) G R právě když x má stejnou barvu vlasů jako y; • (x, y) G R právě když x, j/ mají stejnou výšku a stejnou barvu vlasů; • (x, y) G -R právě když x, 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) G -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 IBOOO definovaná takto: (x, y) G R právě když x i y sedí v první lavici. Proč se v tomto případě nejedná o relaci ekvivalence? Petr Hliněný, Fl MU Brno IBOOO "Úv. Inf.": Binární Relace 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 má stejnou výšku jako y; • (x, y) G R právě když x má stejnou barvu vlasů jako y; • (x, y) G R právě když x, j/ mají stejnou výšku a stejnou barvu vlasů; • (x, y) G -R právě když x, 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) G -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 IBOOO definovaná takto: (x, y) G 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.) □ Detr Hliněný, Fl MU Brno IBOOO "Úv. Inf.": 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 G TV, pak buď A = B nebo A n B = 0; >etr Hliněný, Fl MU Brno B000 "Úv. Inf.": 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, 5 G 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. >etr Hliněný, Fl MU Brno B000 "Úv. Inf.": 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, 5 G 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. • Nechť A0 = {k G N | k mod 3 = 0}, Ax = {k G N | fc mod 3 = 1}, A2 = {k G N | Ä mod 3 = 2}. Pak TV = {Ao,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 Rß/ na M. Petr Hliněný, Fl MU Brno 10 IB000 "Úv. Inf.": Binární Relace Věta 4.9. Buď M množina a M rozklad na M. Nechť R^ C M x M je relace na M definovaná takto (x, y) G üüjv právě když existuje A e TV taková, že x,y etr Hliněný, Fl MU Brno B000 "Úv. Inf.": Binární Relace Věta 4.9. Buď M množina a M rozklad na M. Nechť R^ C M x M je relace na M definovaná takto (x, y) G üüjv právě když existuje A G J\ľ taková, že x,y etr Hliněný, Fl MU Brno B000 "Úv. Inf.": 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) G üüjv právě když existuje A G TV taková, že x,y etr Hliněný, Fl MU Brno B000 "Úv. Inf.": 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) G üüjv právě když existuje A G TV taková, že x,y , proto (x, z) G ií/v" podle definice Rßj. D Detr Hliněný, Fl MU Brno 11 IBOOO "Úv. Inf.": 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 G M definujeme množinu [x] = {yeM\ (x,y) e R}. Pak {[x] | x G M} je rozklad na M, který značíme M j R. >etr Hliněný, Fl MU Brno B000 "Úv. Inf.": 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 G M definujeme množinu [x] = {yeM\ (x,y) e R}. Pak {[x] | x G M} je rozklad na M, který značíme M j R. Důkaz: Dokážeme, že M/R splňuje podmínky Definice 4.8. Petr Hliněný, Fl MU Brno IBOOO "Úv. Inf.": Binární Relace Pro každé [a?] G M/R platí [x] ^ 0, neboť x G [x] 3etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Binární Relace • Pro každé [x] G M j R platí [a;] ^ 0, neboť x e [x]. • Nechť [x], [y] G M j R. Ukážeme, že pokud [x] n [y] ^ 0, pak [x] 3etr Hliněný, Fl MU Brno IB000 "Uv. Inf.": Binární Relace • Pro každé [x] G M/R platí [a;] ^ 0, neboť x e [x]. • Necht [x], [y] G M j R. Ukážeme, že pokud [x] n [y] ^ 0, pak [x] = [y]. Jestliže [a;] n [y] ^ 0, existuje z G M takové, že z G [x] a z G [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G R. Jelikož R je symetrická a (y, z) G -R, platí (z, y) G -R. Jelikož (#,#), (z, y) G -R a E je tranzitivní, platí (x, y) G -R. Proto také (y,x) G -R (opět ze symetrie R). >etr Hliněný, Fl MU Brno B000 "Úv. Inf.": Binární Relace • Pro každé [x] G M/R platí [a;] ^ 0, neboť x e [x]. • Necht [x], [y] G M j R. Ukážeme, že pokud [x] n [y] ^ 0, pak [x] = [y]. Jestliže [a;] n [y] ^ 0, existuje z G M takové, že z G [x] a z G [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G R. Jelikož R je symetrická a (y, z) G -R, platí (z, y) G -R. Jelikož (#,#), (z, y) G -R a E je tranzitivní, platí (x, y) G -R. Proto také (y,x) G -R (opět ze symetrie R). Nyní dokážeme, že [y] = [x]: * ••[x] C [y]:" Nechť -y G [x]. Pak (x,«) G R podle definice [x]. Dále (y, x) G i? (viz výše), tedy (y, v) G i? neboť R je tranzitivní. To podle definice [y] znamená, že « G [y]. >etr Hliněný, Fl MU Brno B000 "Úv. Inf.": Binární Relace • Pro každé [x] G M/R platí [a;] ^ 0, neboť x e [x]. • Necht [x], [y] G M j R. Ukážeme, že pokud [x] n [y] ^ 0, pak [x] = [y]. Jestliže [a;] n [y] ^ 0, existuje z G M takové, že z G [x] a z G [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G R. Jelikož R je symetrická a (y, z) G -R, platí (z, y) G -R. Jelikož (#,#), (z, y) G -R a E je tranzitivní, platí (x, y) G -R. Proto také (y,x) G -R (opět ze symetrie R). Nyní dokážeme, že [y] = [x]: * ••[x] C [y]:" Nechť -y G [x]. Pak (x,«) G R podle definice [x]. Dále (y, x) G i? (viz výše), tedy (y, v) G i? neboť R je tranzitivní. To podle definice [y] znamená, že « G [y]. * ••[y] C [x]:" Nechť « G [y]. Pak (y,v) G i? podle definice [y]. Dále (x,y) G R (viz výše), tedy (x,-y) G R neboť R je tranzitivní. To podle definice [x] znamená, že v G [x]. >etr Hliněný, Fl MU Brno 13 IB000 "Úv. Inf.": Binární Relace Pro každé [x] G M j R platí [x] ^ 0, neboť x e [x]. Necht [x], [y] G M j R. Ukážeme, že pokud [x] n [y] ^ 0, pak [x] = [y]. Jestliže [a;] n [y] ^ 0, existuje z G M takové, že z G [x] a z G [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G -R. Jelikož R je symetrická a (y, z) G -R, platí (z, y) G -R. Jelikož (#,#), (z, y) G -R a E je tranzitivní, platí (x, y) G -R. Proto také (y,x) G -R (opět ze symetrie R). Nyní dokážeme, ze ,j = lzj: N £ [y]; Nechť -y G [x]. Pak (x,«) G i? podle definice [x]. Dále (y, x) G R (viz výše), tedy (y, v) G i? neboť i? je tranzitivní. To podle definice [y] znamená, že v G [y]. ••[y] C [x]:" Nechť « G [y]. Pak (y,«) G R 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 v G [x]. Platí U[ic]eM/ßM = M, neboť x G [x] pro každé a; G M. Petr Hliněný, Fl MU Brno 13 IBOOO "Úv. Inf D Binární Relace