IBOOO Úvod do informatiky -- příklady na procvičení
Sada 5 -- Řešení
Upozornění
Vzorová řešení dostáváte k dispozici, abyste mohli zkontrolovat správnost svých řešení.
Můžete je použít i jako návody k řešení jednotlivých příkladů tak, že je budete číst po
částech a budete se snažit další krok provést vždy sami. Příklady ztratí veškerý svůj
smysl, pokud se je budete učit jako básničku. Snažte se nad nimi přemýšlet a vyřešit je
sami, než se podíváte do vzorových řešení.
Téma
Vlastnosti relací -- relace reflexivní, symetrická, antisymetrikcá, tranzitivní. Ekvivalence
na množině a rozklad množiny.
Příklad 1.
Určete, které z následujících relací jsou reflexivní, symetrické, antisymetrické resp. tranzitivní.
Určete, které z relací jsou ekvivalence.
a) R ={(1,1), (1,2), (1,3), (2, 2), (2,3), (3,3)} C M x M, kde M = {1,2, 3}.
b) R= {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3)} C {1,2,3} x {1,2,3}.
c) R ={(1,1), (1,2), (1,3), (2, 2), (2,3), (3,3)} C M x M, kde M = {1,2,3,4}.
d) R = {(a, a), (b, b), (c, c)}
e) i? = 0
f) R= {(n,n+l) \neN}
g) R = {(m,n) E N x N \ 5 \ m & 7 \ n}
h) R = {(n, n + k) \ n, k G N}
í) R= {(n,n + k) j n, k G Z}
']) R = {(m,n) E Z x Z \ m ^ n}
Řešení
a) Relace je reflexivní, antisymetrická a tranzitivní. Relace není symetrická, protože
například (1,2) G R, ale (2,1) ^ R. Protože relace není symetrická, není to ekvivalence.
b) Relace je reflexivní. Relace není symetrická, protože (1,3) G R, ale (3,1) ^ R.
Relace není antisymetrická, protože (1,2) G i? a zároveň (2,1) G R. Relace není tranzitivní,
protože (3,2) G i? a (2,1) G R, ale (3,1) ^ R. Protože relace není symetrická a
tranzitivní, není to ekvivalence.
c) Relace je tranzitivní a antisymetrická. Relace není reflexivní, protože (4,4) ^ R.
Relace není symetrická, protože (1,2) G R, ale (2,1) ^ R. Protože relace není reflexivní
a symetrická, není to ekvivalence.
d) Tento příklad není úplně dobře zadán. Není jasné, na jaké množině relaci R uvažujeme.
Zkuste určit sami, jaké případy mohou nastat.
Pro binární relaci R musí platit R C M x M pro nějakou množinu M takovou, že
{a, b, c} C M. Rozlišíme dva případy.
{a, b, c} = M. Potom je relace R reflexivní, symetrická, antisymetrická i tranzitivní
(jedná se vlastně o identitu na M). Protože je relace reflexivní, symetrická a tranzitivní,
je to ekvivalence.
1
{a, b, c} C M. Tento zápis znamená, že exituje d G M, které je různé od a, b i
c. V tomto případě je relace R symetrická, antisymetrická a tranzitivní. Relace není
reflexivní, protože (d, ď) ^ R. Protože relace není reflexivní, není to ekvivalence.
e) Ani v tomto případě není jasné, na jaké množině relaci R uvažujeme. I zde rozlišíme
dva případy. Zkuste to nejprve sami. Pokud předpokládáme, že R C M x M, tak
definice relace R nevynucuje žádné prvky množiny M. Podle toho také vypadají případy,
které rozlišíme.
M = 0. Potom je relace R reflexivní, symetrická, antisymetrická i tranzitivní a je to
tedy i ekvivalence. Opět se totiž jedná o identitu na M.
M ^ | . Potom je relace R symetrická, antisymetrická a tranzitivní. Relace R není
reflexivní. Protože M ^ 0, existuje a G M, avšak (a, a) ^ R. Protože relace není
reflexivní, není to ekvivalence.
f) Relace není reflexivní, protože například (1,1) ^ R, i když 1 e N.
Relace není symetrická, protože například (1, 2) G R, ale (2,1) ^ R.
Relace je antisymetrická. Nechť a, b G N jsou libovolná přirozená čísla. Musíme
ověřit, že platí: (a, b) G R a (b, a) G R implikuje a = b. Ukážeme, že předpoklady
implikace nemohou být pro relaci R splněny. Tím dokážeme, že implikace platí.
Předpokládejme tedy, že platí (a, b) G R a zároveň (b, a) E R. Z prvního plyne, že
a = mab = m+l pro nějaké m G N. Z druhého plyne, že b = n a a = n+ 1 pro nějaké
n G N. Z rovností pro b dostáváme, že m+1 = n. Potom z rovností pro a dostáváme, že
m = n+l=m + 2, což je spor. Nemůže tedy zároveň nastat (a, b) E R a (b, a) E R.
Relace není tranzitivní, protože například (1,2) G i? a (2,3) G R, ale (1,3) ^ R.
Protože relace není reflexivní, symetrická a tranzitivní, není to ekvivalence.
g) Relace je tranzitivní. Nechť a,b,c G N jsou libovolná taková, že (a, b) E R a (b, c) E
E R. Z definice R a (a, b) E R plyne, že 5 | a. Z definice R a (b, c) E R plyne, že 7 | c.
Celkem tedy máme, že 5 | a a 7 | c, takže (a, c) E R. To jsme měli dokázat.
Relace není reflexivní, protože například pro číslo 4 G N platí 5 { 4, takže (4, 4) ^
^ R. Relace není symetrická, protože (5,7) G R, ale 7 f 5, takže (7,5) ^ R. Relace není
antisymetrická, protože 5 | 35, 7 | 35, 5 | 70 a 7 | 70, takže (35, 70) G R i (70, 35) G R.
Protože relace není reflexivní a symetrická, není to ekvivalence.
h) Pro řešení budeme předpokládat, že 0 G N. Jak by se výsledky změnily, kdybychom
nulu za přirozené číslo nepovažovali?
Relace je reflexivní. Pro každé n E N je (n, n) = (n, n + 0) G R.
Relace není symetrická. Například (1,2) G R, ale (2,1) ^ R.
Relace je antisymetrická. Nechť a, b E N jsou libovolná přirozená čísla, pro která
platí (a, b) E R a zároveň (b, a) E R. Potom existuje k E N takové, že b = a + k a existuje
/ G N takové, že a = b + /. Spojením obou rovností dostáváme b = b + k + /, odkud musí
být k + / = 0. Protože k > 0 i / > 0, musí platit k = l = 0. Když se vrátíme k původním
rovnostem, dostáváme a = b, což jsme měli dokázat.
Relace je tranzitivní. Nechť a,b,c E N jsou libovolná a nechť platí (a, b) E R a
(b, c) E R. Potom existují k, l E N taková, žeb = a + kac = b + l, takže c = a + (k + /),
k + / G N. Odtud (a, c) E R, což bylo dokázat.
Protože relace není symetrická, není to ekvivalence.
i) Relace je reflexivní ze stejného důvodu, jako relace v předchozím příkladě.
Relace je symetrická. Nechť a, b E Z, (a, b) E R jsou libovolná. Potom b = a + k pro
nějaké k E Z, odkud a = b + (--k), --k E Z, takže (b, a) E R.
2
Relace není antisymetrická, protože například (1,2) G R a ze symetrie plyne, že i
(2,1) G R. Pozor! Obecně neplatí, že každá symetrická relace není antisymetrická. Některé
předchozí příklady demonstrují relace, které jsou zároveň symetrické i antisymetrické.
Jak je možné všechny takové binární relace charakterizovat?
Relace je tranzitivní. Důkaz je analogický předchozímu případu. Proveďte jej sami
bez nápovědy!
Relace je reflexivní, symetrická i tranzitivní, je to tedy ekvivalence.
Ve skutečnosti platí R = Z x Z. Pokud byste chtěli tuto skutečnost využít, museli
byste tuto rovnost množin dokázat. Udělejte to!
j) Relace není reflexivní. Množina Z je totiž neprázdná, ale z definice (n, n) ^ R pro
každé n E Z. Proč je argument o neprázdnosti důležitý?
Relace je symetrická. Nechť a, b E Z, (a, b) E R jsou libovolné. Potom a ^ b, odkud
fe^aa tedy (b, a) E R.
Relace není antisymetrická, protože |Z| > 1 je neprázdná a dále ze symetrie. Proč
zde nestačí neprázdnost?
Relace není tranzitivní. Existují a, b E Z, a ^ b. Potom (a,b),(b,a) E R. Aby R
byla tranzitivní, muselo by platit (a, a) E R, což není možné.
Protože relace není reflexivní a tranzitivní, není to ekvivalence.
Příklad 2.
Pro každou z množin MQ = 0, Mi = {a} a M3 = {a, b, c} určete počet relací i ? C M,x Mi,
které jsou
a) reflexivní
b) symetrické
c) tranzitivní
Řešení
Aby to bylo zajímavější, pro počty reflexivních a symetrických relací nad konečnými
množinami odvodíme kombinatorickou úvahou vztahy závislé na velikosti množin.
Nechť M je konečná množina a uvažujme počty reflexivních, resp. tranzitivních
relací R C M x M. Označme n = \M\ počet prvků množiny M. Potom \M x M\ = n2
.
Relace R může mít tedy nejvýše n2
prvků. Počet všech relací R je
19MXM1 _ 9W2
Všimněte si, že pro n = 3 existuje tedy 512 různých relací, které byste museli vzít v úvahu,
kdybyste počty chtěli zjistit prozkoumáním všech možností.
a) Reflexivní relace splňuje
VaE M : (a, a) E R
Dvojic (a, a), a E M je n. Celkem tedy zbývá n2
-- n dvojic, které v reflexivní relaci R
být mohou, ale nemusí (definice reflexivity nic neříká o dvojicích (a, b), a,b E M, a^b).
Reflexivní relaci R tedy lze rozložit na R = P U Q, kde
P = {(a, a) I a E M}
Q c B = {(a, b) ER\a,bE M Aa^b}
Ano, je tím myšlen rozklad množiny. Dokazte, že {P, Q} je rozklad R. Počet
reflexivních relací R je tedy roven počtu podmnožin množiny s n2
-- n prvky (množina B).
Těch je
nn --n
3
b) Symetrická relace splňuje
Va,be M : (a,b) ER^ (b, a) E R
Protože pro každé a E M platí (a, a) E R => (a, a) E R, neovlivňují dvojice tohoto tvaru
symetrii relace. Zbylé dvojice v symetrické relaci i? je možné myšlené rozdělit do párů,
v jednom páru jsou vždy symetrické dvojice (a, b) a (b,a) pro a, b různá. Symetrickou
relaci R lze tedy rozložit na
jR = Pu|JtS,kde
P <ZA = {(a, a) | a E M}
S C C = {{(a,b), (b, a)} \a,bEM,a^b}
Dokazte, že S U {P} je rozklad R. Proč je to důležité? Počet symetrických
relací R potom můžeme napsat jako
\2A
\-\2C
\ T ˇ 2~ 2 2
c) Vztah pro počet tranzitivních relací by byl natolik složitý, že i pro n = 3 bude
jednodušší uvážit všechny možnosti, než jej odvozovat.
Pro množinu MQ existuje jediná relace R C MQ X MQ = 0 a to právě R = 0. Tato
relace je tranzitivní, takže počet tranzitivních relací je v tomto případě 1.
Pro množinu M\ existují dvě různé relace, kterými jsou R\ = 0 a R2 = {(a, a)}.
Obě jsou tranzitivní, takže tranzitivní binární relace na množině Mi jsou dvě.
Počet tranzitivních relací na M3 určíme rozborem všech možností podle nereflexivních
dvojic. Jednotlivé případy jsou znázorněny v obrázcích. Plné černé šipky vyznačují
zvolené prvky relace (nereflexivní uspořádané dvojice). Plné červené šipky vyznačují ty
prvky relace, které ke zvoleným musíme přidat, aby relace byla tranzitivní. Přerušované
šipky vyznačují prvky relace, které tranzitivitu neovlivňují a můžeme je tak do relace
libovolně přidávat, nebo je odebírat.
-  ˇ " - , r
(a) (b)
r>
- ˇ ˇ -, T ' ˇ - r ˇ
(c) (d) (e)
r r r>
(f) (g) (h) O)
Případ (a) určuje 23
relací podle toho, které reflexivní hrany do relace přidáme.
V případě (b) lze nereflexivní hranu umístit šesti různými způsoby, při každém z nich lze
23
způsoby přidat reflexivní hrany, celkem tedy popisuje 6 ˇ 23
relací. Případy (c) a (d) lze
pootočit třemi způsoby, při každém z nich lze 23
způsoby přidat reflexivní hrany, každý
z nich popisuje 3 ˇ 23
relací. Případ (e) lze otočit třemi různými způsoby, ke každému
z nich můžeme přidat refexivní hranu u zbylého vrcholu, je proto 3 ˇ 2 takových relací.
Případ (f) lze otočit třemi různými způsoby při zobrazené orientaci hran a třemi způsoby
při opačné orientaci hran, ke každému umístění lze přidat 23
způsoby reflexivní hrany,
tento případ popisuje 3-2-23
relací. Případy (g) a (h) lze třemi různými způsoby pootočit,
ke každému lze přidat reflexivní hranu, každý z těchto případů popisuje 3-2 relací. Případ
(i) je jediná relace.
Celkem máme (sčítance odpovídají po řadě znázorněným případům)
23
+ 6-23
+ 3-23
+ 3-23
+ 3-2 + 3 - 2 - 2 3
+ 3-2 + 3-2 + l = 171
tranzitivních relací.
Příklad 3.
Nechť A, B jsou množiny, / : A --ˇ B funkce. Uvažujme relaci R <Z A x A definovanou
předpisem
R={(x,y)eAxA\f(x) = f(y)}
Rozhodněte, zda je tato relace ekvivalencí a své tvrzení dokažte.
Řešení
Ano, relace je ekvivalence. Pro každé a E A platí f (a) = f (a), protože / je funkce,
tedy (a, a) E RaRje reflexivní. Nechť a, b E A jsou libovolné a platí (a, b) E R. Z definice
potom f (a) = f(b) a tedy i f(b) = f (a), odkud (b,a) E R. Proto R je symetrická.
Tranzitivita R plyne z tranzitivity rovnosti. Proveďte důkaz tranzitivity detailně
sami! Návod máte v prvním příkladě této sady.
Příklad 4.
Nechť A, B jsou množiny, S C A x E funkce. Uvažujme relaci R C B x B definovanou
předpisem
R = {(x, y) E B x B | 3 a E A : (a, x) E S A (a, y) E S}
Rozhodněte, zda je tato relace ekvivalencí a své tvrzení dokažte.
Řešení
V tomto příkladě jsem měl samozřejmě na mysli, že S C A x B je relace. Pokud
se omezíme pouze na funkce, platí následující dvě tvrzení. 1. R C klß 2. R = klß
právě tehdy, když S je surjektivní. Dokažte obě tvrzení. S odvoláním na předchozí
příklady lze potom říct, že R je vždy symetrická a tranzitivní. Pokud je navíc S surjekce,
je relace R i reflexivní, takže je to ekvivalence.
Reste tento příklad v případě, že S je obecná relace.
Pokud je S obecná relace, může to být i funkce a vzhledem k výše uvedenému nemusí
být R obecně ani reflexivní ani tranzitivní. Dokažte, že pro libovolnou relaci S je relace R
symetrická.
5
Příklad 5.
Nechť R, S C M x M jsou antisymetrické relace. Rozhodněte, zda platí, že S o R a R~ľ
jsou antisymetrické relace a svá tvrzení dokažte.
Řešení
Relace S o R nemusí být obecně antisymetrická. Protipříkladem je například M =
= {a,b,c}, R = {(a,a), (b,c)} a S = {(a,b),(c,a)}. Po složení dostáváme SoR =
= {(a,b),(b,a)}. Doporučuji, abyste si skládání relací nakreslili a promysleli si, co v
obrázku znamená porušení antisymetrie.
Relace i?- 1
je antisymetrická. Nechť a, b E M jsou libovolné takové, že (a, b) E R~ľ
a (b, a) E R~ľ
. Potom (b, a) E R a (a, b) E R a z antisymetrie R plyne, že a = b.
Příklad 6.
Rozhodněte, které z následujících systémů podmnožin množiny M = {1,2,3, 4, 5, 6} jsou
rozkladem množiny M. U rozkladů vypište výčtem prvků příslušné ekvivalence.
a) {{1,2,3}, {3,4}, {4,5,6}}
b) {{1,2,6}, {3,5}, {4}}
c) {{2,4,6},{1,5}}
d) {{1,4,5},{2,3,6}}
Řešení
a) Nejedná se o rozklad, neboť {1,2, 3} n {3, 4} ^ 0, i když se je to průnik dvou různých
množin.
b) Jedná se o roklad. Příslušná ekvivalence je
R = idM U {(1,2), (2,1), (1,6), (6,1), (2,6), (6, 2), (3, 5), (5,3)}
c) Nejedná se o rozklad, protože {2, 4,6} U {1, 5} ^ M.
d) Jedná se o rozklad. Příslušná ekvivalence je
R = idM U {(1,4), (4,1), (1,5), (5,1), (4, 5), (5, 4), (2,3), (3, 2), (2, 6), (6, 2), (3, 6), (6,3)}
Příklad 7.
Nechť A je množina. Uvažme systém S podmnožin množiny 2 , S = {Ma \ a E A}, kde
pro a E A je Ma = {M C A \ a E M}.
Určete, zda se jedná o rozklad množiny 2 , své tvrzení dokažte, a pokud ano, definujte
příslušnou ekvivalenci.
Řešení
Toto tvrzení obecně neplatí. Jako protipříklad vezměme A = {a, b, c} a M = {a, b} C
C A. Potom M E Ma a M E Mb, tedy Ma n Mb ^ 0. Zároveň však platí Ma ^ Mb
(najděte konkrétní podmnožinu A, která to dokazuje!). Systém S proto není rozklad.
Protipříklad jsme založili na množině A o velikosti 3. Platilo by tvrzení, kdyby měla
množina 0, 1 nebo 2 prvky?
Příklad 8.
Nechť A je množina. Definujme relaci R C 2 x 2 následovně: pro každé X,Y E 2
platí (X, Y) E R právě tehdy, když existuje bijekce / : X --ˇ y.
Dokažte, že R je ekvivalence a nalezněte třídy ekvivalence příslušného rozkladu.
6
Řešení
Ano, relace R je ekvivalence.
Nechť X C A je libovolná. Potom (X, X) G R, protože idx je bijekce z X do X.
Relace je reflexivní.
Nechť X,Y C A a (X,Y) G R. Potom existuje bijekce f : X -> Y. Protože
/ _ 1
: Y --ˇ X je také bijekce (jestli jste to zatím sami nezvládli, dokažte!), takže také
(Y, X) G i?. Relace je symetrická.
Nechť X, y, Z C A, (X, ľ ) e ň a (y, Z) G E. Potom existují bijekce / : X ->ˇ y a
<7 : y --ˇ Z. Protože g ° f je také bijekce (jestli jste to zatím sami nezvládli, dokažte!),
platí (X, Z) G i?. Relace je tranzitivní.
Příslušný rozklad S množiny 2 definujeme podle věty 12 ze skript. Jinak bychom
museli dokázat, že námi definovaná struktura je rozklad, a navíc ještě rozklad odpovídající
tomu, který je definován ve větě 12. Označme [M] = {N C A | (M, N) G R}. Potom S =
= {[M]\ M E2A
}. Takový zápis na písemce obvykle nestačí, proto definici jednotlivých
tříd ekvivalence dále zjednodušíme.
[M] = {N | existuje bijekce / : M --ˇ N} = {N | množiny M a. N jsou stejně velké}
Ještě přehlednějšího zápisu bychom dosáhli tehdy, pokud bychom se omezili na
konečné množiny. Zkuste to!
Příklad 9.
Nechť A, B jsou množiny, / : A --ˇ B funkce. Definice funkce / se rozšiřuje na množiny
podle následujícího předpisu
/(M) = {f(x) \xeM}
(Přestože funkce označujeme stejně, jedná se vlastně o dvě různé funkce. Původní
/ : A --ˇ B a nově definovanou / ' : 2 --ˇ 2 . Stejné označení není na závadu --
typ funkce, kterou máme na mysli, je jednoznačně určen tím, na jaký argument ji apliku­
jeme.)
Nechť A je množina. Definujme množiny
MM C A A
, kde M C A, a systém S C 2A
následovně:
MM = {/ | f (A) = M}
S = {MM I 0 ^ M C A}
Dokažte, že S je rozklad na A a určete příslušnou relaci ekvivalence. Byla by to pravda
i v případě, kdy bychom uvažovali obecné funkce / : A --ˇ B?
Nápověda: Pečlivě si uvědomujte, se kterou strukturou v kterém okamžiku pracujete.
Například S je množina množin funkcí z A do A.
Řešení
Ze zadání mi vypadlo, že funkce se rozšiřuje samozřejmě pouze na takové množiny M,
pro které M C A Z definice je to zřejmé -- jinak by rozšíření nebylo dobře definováno.
Musíme ověřit, že S splňuje všechny tři podmínky z definice rozkladu.
0 ^ S, protože pro každou neprázdnou množinu MCA existuje funkce / : A --ˇ A
taková, že f (A) = M (najděte ji! vyjděte z identity na A), takže / G MM a
MM Je
neprázdná.
7
Nechť M-Mj-M-N  <$, kde M, N C A jsou neprázdné. Druhou podmínku pro
rozklad budeme dokazovat ve tvaru implikace M.M Ť^ M-N =^ -MM ^ MN = 0- Nechť
tedy M.M 7^ M.N- Proto M ^ N. Bez újmy na obecnosti předpokládejme, že existuje
x E M takové, že x ^ N (opačný případ by byl analogický). Nechť / G M.M, 9 = -MN
jsou libovolné funkce, / : A --ˇ A, g : A --ˇ A. Z definice platí /(A) = M a <jf(Ä) = iV.
Zejména tedy existuje a E A takové, že f (a) = x. Protože x ^ N, platí g (a) ^ i a funkce
f a g jsou různé. Protože byly zvoleny libovolně, dostáváme M.u H AI AT = 0Zbývá
dokázat, že (J <S = A . Je zřejmé, že S C A , protože množiny A 1 M obsahují
pouze funkce / : A --ˇ A, tedy prvky A . Uvažme tedy libovolnou funkci / G A .
Protože f (A) = M pro nějakou neprázdnou množinu MCA, platí / G A 1 M G <S. Proto
platí také / G (J S.
Ekvivalenci R C A x A budeme definovat podle věty 11, abychom nemuseli dokazovat
korektnost konstrukce (srovnejte s předchozím příkladem).
R = {(/, 9)\f,geMM Pro nějakou 0 ^ M C A}
= {(f,g)\f(Ä) = g(Ä)}
Obecné funkce / : A --ˇ B bychom mohli uvažovat pouze v případech, kdy by platilo
\A\ > \B\. Kromě toho musí platit A = 0 =>- B = 0, jinak by konstrukce nebyla dobře
definována. Jestliže jsou tyto podmínky splněny, tak pro každou I ^ M C S víme, že
existuje g : A --ˇ B taková, že g (A) = M. (Dokažte to! Neomezujte se na konečné nebo
spočetné množiny.)
Pokud by bylo \A\ < \B\, tak by neexistovala funkce g : A --ˇ B taková, že g (A) = B
(dokažte!) a systém S by potom obsahoval prázdnou množinu. Nebyl by to tedy rozklad.
8