IBOOO Úvod do informatiky — príklady na procvičení Sada 3 — Ř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
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)  JR={(l,a),(2,a),(3,6),(2,c),(3,c)}CA1xA2
b)  R = {(1,1), (1, 2), (2, 2), (3, 2)} CAixAs
c)  R = A3 x A2 C Ax x A2
Řešení
a)  Totální funkce / : A\ —► A2, f C R existují čtyři:
A = {(1, a), (2, c), (3, c)} /2 = {(l,a),(2,a),(3,c)} /3 = {(l,a),(2,c),(3,6)} /4 = {(l,a),(2,a),(3,6)}
Injektivní je pouze funkce fy, surjektivní je také pouze funkce fy. Jedinou bijekcí je proto právě funkce fy.
b)  Totální funkce / : A\ —► A3, / C R existují dvě:
A = {(1,1), (2, 2), (3, 2)} fy = {(1,2), (2, 2), (3, 2)}
Injektivní není žádná funkce. Surjektivní je pouze funkce f\. Protože žádná funkce není injektivní, nemůže být žádná funkce ani bijektivní.
c)  Totální funkce / : A\ —► A3, f C R neexistuje žádná, protože (3,x) ^ R pro žádné X G A3.
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
1
Nechť A a. B jsou množiny. Pro následující případy nalezněte funkce / : A —► B a g : 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í SoR = id a-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, ß = {l}
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!
Řešení
Uvědomte si, že dokud budou odpovědi na otázky ze zadání kladné, jedná se vlastně o důkazy tvrzení „existují funkce f a g mající nějaké vlastnosti" a „existují relace R a S mající nějaké vlastnosti". Pro tento příklad nejlepším způsobem, jak taková tvrzení dokázat, bude nalezení konkrétních funkcí, resp. relací, které budou mít požadované vlastnosti. Formulace dokazovaných tvrzení, pokud odpověď bude záporná, budou uvedeny v průběhu řešení.
a)  Příkladem požadovaných funkcí / : A —► B a g : B —► A jsou / = {(1, a), (2, b), (3, c)} a g = /_1. Pro tyto funkce platí g o f = id^ i / o g = id#.
Příkladem relací R a S, kde alespoň jedna z nich (relace R) není funkcí, jsou
R= {(1,1), (2, 2), (2, 3), (3, 3)} S = {(1,1), (2,2), (3, 3)}
Pro tyto dvě relace platí S o R = kl a- Naopak Ro S ^ id#.
Relace S musí být funkcí. Pokud by navíc mělo platit i R o S = id#, musela by i relace R být funkcí. Zkuste to dokázat. Místo rozboru všech možností dokažte obecnější tvrzení. Využijte toho, že \A\ = \B\ {A a B mají stejný počet prvků).
b)  Příkladem požadovaných funkcí f: A^Bag: B^A jsou
/ = {(1,2),(2,3)}
g = {(1,1), (2,1), (3, 2), (4, 2)}
Pro tyto funkce platí g o f = id a-
Příkladem požadovaných relací RCAxBaSCBxA jsou
E={(1,1),(1,2)(2,3)}
S = {(1,1), (3, 2), (4,1), (4, 2)}
Pro tyto dvě relace platí S o R = id a-
Pro tyto dvě množiny A a B nemůže vztah R o S = idß platit pro žádné dvě relace R C AxB a S C BxA bez ohledu na to, jsou-li funkcemi nebo ne. Zkuste to dokázat. Místo rozboru všech možností dokažte obecnější tvrzení. Využijte toho, že \A\ < \B\.
2
c)  Protože \A\ > \B\, neexistují žádné relace RCAxB&SCBxA bez ohledu na to, jsou-li funkcemi nebo ne, pro něž by platilo S o R = id a- Využije se stejné tvrzení jako v závěru předchozího případu.
d)  Protože A = 0, platí AxB = BxA = 0. Uvažme nejprve libovolné relace R C Ax B a S C B x A. Jedinými takovými relacemi jsou R = S = 0. Přitom R je totální funkce R : A —► B a S je parciální funkce S : B —► A. Protože toto jsou jediné relace, stačí zjistit, které z požadovaných vlastností splňují.
Vztah S o R = id a platí. Uvědomte si, že id.0 = 0.
Vztah R o S = idß neplatí a vzhledem k výše uvedenému neexistují žádné relace, které by jej pro dané množiny A a. B splňovaly.
e)  Analogickými úvahami jako v předchozím případě dospějeme k tomu, že neexistují žádné relace ani funkce požadovaných vlastností.
Příklad 3.
Mějme relaci R = {(i, 2i) | i G 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!
Řešení
a)  R-1 = {(2i,i) | í G No}
b)  RoR = {(i,4i) | ie No}
Příklad 4.
Mějme relaci R = {(i,j) | existuje k G N 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.
Řešení
a)  R = {(j, i) | existuje k G N tak, že i = k ■ j}
b)  Tvrzení platí. Protože se jedná o rovnost dvou množin, dokážeme dvě inkluze. Uvědomte si, že R je relací dělitelnosti: (i, j) G R právě tehdy, když i je dělitelné j. Triviálně proto platí (i, i) G R pro všechna i G N. Uvědomte si, že 0 = k ■ 0 pro všechna fc G No. Skutečnost, že existuje více takových k nám v tomto příkladě, na rozdíl od algebry, nevadí. Nezáleží proto na tom, zda nulu považujeme za přirozené číslo nebo ne.
R C R o R. Nechť (i, j) G R. Protože (j, j) G R, platí (i, j) G R o R.
R o R C R. Nechť (i, j) E R o R. Z definice skládání relací proto existuje k E No takové, že (i, k) E R a (k, j) E R. Protože (k, j) E R, existuje z definice R číslo m G No takové, že k = m ■ j. Podobně z (i, k) E R dostáváme, že existuje n E No takové, že i = n- k. Celkem dostáváme i = (n- m) ■ j. Tedy existuje / G No takové, že i = l ■ j (stačí položit / = m ■ n). Proto (i, j) E R.
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!
3
Řešení
a)  Protože plus je relace mezi množinami N x N a N, není složení plus o plus definováno.
b)  plus-1 o plus = {((i, j), (k,l)) E (NxN) x (N x N) | i + j = k + l}
c)  plus o plus-   = {(n, n) E N x N | existují i, j E N tak, že n = i + j}
Pokud 0 ^ N, potom plus o plus- = {(n, n) E N x N | n > 1}, protože 1 ^ i + j pro žádná nenulová přirozená čísla i a j.
Pokud 0 G N, potom plus o plus-   = idpj.
d)  Podobně jako v prvním případě není plus-   o plus-   definováno.
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í?
Řešení
Funkce / není injektivní, protože nejsou definovány obrazy všech prvků definičního oboru. Nemá tedy smysl porovnávat obrazy dvou různých vzorů.
Protože pro každé n E N platí f(5n) = n, je funkce / surjektivní.
Protože funkce / není injektivní, nemůže to být ani bijekce.
Relace /-1 je totální funkce definovaná předpisem f~1(x) = 5x. Dokažte toto tvrzení. (Musíte dokázat rovnost dvou množin-relací. Relace, kterou získáte z funkce / pomocí definice inverzní relace, a relace definující funkci /-1 podle uvedeného předpisu.)
Funkce /-1 je injektivní, protože pro m,n G N, m ^ n platí 5m ^ 5n.
Funkce /-1 není surjektivní. Například číslo 4 není obrazem žádného přirozeného čísla ve funkci /_1.
Protože funkce /-1 není surjektivní, není ani 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.
Řešení
Složení fog není definováno, protože obor hodnot funkce g nemusí být ani podmnožinou definičního oboru funkce /.
Funkce go f je injektivní. Abychom to dokázali, musíme ukázat, že splňuje vlastnost z definice injektivní funkce. Musíme tedy ukázat, že pro libovolné x, y E A, x ^ y platí
(g o f)(x)ŕ (g o /)(y).
Mějme tedy x, y E A, x ^ y libovolné. Protože / je injekce, platí f (x) ^ f(y)-Protože g je injekce, platí g(f(x)) ^ g(f(y))- Ovšem g(f(x)) = (g o f)(x) a g(f(y)) = = (g o f)(y). Celkem tedy dostáváme (g o f)(x) ^ (g o f)(y), což jsme měli dokázat.
Promyslete si: Musí být funkce / injekce, aby tvrzení platilo? Musí být funkce g injekce, aby tvrzení platilo? Může tvrzení platit, i když ani jedna z funkcí není injektivní?
Nápověda: otázkou tedy je, zda existují nějaké konkrétní funkce f a g takové, že g o f je injektivní, ale /, g, resp. ani jedna z f a g není injektivní.
4