IBOOO Úvod do informatiky -- príklady na procvičení
Sada 7 -- Zadání
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.
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.)
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.)
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} C N 0 x N 0
b) R = {(k + 2, k) I k E No} C No x No
c) R= {(a,b) | 6 | a} C N0 x N0
d) R={(k,k2
) | k E N0} C Q x Q
e) R = {(a, b) | a < b + 3} C Q x Q
f) R = {(/, g) | V x E No : g(x + 1) = f (x)} C N<T° x N<T°
g) Nechť T C 2 je množina všech parciálních funkcí z A do A. R = {(f, g) \ fUg E
E T} C J7
x J7
Jak by se výsledky změnily, kdybychom uvažovali obecné parciální funkce
z Ado B?
h) Nechť T C 2 je množina všech parciálních funkcí z Ado A. R = {(f, g) E TxT \
| / 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 >?
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.