Relace ekvivalence

příkady (řešené)   |   neřešené úlohy   |   řešení 



Výroková logika

Výrokové formy

Množinové vztahy

Množinové operace

Složené výrokové formy

Kartézský součin

Binární relace

Relace ekvivalence

Relace uspořádání

Relace zobrazení






Vytvoř písemku

Příklady (řešené)

1.  Vytvořte všechny možné rozklady množiny T = {xN;x<0 V 5≤x<8}.

Řešení:
Množinu T lze zapsat i výčtem prvků: T = {5,6,7}. Dále můžeme vytvořit
systém podmnožin množiny T:

P{T) = {Ø, {5}, {6}, {7}, {5,6}, {5,7}, {6, 7}, {5,6, 7}}. Vybrané prvky množiny P(T) nazveme třídami rozkladu právě tehdy, když platí:

a)    žádný tento prvek není prázdná množina,

b)    sjednocení těchto vybraných prvků je rovno T,

c)    každé dva tyto prvky P(T) jsou disjunktní.

Hledané řešení nalezneme v P(T) \ Ø.  Z  P(T) \ Ø vybereme např. množiny {5}, {6}, {7}, tyto množiny nazveme třídami rozkladu A, neboť splňují podmínky a), b), c). Označíme-li T1 rozklad množiny A, potom  T1 = {{5}, {6}, {7}},

další řešení:
T2    =    {{5}, {6,7}},
T3    =    {{6}, {5,7}},
T4    =    {{7}, {5,6}},
T5    =    {{5,6,7}}.

Rozklad T1 obsahuje 3 třídy rozkladu, je nejjemnějším rozkladem množiny T;  rozklady T2,T3, T4 obsahují 2 třídy rozkladu;  rozklad T5 obsahuje jednu třídu rozkladu, je nejhrubším rozkladem množiny
T; T5 = T.


2.  Zjistěte, zda relace R = {(4,4), (2, 2), (1,5), (2,3), (6, 5)} definovaná v množině A = {x  N;x ≤ 6}, je relace ekvivalence. Pokud není, doplňte ji minimálně nutným počtem uspořádaných dvojic tak, aby byla relací ekvivalence a určete rozklad množiny A daný touto ekvivalencí.

Řešení:
Sestrojme uzlový graf relace R (není podmínkou):

 
Z výčtu prvků relace R (i z grafu) zjistíme, že relace

a)    není reflexivní (chybí (1,1) a další),

b)    není symetrická (chybí (3,2) a další),

c)    je tranzitivní,

relace R není relací ekvivalence, Musíme ji doplnit.  Aby byla R reflexivní, doplníme (1,1), (3,3), (5,5), (6,6); aby byla symetrická, musíme ji doplnit (3,2), (5,1), (5,6). Tím, že jsme doplnili dvojice (viz výše),
zrušili jsme „původní" tranzitivnost, proto doplníme dvojice (1,6), (6,1) a relace R bude tranzitivní. Uzlový graf po doplnění :


Označme Rm množinu doplněných dvojic, RE relaci ekvivalence, potom
Rm = {(1,1), (3,3), (5,5), (6,6), (3,2), (5,1), (5,6), (1,6), (6,1)}
a  RE = R  Rm.
Relace  RE je relace ekvivalence definovaná na množině A, vytváří její rozklad.
Označíme-li třídy rozkladu A1  =  {4},  A2  =  {2,3},  A3  =  {1,5,6}, je rozklad množiny
AR = {A1, A2 ,A3 }.


Neřešené úlohy :


1. Kolik a jaké jsou relace ekvivalence na množině A, jestliže A je prázdná množina?


2. Kolik a jaké jsou relace ekvivalence na množině A, jestliže A je jednoprvková množina?


3. Kolik a jaké jsou relace ekvivalence na množině A, jestliže A je dvouprvková množina?


4. Kolik a jaké jsou relace ekvivalence na množině A, jestliže A je tříprvková množina?


5.  Je dána množina M = {a,b,c,d,e} a v ní relace S = {(c,c), (b,a), (b,d), (e,e)}. Minimálně nutným počtem uspořádaných dvojic doplňte relaci S na relaci ekvivalence SE a zapište rozklad množiny M na třídy ekvivalentních prvků.


6.  Je dána množina F = {p,q, r, s} a relace R = {(p,p), {r,r)}. Rozhodněte, zda R je relace ekvivalence. Není-li, doplňte ji minimálně nutným počtem uspořádaných dvojic na relaci ekvivalence RE, která vytváří nejjemnější rozklad množiny F.


7.  Je dána množina T = {1,2, 3,4, 5} a v ní relace R = {(1,1), (2,4), (3,3), (4,4)}. Minimálně nutným počtem uspořádaných dvojic doplňte relaci R na relaci ekvivalence RE a utvořte rozklad množiny T na třídy ekvivalentních prvků.


8.  Je dána množina K = {a,b,c,d,e,f} a v ní relace A = {(c,a), (b,e), (a,c), (d,d), (e,e), (f,f), (b,f),(d, f),
(b, b), (f,d)}. Rozhodněte, zda relace A je relací ekvivalence. Pokud není, doplňte ji minimálně nutným počtem uspořádaných dvojic na relaci ekvivalence AE a zapište rozklad množiny K.


9.  Je dána množina M = {a,b,c,d} a v ní relace R = {(a,a), (c,c)}. Minimálně nutným počtem uspořádaných dvojic doplňte relaci R na relaci RE, která vytváří rozklad množiny M na dvě třídy rozkladu. Kolik řešení má úloha? Znázorněte je na uzlových grafech.


10. Je dána množina M prvních pěti prvočísel. Určete dvě různé relace v množině M, z nichž první rozloží množinu na tři třídy a druhá na dvě třídy rozkladu.


11. M je množina všech úseček, jejichž krajní body jsou vrcholy libovolného čtverce. V množině M je dána relace A předpisem (x, y)  A <=> x je shodná s y. Výčtem prvků zapište relaci A, určete její vlastnosti a je-li relací ekvivalence, zapište rozklad množiny M.


12.  M je množina všech stran libovolného rovnostranného trojúhelníka. V množině M je dána relace
R = {(x,y)  M x M ; x je shodné s y}. Výčtem prvků zapište relaci R, určete její vlastnosti a je-li relací ekvivalence, zapište rozklad množiny M.


13. M je množina všech úseček, jejichž krajní body jsou vrcholy libovolného ko-sodelníka. V množině M je dána relace A = {(x, y)  M x M ; x || y}. Výčtem prvků zapište relaci A, rozhodněte, zda je relací ekvivalence. Pokud je, zapište rozklad množiny M na třídy ekvivalentních prvků.


Řešení :


1.  Existuje jen jedna, nulová relace


2.  Existuje jen jedna,  A2 = ∆A  (úplná relace)


3.  Existují právě dvě,  A2 = {(a,b),(b,a)} a  A


4.  Existuje jich právě pět : R1 = A  {(a,b),(b,a)}, R2 = A  {(a,c),(c,a)}, R3 = A  {(b,c),(c,b)},
 R4 = A , R5 = A2 .  


5.  SE = S {(a,a), (b,b), (d,d), (a,b), (d,b), (a,d),(d,a)};
třídy rozkladu: S1 = {a,b,d}, S2 = {c}, S3 = {e}, MR = {S1,S2,S3}.



6.  R není relace ekvivalence. RE = R  {(q, q), (s, s)}.
FR = {{p}, {q}, {r}, {s}} — nejjemnější rozklad množiny F.


7. RE = R  {(2, 2), (5, 5), (4,2)}; 
T1 = {1}, T2 = {3}, T3 = {5}, T4 = {2,4},  TR =  {T1, T2,T3,T4}. 


8.  A není relace ekvivalence;
AE = A  {(a,a),(c,c),(e,b),(f,b),(d,e),(e,d),(e,f),(f,e),(b,d),(d,b)}; třídy rozkladu K1 = {a,c}, K2 = {b,d,e,f}, KR = { K1, K2 }.


9.  Úloha má tři řešení :



10.  M = {2,3,5,7,11}; např. R1 = {(2,2), (3,3), (5,5), (7,7), (11,11), (2,3), (3,2), (7,11), (11,7)} a další; např. R2 = {(2,2), (3,3), (5,5), (7,7), (11,11), (2,3), (3,2), (2, 5), (5,2), (3,5), (5,3), (7,11), (11,7)} a další.



11.  M = {a, b, c, d, e, f}, kde a, b, c, d jsou strany čtverce, e, f jeho úhlopříčky. A = {(a, a), (b, b), (c, c), (d, d), (e, e), (f, f), (a, b), (b, a), (a, c), (c, a), (a, d), (d, a), (b, c), (c, b), (b, d), (d, b), (c, d), (d, c), (e, f), (f, e)}. A je relace ekvivalence; M1 = {a,b,c,d}, M2 = {e,f}, MR = {M1,M2}.



12. M = {a,b,c}; R = {(a, a), (b, b), (c, c), (a, c), (c, a), (a, b), (b, a), (b,c), (c, b)}; R je relace ekvivalence; MR = {{a, b, c}}.


13. M = {a, b, c, d, e, f }, kde a, b, c, d jsou strany kosodélníka, e, f jeho úhlopříčky. A = {(a, a), (b, b), (c, c), (d, d), (e, e), (f, f), (a, c), (c, a), (b, d), (d, b)}; A je relace ekvivalence; M1 = {a,c}, M2 = {b, d},
M3 = {e}, M4 = { f }, MR = { M1,M2,M3,M4 }.