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)
o
-►•    -,          T
' •  -        r  •
(c)
(d)
(e)
o
o
o
(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-23 + 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, SCAxE 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 aplikujeme.)
Nechť A je množina.   Definujme množiny
MM C Aa, 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é MCA 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) ^ia funkce f a g jsou různé. Protože byly zvoleny libovolně, dostáváme M.u H AI at = 0-
Zbývá dokázat, že (J <S = A . Je zřejmé, že S C A , protože množiny A1m 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 A1m 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^MCS 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