IBOOO Úvod do informatiky — príklady na procvičení Sada 2 — Ř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
Důkaz vět typu „tehdy a jen tehdy". Množiny, vztahy mezi množinami, operace nad množinami.
Příklad 1.
Rozhodněte, zda 1 patří do množiny (R značí množinu reálných čísel, Z značí množinu celých čísel) a){l,2,{l}}
b) {{!},{{!}}} c){{1,2},{1,{1}}}
d)  {{{1}}}
e)  {x G E I x je celé číslo větší než 1}
f)  {x G ÍR | x je třetí mocninou přirozeného čísla}
g)  {3z + 7 | z G Z}
Řešení
a)  Ano.
b)  Ne.   Množina má prvky {1} (množina obsahující 1) a {{1}} (množina obsahující množinu obsahující 1). Ani jeden z nich není 1.
c)  Ne. Podobně jako v předchozím příkladě má množina dva prvky (jaké?), ani jeden z nich není 1.
d)  Ne. Množina má jediný prvek: množinu obsahující množinu obsahující 1, což není 1.
e)  Ne. Protože 1 je reálné číslo, tj. lei, stačí ověřit, zda splňuje podmínku „1 je celé číslo větší než 1". To ale není pravda, neboť 1 ýt 1.
f)  Ano.  Podobně jako v předchozím přiklade musíme ověřit, zda 1 splňuje podmínku „1 je třetí mocninou přirozeného čísla". To platí, protože 1 = l3 a 1 je přirozené číslo.
g)  Ano. Aby 1 patřila do množiny, musíme ověřit, že existuje celočíselné řešení rovnice 3z + 7 = 1. Řešením této rovnice je z = —2, což je celé číslo.
Příklad 2.
V termínech dělitelnosti charakterizujte prvky množiny
a)  {3n | n G N0}
b)  {An + 2 I n G N0}
1
Řešení
a)  Množina přirozených čísel dělitelných třemi.
b)  Množina přirozených čísel, jejichž zbytek po dělení čtyřmi je 2.
Příklad 3.
Výčtem prvků popište následující množiny (tj. vypište všechny jejich prvky):
a)  A = 2í°>
b)  B = 2{°'í°>>
c)  C = 2Ía'6'c>
d)  D = 2Ía'í6'c»
e)  E = 20
f)  F = 2W
g)  G = 2<*>W>
Řešení
a)  A = {0,{a}}
b)  B = {0, {a}, {{a}}, {a, {a}}}
c)  C = {0, {a}, {&}, {c}, {a, b}, {a, c},{b, c}, {a, b, c}} d)D = {$,{a},{{b,c}},{a,{b,c}}}
e) E = {0}
f)F = {0,{0}}
g)G = {0,{0} {{0}},{0,{0}}}
Jaký je rozdíl mezi množinami B a. Gl
Příklad 4.
Co můžete říct o množinách A a B, když víte, že platí následující vztahy? Svá tvrzení dokažte. (Nápověda: použijte relace C a = mezi množinami, případně jiné operace nad množinami a prázdnou množinu.)
a)  A D B = A
b)  A U B = A
c)  A \ B = A
d)  A\S = 0
Řešení
a)  Platí A C B. Pokud jste na to nepřišli, zkuste to nyní alespoň dokázat.
Dokazujeme tvrzení „AílB = A implikuje A <Z Bu. Důkaz provedeme přímo. Neboť A n B = A, platí A <Z Ail B, neboli každý prvek A patří do množiny A a zároveň patří do množiny B. Tedy každý prvek množiny A patří do množiny -S, tj. A <Z B.
b)  Platí B C A. Pokud jste na to nepřišli, zkuste to nyní alespoň dokázat. Dokazujeme tvrzení „A U B = A implikuje B C Au.   Podobně jako v předchozím
případě provedeme důkaz přímo. Neboť A U B = A, platí A U B C A, neboli každý prvek z množiny A nebo z množiny B je prvkem množiny A. Tedy každý prvek množiny B je prvkem množiny A, tj. B C. A.
c)  Platí Aí~\B = 0. Pokud jste na to nepřišli, zkuste to nyní alespoň dokázat. Dokazujeme tvrzení „A \ B = A implikuje A n B = 0". Důkaz provedeme sporem.
Nechť tedy A\B = A a. zároveň AílB ^ 0. Protože Ani? je neprázdná množina, existuje x E A H B, tj.   x E A a x E B.   Z definice rozdílu množin dostáváme, že x ^ A \ B.
2
Ovšem x E A, takže by neplatilo A \ B = A (množiny na levé a pravé straně rovnosti by se lišily v prvku x). Takže AC\ B musí být prázdná množina. d) Platí A C B. Pokud jste na to nepřišli, zkuste to nyní alespoň dokázat.
Dokazujeme tvrzení „A \ B = 0 implikuje A C Bu. Tvrzení dokážeme obměnou, budeme tedy dokazovat tvrzení „A $Z B implikuje J4\ß^fl".
Nechť tedy A ^ B. Potom existuje x E A takové, že x ^ B. Tedy z definice rozdílu množin vyplývá x E A \ B. Tedy A\B není prázdná množina, což jsme měli dokázat.
Příklad 5.
Mějme množiny Aa.B,A<ZMa.B<ZM pro nějakou množinu M.  Ukažte, že A C B platí právě tehdy, když B C A.
Řešení
Jedná se o větu typu „tehdy a jen tehdy". Přestože se jedná o velmi jednoduchý důkaz, budeme se držet šablony pro důkazy vět tohoto typu. Dokážeme tedy dvě implikace: zleva doprava (=^>) a zprava doleva (<í=).
Připomeňme, že doplňky množin zde implicitně uvažujeme vzhledem k množině M. Ekvivalence x ^ C -<=/- x E C, kde C C M, potom platí pouze tehdy, pokud se omezíme na x E M. Pokud bychom to neudělali, přestane platit implikace jedním směrem. Kterým? Co se stane s platností implikace druhým směrem? Jak se vztahuje tato poznámka k jednotlivým částem důkazu? Který směr se v které části používá?
„=>" Dokazujeme implikaci A C B =>- B C A, tj. předpokládáme, že A C B. Potom pro libovolné x E M platí x E A =>- x E B. Obměnou implikace dostáváme, že platí x ^ B =>- x ^ A. Tedy x E B =>- x E A, odkud již přímo plyne B C A.
„<=" Dokazujeme implikaci B C A =>- A C B. Nechť tedy B C A a uvažujme x E M libovolné. Protože platí x E B =>- x E A, platí také x^B^x^Aa obměnou implikace dostáváme x E A =>- x E B. Tedy A C B.
Uvědomte si, že z x E A ^- x E B pro x E M můžeme uzavřít A C B pouze tehdy, pokud A C M. Co by se stalo, kdyby to nebyla pravda? Najděte protipříklad.
Příklad 6.
Dokažte, že platí
{2z + 1 | z E Z} = {2z - 1 | z E Z}
kde Z značí množinu všech celých čísel.
Řešení
Máme dokázat rovnost dvou množin. Musíme tedy dokázat inkluzi zleva doprava a zprava doleva. Označme
A = {2z + 1 | z E Z} B = {2z - 1 | z E Z}
„C" Dokazujeme A C B. K tomu stačí dokázat, že x E A =^> x E B. Nechť tedy x E A. Potom existuje z E Z takové, že x = 2z + 1 = 2(z + 1) — 1. Ovšem z + 1 E Z, takže x E B.
Pokud jste důkaz nezvládli provést sami, zkuste teď sami alespoň druhou část.
3
„D" Dokazujeme B C A. K tomu stačí dokázat, že x E B =>- x E A. Nechť tedy x E B. Potom existuje z E Z takové, že x = 2z — 1 = 2(z — 1) + 1. Protože z — 1 E Z, platí x E A.
Příklad 7.
Dokažte, že pro každé n E N, n > 0 platí
n              n
i=l           i=l
kde Ai, i = 1,..., n jsou libovolné množiny.
Nápověda: všimněte si podobnosti s příkladem 5 první sady.
Řešení
Abychom mohli mluvit o doplňku množiny, musíme specifikovat nějakou její nad-množinu, vhledem k níž budeme doplněk určovat. V tvrzení není žádná taková množina explicitně uvedena. Tvrzení by tedy mělo implicitně platit pro každou takovou množinu, vzhledem k níž má smysl určovat doplňky. V dalším budeme předpokládat, že pro každé n E N máme libovolnou množinu M takovou, že platí Ai C M, i = 1,..., n. Bude tedy mít smysl vzhledem k ní určovat doplňky množin.
Důkaz povedeme matematickou indukcí vzhledem k n. Pokud jste nepoužili matematickou indukci, zkuste tvrzení dokázat i tímto způsobem. Přestože se v základním i indukční kroku jedná o důkaz rovnosti množin, nebudeme zde dokazovat dvě inkluze. V základním kroku bude rovnost zřejmá, v indukčním kroku využijeme již předem známé rovnosti množin.
Pro n = 1 rovnost zřejmě platí
~i                       l
(JAí = M = [)Tí í=i                      í=i
Pro důkaz indukčního kroku budeme potřebovat rovnost pro n = 2. Tuto rovnost lze znadno dokázat jako dvě inkluze. Udělejte to.
Ax U Ai = ~Ä[ n ~A~2
Nechť rovnost platí pro nějaké n E N. Potom
n+l                           n
\jAt = An+1 \j(JAí (použijeme již dokázanou rovnost pro n = 2)
n
= An+1 n\jAt
(druhý člen upravíme podle indukčního předpokladu)
n
= An+1 n p| Ä í=l
n+l
= f]Ä,
í=l Tím jsme rovnost dokázali pro n + 1 a důkaz matematickou indukcí je tak dokončen.
4