Příklady
(řešené)
1.
Vytvořte všechny možné rozklady množiny T = {x
N;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 T
1
rozklad množiny A, potom T
1 = {{5},
{6}, {7}},
další řešení:
T
2
= {{5}, {6,7}},
T
3
= {{6}, {5,7}},
T
4
= {{7}, {5,6}},
T
5
= {{5,6,7}}.
Rozklad T
1 obsahuje 3 třídy rozkladu, je
nejjemnějším rozkladem množiny T; rozklady T
2,T
3,
T
4 obsahují 2 třídy rozkladu; rozklad T
5
obsahuje jednu třídu rozkladu, je nejhrubším rozkladem množiny
T; T
5 = 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 R
m množinu doplněných dvojic, R
E
relaci ekvivalence, potom
R
m = {(1,1), (3,3), (5,5), (6,6),
(3,2), (5,1), (5,6), (1,6), (6,1)}
a R
E = R

R
m.
Relace R
E je relace ekvivalence
definovaná na množině A, vytváří její rozklad.
Označíme-li třídy rozkladu A
1
= {4}, A
2
= {2,3}, A
3
= {1,5,6}, je rozklad množiny
A
R = {A
1, A
2 ,A
3 }.
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, A
2
= ∆A (úplná relace)
3.
Existují právě dvě, A
2 =
{(a,b),(b,a)} a
∆A
4.
Existuje jich právě pět : R
1 =
∆A

{(a,b),(b,a)}, R
2
=
∆A 
{(a,c),(c,a)}, R
3
=
∆A 
{(b,c),(c,b)},
R
4 =
∆A
, R
5 = A
2 .
5.
S
E = S

{(a,a), (b,b),
(d,d), (a,b), (d,b), (a,d),(d,a)};
třídy rozkladu: S
1 = {a,b,d}, S
2
= {c}, S
3 = {e}, M
R = {S
1,S
2,S
3}.
6.
R není relace ekvivalence. R
E = R

{(q, q), (s,
s)}.
F
R = {{p}, {q}, {r}, {s}} — nejjemnější rozklad
množiny F.
7. R
E
= R

{(2, 2), (5,
5), (4,2)};
T
1 = {1}, T
2 = {3}, T
3
= {5}, T
4 = {2,4}, T
R
= {T
1, T
2,T
3,T
4}.
8. A není relace ekvivalence;
A
E
= A

{(a,a),(c,c),(e,b),(f,b),(d,e),(e,d),(e,f),(f,e),(b,d),(d,b)}; třídy
rozkladu K
1 = {a,c}, K
2 =
{b,d,e,f}, K
R = { K
1, K
2
}.
9. Úloha má tři řešení :


10. M = {2,3,5,7,11}; např. R
1
= {(2,2), (3,3), (5,5), (7,7),
(11,11), (2,3), (3,2), (7,11), (11,7)} a další; např. R
2
= {(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; M
1 =
{a,b,c,d}, M
2 = {e,f}, M
R
= {M
1,M
2}.
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; M
R =
{{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; M
1 = {a,c}, M
2
= {b, d},
M
3 = {e}, M
4 = { f
}, M
R = { M
1,M
2,M
3,M
4
}.