IBOOO Úvod do informatiky — príklady na procvičení Sada 7 — Ř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
Relace, vlastnosti relací. Ekvivalence. Uspořádání. Vhodně definované vlastnosti relací. Uzávěry relací.
Příklad 1.
Nechť T C 2 je množina všech parciálních funkcí z A do B. Udejte příklad množin A a B a funkcí e, f,g,h E T takových, že v uspořádané množině (T, C) funkce e pokrývá funkce f a g a funkce / je pokrývána funkcemi e a h.
Řešení
Při řešení použijeme zbabělý trik. Protože v zadání není vyžadováno, aby / ^ g a e ^ h, z definice relace pokrytí musí platit pouze e^///íae^j//i. Proto pro jednoduchost můžeme uvažovat e = h a f = g. Vy však zkuste najít i takový příklad, kde e, f, g a h jsou čtyři navzájem různé funkce.
Nechť A = {a} a B = {b}, odkud T = {0,{(a,6)}}. Potom e = h = {(a,b)} a / = g = 0 jsou hledané funkce.
Příklad 2.
Rozhodněte, zda jsou následující vlastnosti binárních relací vhodně definované, a svá tvrzení dokažte. U vlastností, které nejsou vhodně definovány, ověřte, zda splňují alespoň jednu z podmínek kladených na vhodně definované vlastnosti.
a)  Nechť R C. M x M je binární relace na množině M. Řekneme, že relace R má hvězdičky před očima, jestliže pro každé x E M platí: (x, x) E R právě tehdy, když (x, y) E R pro všechna y E M.
b)  Nechť R C MxMje binární relace na množině M. Řekneme, že relace i? je odpudivá, jestliže pro každé x, y, z E M platí: pokud (x, y) E R a (x, z) E R, potom (y, z) E R.
c)  Nechť R C. M x M je binární relace na množině M. Řekneme, že relace R je přitažlivá, jestliže pro každé x,y E M platí: pokud (x, y) E R, potom existuje z E M takové, že (x, z) E R a (y, z) E R.
d)  Nechť ECMxMje binární relace na množině M. Řekneme, že relace R je divná, jestliže R o R C idjvf-
e)  Nechť ňCMxMje binární relace na množině M. Řekneme, že relace R je parciálni funkcí z M do M jestliže pro každé x, y, z E M platí: pokud (x, y) E R a (x, z) E R, potom y = z. (Dokažte také, že tato definice je konzistentní s obecnou definicí parciální funkce.)
1
f) Nechť ižCMxMje binární relace na množině M. Řekneme, že relace R je totální funkcí z M do M jestliže pro každé x E M existuje y E M takové, že (x, y) E R a pro každé x, y, z E M platí: pokud (x, y) E R a (x, z) E R, potom y = z. (Dokažte také, že tato definice je konzistentní s obecnou definicí totální funkce.)
Řešení
a)  Vlastnost „mít hvězdičky před očima" je vhodně definovaná. K tomu, abychom to dokázali, musíme ukázat, že libovolná relace s hvězdičkami před očima splňuje obě podmínky z definice vhodně definované vlastnosti.
Pro první podmínku předpokládejme, že M je množina, R C M x M relace na M. Musíme ukázat, že potom existuje relace S* C M x M s hvězdičkami před očima taková, že R C S. Položme S = M x M. Snadno se ukáže, že relace S má hvězdičky před očima (udělejte to!), první podmínka je tedy splněna.
Pro druhou podmínku předpokládejme, že M je množina a pro každé i E I, kde / je indexová množina, je Rí C M x M relace s hvězdičkami před očima. Musíme ukázat, že relace f]iej Rí má také hvězdičky před očima.
Nechť (a, a) E f]iej Rí- Potom (a, a) E Rí pro každé i E I a protože relace Rí má hvězdičky před očima pro každé i E I, dostáváme, že pro každé i E I platí (a, b) E Rí pro každé b E M. Tedy (a, b) E f]iej Rí pro každé b E M.
Nechť naopak (a, b) E f]iej Rí platí pro každé b E M. Potom volbou b = a dostáváme (a, a) G Die/^i•
Uměli byste k libovolné relaci R C M x M vytvořit její uzávěr s hvězdičkami před očima? Pokud ano, jak?
b)  Odpudivost je vhodně definovaná vlastnost.
Nechť M je množina, R C M x M relace. Snadno se ověří, že M x M je odpudivá (dokažte!), takže první podmínka je splněna.
Pro druhou podmínku předpokládejme, že M je množina a pro každé i E I, kde / je indexová množina, je Rí C M x M odpudivá relace. Ukážeme, že f]ieI Rí je také odpudivá relace. Nechť x,y, z E M jsou libovolné prvky takové, že (x,y), (x, z) E Hie/ Ri-Potom (x, y), (x, z) E Rí pro každé i E I. Protože relace Rí je odpudivá pro každé i E I, pro každé i E I platí (y,z) E Rí. Tedy (y,z) E f]ieIRi, což bylo dokázat.
Uměli byste k libovolné relaci R C M x M vytvořit její odpudivý uzávěr? Pokud ano,jak?
c)  Přitažlivost není vhodně definovaná vlastnost.
První podmínka je splněna, protože M x M je přitažlivá (dokažte!).
Protipříklad pro druhou vlastnost tvoří například množiny A = {a,b,c}, I = {1,2} a relace R\ = {(a,b),(b,a),(b,c),(c,b),(c,a),(a,c)} a R2 = {(a,b),(b,b)}. Potom R\ i i?2 Jsou přitažlivé (dokažte rozborem po jednotlivých prvcích), ale R\ n R2 = {(a, b)}, což není přitažlivá relace.
Uměli byste k libovolné relaci R C M x M vytvořit její přitažlivý uzávěr? Pokud ano,jak?
d)  Divnost není vhodně definovaná vlastnost.
Uvažme relaci R = M x M C M x M, kde M je množina. Potom jediná relace S na M, pro kterou platí R C S, je S = M x M, ovšem M x M není divná, pokud M je alespoň dvouprvková (dokažte!). Tedy divnost nesplňuje první podmínku. Uvědomte si, že jsme zde použili obecnější tvrzení: vlastnost V splňuje první podmínku právě tehdy, když M x M má vlastnost V. Dokažte toto tvrzení.
2
Druhou podmínku divnost splňuje, pokud 7^0. Kdybychom připustili i možnost 7, dostali bychom se do problémů, jejichž vysvětlování sahá za rámec těchto příkladů. Problémy mají souvislost s tím, že neplatí první podmínka. Kdyby platila, problémy by se neprojevily.
Nechť tedy M, 7^0 jsou množiny, Ri C M x M divná relace pro každé i E I. Abychom ukázali, že f]ieI Ri je divná relace, musíme ukázat, že f]ieI Ri o f]ieI Ri C C idjvf- K tomu stačí dokázat následující implikaci
(a,b)e[)Rio[)Ri^a = b
íel        íel Nechť tedy (a, b) E f]iej Rí o f)ieI Rí.  Z definice skládání relací existuje c E M takové, že (a, c) E f]ieI Ri a (c, b) E f]ieI Ri-   To může nastat jen tehdy, pokud (a, c) E Ri a (c, b) E Ri pro každé i E I.  Protože 7^0, existuje j E I takové, že (a, c), (c, b) E Rj, takže (a, b) E Rj o Rj C ícIm, protože Rj je divná relace. Tedy a = b.
Dobře si promyslete, proč jsme v předchozím odstavci potřebovali předpoklad 7^0.
Uměli byste k libovolné relaci R C M x M vytvořit její divný uzávěr? Pokud ano, jak?
e)
Tato definice je vlastně instancí definice pro obecné funkce / : A —► B, pokud položíme A = B = M.
Protože M x M není parciální funkce (dokažte!), nesplňuje tato vlastnost první podmínku (vizte výše).
Důkaz toho, že druhá podmínka pro 7^0 platí je snadný a ponecháváme jej čtenáři. f) V tomto případě jsou všechny důkazy natolik snadné, že uvedeme pouze správné výsledky a důkazy ponecháme čtenáři.
Skutečně se jedná o totální funkce, i když zde není korespondence tak zřejmá jako v případě parciálních funkcí.
Protože M x M není totální funkce (dokažte!), nesplňuje tato vlastnost první podmínku (vizte výše).
Tato vlastnost nesplňuje ani druhou podmínku. Protipříkladem jsou množiny M = = {a, b}, I = {1,2} a relace R\ = {(a, b), (b, a)} a R2 = idjvf-
Příklad 3.
Určete reflexivní, symetrický, tranzitivní, reflexivní a tranzitivní, resp. reflexivní, symetrický a tranzitivní uzávěr následujících relací. Nestačí jen opsat definice. Podejte přesné charakterizace prvků jednotlivých uzávěrů.
a)  R = {(k, 2k)\kE No} CN0xN0
b)  R = {(k + 2, k) I k E No} C No x No
c)  R= {(a,b) I 6 I a} C N0 x N0
d)  R={(k,k2) I k E No} CQxQ
e)  R = {(a, b) I a < b + 3} C Q x Q
f)  R = {(/, g) I V x E No : g (x + 1) = f (x)} C N0N° x N0N°
g)  Nechť T C 2 je množina všech parciálních funkcí z A do A. R = {(f, g) \ f U g E E T} C T x T Jak by se výsledky změnily, kdybychom uvažovali obecné parciální funkce z A do B?
h) Nechť T C 2        je množina všech parciálních funkcí z A do A. R = {(/', g) E TxT \ I / U g E J7} C 2         x 2        . Jak by se výsledky změnily, kdybychom uvažovali obecné
parciální funkce z A do 7??
3
Řešení
V řešení budeme značit R0 reflexivní, R symetrický, R+ tranzitivní, R* reflexivní a tranzitivní a R   reflexivní, symetrický a tranzitivní obal relace R. a)
r0 = {(k, k) | k e No} U {(k, 2k) \ k e N0} R = {(k, 2k)\ke No} U {(2fc, k) \ k e N0} ^+ = {(^,2^) | í G N, fc G No} R* = {{k,2lk) | MeNo} if = {(2^,2-^) | z, j, k e N0}
b)
c)
d)
e)
r0 = {(k, k) | k g No} U {(k + 2,k)\ke N0} i? = {(k + 2, fc) | k G No} U {(fc, k + 2) | fc g No} i?+ = {(fc + 2i,fc) | i gN,/cgN0} E* = {(fc + 2i,fc) | i, k e No} R* = {(k + 2i,k + 2j) | i, j, k G N0}
i?0 = {(a, b) G No x No | b\ a} R = {(a, b) G No x No | b | a nebo a | 6} R+ = {(a, b) G No x No | b\ a} R* = {{a,b) G No x No | b\ a} R* = No x No
r0 = {(k, k)\keQ}u {(k, k2) \ke N0} r = {(k, k2)\ke No} U {{k2, k) \ k e N0} R+ = {{k,k2t) | í G N, fc G N0} r* = {(k,k) I k g Q} U {(fc,fc2*) \i,ke N0} jf = {(fc,fc) | fceQ}u{ŕ,fc23) | i,j,k e No}
R0 = {(a,b) GQxQ|a<6 + 3} R =Q x Q i?+ = Q x Q R* = Q x Q #* = O x O
4
f)
Nn
R
R+ R*
r
/^gNo^AVxgNo
N,
/^gNo^AVxgNo
N,
Äo = {(/,/) I /eNoflo}u
{(f, g) {{f, g) {(f, g) {(f, g) {(J, g)
f, g E Wi0 A V x E No
g(x+l) = f(x)} g(x+l) = f(x)}U f(x + l)=g(x)} f, g E N0N° A 3 k E N V x E N0 : g (x + fc) = /(x)} /, 5- G N0N° A 3 k E N0 V x E N0 : #(x + k) = f {x)} f, g E N0N° A 3 k, l E N0 V x E N0 : g (x + fc) = f {x + /)} g) Nenechte se zastrašit složitými konstrukcemi. Tento příklad je velmi jednoduchý.
Ro = {(f,g) \f,gEfjUgEF} R = {(J,g) \f,gET,fugET}
R+ = 3= x T R* = T*T R* = TkT
Pokud bychom uvažovali obecné parciální funkce z A do B, na výsledcích by se nic nezměnilo. h)
Ro
n
R+ R*
r
{(R, R) \RCAxA}l) {(f,g) | f,g E T, fU g E T}
{(J,g) \f,gET,fugET}
{(R, R)   i?axi}ufxf {(R, R)   i?axi}ufxf
Pokud bychom uvažovali obecné parciální funkce z A do B, na výsledcích by se nie nezměnilo.
Příklad 4.
Dokažte, nebo uveďte protipříklad pro následující tvrzení.
a)  Jestliže R, S jsou uspořádání na M, potom také R o S je uspořádání na M.
b)  Jestliže R je uspořádání na M, potom také i?-1 n i? je uspořádání na M.
Řešení
a)  Tvrzení neplatí. Jako protipříklad uvažme M = {a, b,c,d}, S = idj^fU {(a, b), (c, d)}, R = idjvf U {(b, c), (d, a)}. Potom (a, c), (c, a) E R o S, takže R o S není antisymetrická relace.
b)  Tvrzení platí. Nechť x E M. Jelikož R je reflexivní, platí (x, x) E R, tedy také (x, x) E R~ľ. Proto (x, x) E R~ľ n R a tudíž R~ľ n i? je reflexivní.
Nechť (x,y), (y, x) E R~ľ n R. Pak (x, y), (y, x) E R, a protože R je antisymetrická, platí x = y (což bylo dokázat).
Nechť (x, y), (y, z) E R~ľ fl R. Pak (x, y), (y, z) E R~ľ a (x, y), (y, z) E R. Z tranzitivity R dostáváme, že (x, z) E R. Jelikož (x,y), (y, z) E R~ľ, platí (y,x), (z,y) E R a proto (z,x) E R (opět z tranzitivity R). Celkem (x, z), (z, x) E R, tedy (x, z) E R~ľ n R (což bylo dokázat).