IBOOO Úvod do informatiky — príklady na procvičení Sada 9 — Ř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 Induktivně definované množiny, jednoznačné induktivní definice, induktivně definované funkce z induktivně definovaných množin. Strukturální indukce. Příklad 1. Nechť M C No je induktivně definována takto: • 0 G M • jestliže x G M, potom x + 4 G M a) Zapište formálně funkce induktivních pravidel této definice. b) Platí 129 G M? Platí 65 G M? c) Množinu M zapište explicitně, tj. ve tvaru M = {...}. d) Je tato definice jednoznačná? Svou odpověď zdůvodněte. Řešení a) Tato definice má jediné induktivní pravidlo, které je určeno funkcí / : M —► M, f (x) = x + 4 pro každé x G M. b) Platí 129 ^ M a 65 ^ M. Protože induktivní pravidlo je rostoucí v tom smyslu, že větší číslo je prvkem množiny M na základě toho, že nějaké menší číslo je prvkem množiny M, stačí začít se základním prvkem množiny M a aplikovat induktivní pravidlo tak dlouho, dokud nedojdeme alespoň k číslu 129. Pokud číslo 129 odvodíme, potom 129 G G M. Pokud odvodíme číslo větší než 129, aniž bychom předtím odvodili 129, potom 129 ^ ^ M. Pro číslo 129 by příslušná sekvence byla 0,4,8,12,..., 124,128,132 takže 129 ^ M. Analogicky bychom argumentovali pro 65 ^ M. c) M = {An I n G No} Důkaz indukcí ponecháváme čtenáři. Jako návod poslouží analogické důkazy, které provedeme u dalších, složitějších příkladů. Důkaz správnosti explicitního vyjádření spočívá v důkazu rovnosti dvou množin. Musíme již tedy znát jak induktivní definici množiny, tak její explicitní vyjádření. Není jasné, jak jsme explicitní vyjádření určili. Algoritmus neexistuje. S trochou zkušeností u těchto jednoduchých příkladů použijete metodu „podívám se a vidím". Když se podíváte a nevidíte, zpravidla pomůže, když začnete s bázovými prvky a systematicky vypíšete nejsnáze odvoditelné prvky množiny, 1 aniž byste vznikající výrazy zjednodušovali. V tomto příkladě by takovou posloupností bylo Oe M 0 + 4e M 0 + 4 + 4G M 0 + 4 + 4 + 4G M Nyní už si můžete všimnout toho, že 0 = 4-0 0 + 4 = 4-1 0 + 4 + 4 = 4-2 0 + 4 + 4 + 4 = 4-3 a pokud si alespoň na intuitivní úrovni uvědomujete důkaz indukcí, který budete muset provést, dojdete k závěru, že budou postupně vznikat všechny násobky čísla 4. Jedná se vlastně o stejný mechanismus, jako je určování tranzitivního obalu relace. d) Ano, tato definice je jednoznačná, protože množina má jediný bázový prvek a definice má jediné „rostoucí" induktivní pravidlo. Příklad 2. Nechť M C No je induktivně definována takto: • 0 G M • jestliže x G M, potom x + 3eM&x + 5eM • jestliže x,y G M, potom xy G M a) Zapište formálně funkce induktivních pravidel této definice. b) Platí 127 G M? Platí 17 G M? c) Množinu M zapište explicitně, tj. ve tvaru M = {...}. d) Je tato definice jednoznačná? Svou odpověď dokažte. e) Rozhodněte, zda platí tvrzení 3m G No- \/n G No- m < n =>- n G M a správnost svého rozhodnutí dokažte. Řešení a) Tato definice má ve skutečnosti tři induktivní pravidla, kterým odpovídají následující funkce: /i : M ->■ M, fi(x) = x + 3 pro každé x e M ji : M —► M, f2{x) = x + 5 pro každé x E M fe-.MxM^ M, fs(x,y) = xy pro každá dvě x,y G M b) Pokud chceme ověřit, že nějaké n G N patří do induktivně definované množiny M, musíme jej odvodit. Odvozením se rozumí taková posloupnost prvků M končící číslem n, že každý prvek posloupnosti je buď bázovým prvkem M, nebo vznikne z předchozích prvků posloupnosti a nějakého induktivního pravidla. Jedná se vlastně o podobný výpočet zdola nahoru, jako při výpočtu hodnoty formule pro danou valuaci. 2 Odvození ukážeme pro číslo 17. O) bázový prvek M (u) z (i) a funkce f\ (iii) z (ii) a funkce f\ (iv) z (iii) a funkce f\ (v) z (iv) a funkce f\ (vi) z (v) a funkce f2 0 G M 3 G M 6 G M 9 G M 12 G M 17 G M Tedy 17 G M. Podobně, jen delším odvození, bychom ověřili, že 127 G M. Opakovanou aplikací pravidla určeného funkcí f\ bychom odvodili, že 117 G M, odkud bychom dvojnásobnou aplikací pravidla určeného funkcí J2 dospěli k 127 G M. c) Určení explicitního vyjádření množiny si můžete usnadnit, pokud se přesvědčíte, že nepracujete se „zbytečnými" induktivními pravidly a bázovými prvky. Bázový prvek je „zbytečný", pokud je možné jej odvodit pomocí induktivních pravidel z jiných bázových prvků. Induktivní pravidlo je zbytečné, pokud je možné jej nahradit posloupností jiných induktivních pravidel. Zbytečné bázové prvky a zbytečná induktivní pravidla je možné z našich úvah dočasně vynechat, aniž bychom změnili množinu, s jejíž definicí pracujeme. Na rozdíl od bázových prvků může být explicitní vyjádření a důkaz toho, že induktivní pravidlo je zbytečné, poměrně komplikované. Často je lepší se spolehnout na intuitivní odhad a korektnost odhadu ověřit až při důkazu rovnosti množin. Připomeňme, že se jedná o „virtuální" úpravy, které nám mají usnadnit nalezení explicitního vyjádření množiny. Důkazu korektnosti explicitního vyjádření se nevyhneme. Je také důležité, abyste při postupném označování bázových prvků a induktivních pravidel jako „zbytečných" neoznačili bázový prvek nebo induktivní pravidlo, které jste již dříve použili k označení jiného prvku nebo pravidla. Potom by se definovaná množina změnila. V naší induktivní definici je zbytečné induktivní pravidlo, které je určeno funkcí /3. Při vypisování nejsnáze odvoditelných prvků množiny M jej proto nebudeme uvažovat. Prvky jsme již upravili do tvaru, z nějž je dobře vidět jejich explicitní vyjádření. Systematicky prozkoumáváme všechny možnosti aplikací funkcí f\ a J2 podle celkového počtu jejich aplikací. OG M Og M OG M Og M 1 G M 2 G M OG M 1 G M 2 G M 3G M 0 = = 3 0 + 5 3 = = 3 1 + 5 5 = = 3 0 + 5 6 = = 3 2 + 5 8 = = 3 1 + 5 10 = = 3 0 + 5 9 = = 3 3 + 5 11 = = 3 2 + 5 13 = = 3 1 + 5 15 = = 3 0 + 5 Odtud již můžeme uhádnout, že M vyjádření množiny M správné. {3k + 5l I k,l G No}. Dokážeme, zeje toto explicitní 3 Označme Mi induktivně definovanou množinu a M2 = {3k + 5l \ k,l G No}. Musíme dokázat rovnost množin Mi = Mi- Nejprve dokažme, že Mi C Mi- Důkaz můžeme vést strukturální indukci, protože dokazujeme tvrzení \/x G Mi. x G Mi- Základní krok: x je bázový prvek Mi. Tedy x = 0 = 3-0 + 5-0g Mi- Indukční krok: pravidlo určené funkcí f\. Nechť pro x G Mi platí x G M2 (toto je indukční předpoklad). Musíme dokázat, že fi(x) = x+3 G M^. Z indukčního předpokladu víme, že x G M2, tedy x = 3k + 5l pro nějaká k, / G No- Potom x+ 3 = 3(k+ l) + 5/ G M2, což jsme měli dokázat. Indukční krok: pravidlo určené funkcí f2. Nechť pro x G Mi platí x G M2 (toto je indukční předpoklad). Musíme dokázat, že f2(2) = x+5 G M2. Z indukčního předpokladu víme, že x G M2, tedy x = 3k + 5l pro nějaká k, / G No- Potom x + 5 = 3fc + 5(/ + l) G M2, což jsme měli dokázat. Indukční krok: pravidlo určené funkcí f3. Nechť pro x,y G Mi platí x G M2 a y G M2 (toto je indukční předpoklad). Musíme dokázat, že fs(x,y) = xy G M2. Z indukčního předpokladu víme, že x G M2, tedy x = 3fci+5/i pro nějaká k\, l\ G No- Dále z indukčního předpokladu víme, že y E M2, tedy y = 3/c2 + 5/2 pro nějaká k2,h €= No- Potom xy = = (3fci + 5/i)(3fc2 + 5/2) = 3(3kik2 + Sfah + 5k2h) + 5(5/i/2) e M2, což jsme měli dokázat. Nyní dokažme, že M2 C Mi. Intuitivně je tvrzení zřejmé: nechť 3k + 5/ G M2 pro nějaká k, / G No- Potom 3k + 5/ G Mi, protože jej získáme fc-násobnou aplikací funkce f\ a /-násobnou aplikací funkce f2 na bázový prvek 0 G Mi. My však budeme pečliví a uvedeme formální důkaz. Dokazujeme tvrzení \/k G No- V/ G No- 3k + 5/ G Mi. Důkaz povedeme indukcí vzhledem k n = k + l. Základní krok: n = 0. Potom fc = i = 0a3H5í = 0e Mi, protože 0 je bázový prvek Mi. Indukční krok: k + / = n + 1. Rozlišíme dvě možnosti. Pokud k > 0, potom (fc — 1) + / = n a z indukčního předpokladu víme, že 3(k — 1) + + 5/ G Mi. Aplikací pravidla určeného funkcí f\ na 3(fc — 1) + 5/ dostáváme 3(k — 1) + + 5/ + 3 = 3fc + 5/ G Mi, což jsme měli dokázat. Pokud / > 0, potom k + (l — 1) = n a z indukčního předpokladu víme, že 3k + 5(/ — — 1) G Mi. Aplikací pravidla určeného funkcí f2 na 3k + 5(/ — 1) dostáváme 3k + 5(/ — — 1) + 5 = 3k + 5/ G Mi, což jsme měli dokázat. d) Definice jednoznačná není. Jako protipříklad uvedeme jiné odvození 17 G M, než které jsme uvedli výše. 0 G M O) bázový prvek M 3 G M (u) z (i) a funkce f\ 8 G M (iii) z (ii) a funkce f2 11 G M (iv) z (iii) a funkce f\ 14 G M (v) z (iv) a funkce f\ 17 G M (vi) z (v) a funkce f\ e) Přirozeným jazykem řečeno se zajímáme o to, zda od nějakého přirozeného čísla jsou všechna větší přirozená čísla prvkem množiny M. Pokud tvrzení platí, nejsnazší způsob, 4 jak jej dokázat, může spočívat v nalezení onoho čísla m a důkazu, že \/n E No- m < < n => n E M pro naše konkrétní m. Pokud tvrzení neplatí, nejsnazší způsob, jak jej dokázat, může spočívat ve stanovení předpisu, který ke každému přirozenému číslu m stanoví větší přirozené číslo n, které není prvkem M. Tvrzení platí. Dokážeme, že každé přirozené číslo větší než nějaké určité přirozené číslo můžeme vyjádřit ve tvaru 3k + 5/, kde k,l E No- Nejprve ukážeme, jak ve tvaru 3k + 5/ vyjádřit čísla od 20 do 24 včetně. 4 0 2 4 0 Nechť n E No, n > 20. Nechť n = 5q + r, kde q, r E No, 0 < r < 5. (Tj. r je zbytek z n po dělení číslem 5.) Protože n > 20, platí q > 4. Potom n = 5(q — 4) + (20 + r), kde 20 < 20 + r < 24, takže platí 20 + r = 3k + 5/, kde k a / je určeno výše uvedenou tabulkou. Celkem dostáváme n = 5(q — 4) + 3k + 5/ = 3k + 5(/ + q — 4) E M. Tvrzení tedy platí, protože jsme dokázali, že za m můžeme položit například číslo 20. 20 = 3 0 + 5- 21 = 3 7 + 5- 22 = 3 4 + 5- 23 = 3 1 + 5- 24 = 3 8 + 5- Příklad 3. Uvažujme induktivně definovanou množinu M C No • 0 E M, 1 E M • jestliže x E M, potom 2x E M Tato induktivní definice je zřejmě jednoznačná, takže funkce / : M určena následující induktivní definicí No je korektně /(0) = /(2s) 0 a) Ukažte všechny kroky výpočtu hodnoty 7(256) podle této induktivní definice. b) Ukažte všechny kroky výpočtu hodnoty /(l92) podle této induktivní definice. c) Množinu M zapište explicitně. d) S využitím explicitního vyjádření prvků množiny M zapište explicitně i funkci /, tj. pro každé n E M stanovte hodnotu f (n). Řešení a) Hodnota f (m) je definována induktivně v závislosti na struktuře prvku m E M. Jedná se tedy o analogii funkcí T a Q pro normalizaci formulí výrokové a predikátové logiky. Výpočet proto bude také analogický. Rozdíl je pouze v tom, že u formulí byla struktura zřejmá z jejich zápisu. U čísel budeme muset jejich strukturu hledat. Jednoznačnost induktivní definice množiny M zajišťuje že bude vždy existovat právě jedna možnost, jak číslo rozložit na strukturálně jednodušší čísla. /(256) = /(2 • 128) = /(128) + 1 = /(2 • 64) = (/(64) + 1) + 1 = (/(2 • 32) + 1) + 1 = ((/(32) + 1) + 1) + 1 = ((/(2 • 16) + 1) + 1) + 1 5 = (((/(16) + 1) + 1) + 1) + 1 = (((/(2 • 8) + 1) + 1) + 1) + 1 = ((((/(8) + 1) + 1) + 1) + 1) + 1 = ((((/(2 • 4) + 1) + 1) + 1) + 1) + 1 = (((((/(4) + 1) + 1) + 1) + 1) + 1) + 1 = (((((/(2 ■ 2) + 1) + 1) + 1) + 1) + 1) + 1 = ((((((/(2) + 1) + 1) + 1) + 1) + 1) + 1) + 1 = ((((((/(2 - 1) + 1) + 1) + 1) + 1) + 1) + 1) + 1 = (((((((/(l) + l) + l) + l) + l) + l) + l) + l) + l = (((((((0 + l) + l) + l) + l) + l) + l) + l) + l = 8 b) Zadání v tomto případě samozřejmě nemá smysl, protože 192 ^ M a funkce / pro něj není definována. Pokud byste se pokusili o výpočet, dostali byste /(192) = /(2-96) = /(96) + 1 = /(2 • 48) + 1 = (/(48) + 1) + 1 = (/(2 • 24) + 1) + 1 = ((/(24) + 1) + 1) + 1 = ((/(2 • 12) + 1) + 1) + 1 = (((/(12) + 1) + 1) + 1) + 1 = (((/(2 • 6) + 1) + 1) + 1) + 1 = ((((/(6) + 1) + 1) + 1) + 1) + 1 = ((((/(2 • 3) + 1) + 1) + 1) + 1) + 1 = ((((/(3) + 1) + 1) + 1) + 1) + 1 Není jasné, jak pokračovat s výpočtem /(3), protože číslo 3 není ani bázový prvek M, ani jej není možné rozložit na strukturálně jednodušší prvky M. c) Opět vypíšeme několik prvních prvků množiny M. Oe M 1 = 2° G M 2 1 = 2ľ e M 2 2 1 = 22 G M 2-2 2 1 = 23 G M 2-2 2 1 = 24 G M Je vidět, že kromě čísla 0 budou všechny prvky množiny M tvaru 2l pro nějaké přirozené číslo i. Platí tedy M = {0}U{2Í | i G No}. Důkaz ponecháváme čtenáři. d) Indukcí vzhledem k i by bylo snadné dokázat, že f(2l) = i platí pro všechna i G No-Pokud to spojíme s tím, že hodnota /(O) není definována, můžeme hodnotu f(n) pro libovolné n E M explicitně zapsat takto: f(n) = f-L P°kud™ = °. ' y% pokud n = 2l pro nějaké i G No Musíme upozornit na to, že jsme se zde dopustili malé nepřesnosti. Vzhledem k tomu, že jsme / definovali jako parciální funkci, aby odpovídala logaritmu na přirozených číslech s nulou, nestačí ke korektnosti její induktivní definice, aby byla induktivní definice množiny M jednoznačná. Využili jsme i toho, že z bázového prvku 0 nelze odvodit žádný jiný prvek M. Jinak bychom museli říct, co znamená například _L + 1. 6 Příklad 4. Množinu No C No definujme následující induktivní definicí: • 0 G No • jestliže n G No, potom n + 1 G No Induktivně definujte funkce a)/ b)/ c)/ d)/ No^No, f(n) = n + 3 No^No, f(n) = n2 + 3n^ No ^ No, /(ra) = 2«+1 - 1 No —► {sudé, liché} f(n) f sudé pokud n je sudé \ liché jinak Řešení Nechť je úkolem explicitně zadanou funkci / : A —► B definovat induktivně, pokud je množina A zadána jednoznačnou induktivní definicí. Pro základní krok definice / stačí podle explicitního zadání / vypočítat její hodnotu pro bázové prvky z induktivní definice A. Nechť je induktivní pravidlo definice A určeno funkcí g : An —► A. Induktivní pravidlo definice / odpovídající tomuto pravidlu definice A můžeme určit tak, že pomocí explicitního zadání funkce / se pokusíme upravit f(g(x\,...,xn)) na h(f(x\),..., f(xn)). Hodnotu f(g(xi,... ,xn)) tedy vyjádříme v závislosti na hodnotách funkce / aplikované na strukturálně jednodušší prvky A. To může být velmi obtížné, nebo to nemusí být vůbec možné. Induktivní definice množiny No obsahuje jediný bázový prvek a jediné induktivní pravidlo. Podle výše uvedeného postupu tedy vždy nejprve provedeme dva výpočty (pro bázový a induktivní krok definice /) a potom zapíšeme induktivní definici funkce /. a) Výpočty: /(O) =0 + 3 = 3 f(n + 1) = (n + 1) + 3 = (n + 3) + 1 = f(n) + 1 Induktivní definice /: • /(O) = 3 . f(n + l) = f(n) + l b) Výpočty: /(O) = O2 + 3 • 0 + 1 = 1 f(n + 1) = (n + l)2 + 3(n + 1) + 1 = n2 + 3n + 1 + 2n + 4 = f(n) + 2n + 4 Induktivní definice /: • /(O) = 1 f(n + 1) = f(n) + 2n + A Použití n v induktivním kroku definice / je možné, protože se jedná o funkci, jejíž definiční obor je totožný s oborem hodnot. U obecné funkce / : A —► B by to samozřejmě možné nebylo. 7 c) Výpočty: /(O) = 20+1 -1 = 1 f (n + 1) = 2x C M je množina bázových prvků definice X a nechť By C M je množina bázových prvků definice Y. Nechť definice X a. Y mají společné funkce induktivních pravidel /i,...,/n. Nechť má induktivně definovaná množina S C M množinu bázových prvků Bx H By a funkce induktivních pravidel fi,... , fn. Nechť má induktivně definovaná množina T C M množinu bázových prvků Bx U By a funkce induktivních pravidel fi,... , fn. a) Rozhodněte, zda je množina S definována jednoznačně. Své tvrzení dokažte. b) Rozhodněte, zda je množina T definována jednoznačně. Své tvrzení dokažte. c) Rozhodněte, zda platí S = X n Y a své tvrzení dokažte. Co můžeme na základě tohoto výsledku říct o případě, v němž bychom nepožadovali, aby definice množin X a Y byly jednoznačné? d) Rozhodněte, zda platí T = X U Y a své tvrzení dokažte. Co můžeme na základě tohoto výsledku říct o případě, v němž bychom nepožadovali, aby definice množin X a Y byly jednoznačné? Příklad 10. Y závěrečném příkladě této sady se seznámíte s obecnějším pojetím induktivních definic, kdy je navzájem provázána definice více množin, resp. funkcí. U funkcí jste se s tím už v omezené míře setkali. Definice funkcí T a Q, které převádějí logické formule do normálního tvaru, jsou také provázány, ale obě funkce mají stejný definiční obor. Nechť jsou množiny A,B,C C {0,1, 2, 3, 4, 5, 6, 7, 8, 9, (,),*, +}* definovány induktivně takto (všimněte si typografického vyznačení, že se jedná o symboly, z nichž budeme vytvářet slova, nikoliv o čísla a operace s nimi): • {0,1,2,3,4,5,6,7,8,9} C A • jestliže t E C, potom (í) E A • AGB • jestliže x E B a y E A, potom x*y E B 10 • BC C • jestliže x E B a y E C, potom x+y E C Nechť X = {0,1,2, 3, 4, 5, 6, 7, 8, 9, T, P}. Nechť u, v E X*. Zřetězení slov u a v budeme značit u . v, pokud by zápis uv vedl k nejasnostem. Uvažme funkce Ma : A —► X*, Mb : B —► X* a Mc : C —► X* definované induktivně takto: • MA{k) = k pro k E {0,1, 2,3, 4, 5, 6,7, 8, 9} • MA(U)) = Mc(t) • Mg (í) = MA(t) pro ŕ G A • Mß(x*y) = Mß(x) . MA(y) . T • Mc(t) = M b (t) wot E B • Mc(x+y) = M b (x) . M (C) . P a) Rozhodněte, zda platí 8+9 G C, (8+9) G C, 4+15+0 G C, 3+2 G A, (3+2+4*7) G A, 3*(2+2) G S, 3*2+2 G S, (3*2)+2 G S, 3*2+2 G C. b) Ukažte všechny kroky výpočtu Mc(l+2+3+4*5*6*7*8). c) Ukažte všechny kroky výpočtu Mc(l*(2+3*4+5*6)*7+8*9). d) Umíte říct, co je množina C a co počítá funkce Mc? 11