IBOOO Úvod do informatiky — príklady na procvičení Sada 3 — Zadání
Téma
Operace nad množinami. Relace mezi množinami. Skládání a inverze relací. Totální a parciální funkce. Injekce, surjekce, bijekce.
Příklad 1.
Mějme množiny A\ = {1,2,3}, A2 = {a,b,c} a A3 = {1,2}. Pro danou relaci R C C A; x Aj určete výčtem jejich prvků všechny totální funkce / : A{ —► Aj takové, že /CE. Které z nich jsou injektivní, surjektivní, resp. bijektivní?
a)  R= {(l,a),(2,a),(3,b),(2,c),(3,c)} C Aľ x A2
b)  R = {(1,1), (1, 2), (2, 2), (3, 2)} CAixAs
c)  R = A3 x A2 c Ax x A2
Příklad 2.
Nechť X je množina. Identitou nad X nazýváme binární relaci idx nad X definovanou vztahem
idx = {(x,x) \ x E X} C X x X
Nechť A a. B jsou množiny. Pro následující případy nalezněte funkce / : A —► B a <7 : B —► A takové, že g o f = id^. Existují takové funkce, aby navíc platilo f o g = id#? Existují relace fiCAxßaa'Cßxi, které nejsou funkcemi, a které splňují 5 o i? = id^. Existují takové relace, aby navíc platilo Ro S = idß? Svá tvrzení zdůvodněte.
a)  A = {1,2,3}, B = {a,b,c}
b)  A = {1,2}, B = {1,2,3,4}
c)  A = {1,2,3}, B = {1,2}
d)  A = 0, S = {1}
e)  A = {1}, ß = 0
Poznámky k zadání a řešení: Cílem tohoto příkladu je, abyste se zamysleli nad rozdílem
mezi obecnou relací a funkcí. Při řešení zjistíte, že zadání dovoluje v některých místech
více interpretací. K řešení si můžete vybrat jen jednu z nich nebo lépe postupně zkusit
všechny.
Protože se jedná o konečné případy, kreslete si při řešení obrázky.  Řešení pak ale vždy
zapište i ve formálním matematickém tvaru!
Příklad 3.
Mějme relaci R={(i,2i) \ie N0} C N0 x N0.
a)  Určete relaci i?-1.
b)  Určete relaci Ro R. Dosazení do definice nestačí! Zápis zjednodušte!
Příklad 4.
Mějme relaci R = {(i,j) \ existuje k eN tak, že i = k ■ j} C N x N.
a)  Určete relaci i?-1.
b)  Rozhodněte, zda platí R = R o R a své tvrzení dokažte.
Příklad 5.
Mějme relaci plus C (N x N) x N, plus = {((i,j),i + j) \ i, j G N}.
a)  Určete relaci plus o plus.
b)  Určete realci plus-   o plus.
c)  Určete relaci plus o plus- .
d)  Určete relaci plus-   o plus- .
Dosazení do definice složení relací nestačí! Zápisy zjednodušte!
Příklad 6.
Nechť / : N —► N je parciální funkce definovaná předpisem
f(\ — { x/§    pokud x je dělitelné pěti J ^   '      1 _L      jinak
Je tato funkce injektivní, surjektivní, bijektivní?   Uvažme relaci /_1.   Je tato relace funkce? Je to totální funkce? Pokud ano, je injektivní, surjektivní, bijektivní?
Příklad 7.
Nechť f: A^B&g: B^C jsou injektivní funkce. Rozhodněte, zda g o / a / o g jsou injektivní funkce. Své tvrzení dokažte.