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 ^ / / / í a e ^ 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ť E C M x M j e binární relace na množině M. Řekneme, že relace R je divná,
jestliže R o R C idjvfe)
Nechť ň C M x M j e 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 ž C M x M j e 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/ RiPotom
(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 Js o u
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 = idjvfPří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} C N 0 x N 0
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} C Q x Q
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 N0
N
° x N0
N
°
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,fcG No}
R* = {{k,2l
k) | M e N o }
i f = {(2^,2-^) | z, j , k e N0}
b)
c)
d)
e)
R 0 = {(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 G N , / C G N 0 }
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
R 0 = {(k, k)\keQ}u {(k, k2
) \ke N0}
R = {(k, k2
)\ke No} U {{k2
, k) \ k e N0}
R+ = {{k,k2t
) | í G N,fcG N0}
R* = {(k,k) I k G Q} U {(fc,fc2
*) \i,ke N0}
j f = {(fc,fc) | fceQ}u{ŕ,fc23
) | i,j,k e No}
R0 = {(a,b) G Q x Q | 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
/ ^ G N O ^ A V X G N O
N,
/ ^ G N O ^ A V X G N O
N,
Äo = {(/,/) I /eNof l o
}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 N0
N
° A 3 k E N V x E N0 : g(x + fc) = /(x)}
/, 5- G N0
N
° A 3 k E N0 V x E N0 : #(x + k) = f {x)}
f, g E N0
N
° 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 ? a x i } u f x f
{(R, R) i ? a x i } u f x f
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).