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 + 4 e 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
O G M
OG M
O G 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 = MiNejprve
dokažme, že Mi C Mi- Důkaz můžeme vést strukturální indukci, protože
dokazujeme tvrzení \/x G Mi. x G MiZákladní
krok: x je bázový prvek Mi. Tedy X = 0 = 3 - 0 + 5 - 0 G MIIndukč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 = 0 a 3 H 5 í = 0 e 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 + 521
= 3 7 + 522
= 3 4 + 523
= 3 1 + 524
= 3 8 + 5Pří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 NoPokud
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
TM = °.
' 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 ) /
N o ^ N o , f(n) = n + 3
N o ^ N o , 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) = 2<n + 1
)+ 1
- 1 = 2- 2 n + 1
- 1 = 2(2n + 1
- 1) + 1 = 2f (n) + 1
Induktivní definice /:
/(O) = 1
. f(n + 1) = 2 ˇ /(n) + 1
d) Zde si výpočty odpustíme. Nula je jistě sudé číslo. Pokud k sudému číslu přičteme
jedničku, získáme číslo liché. Pokud naopak přičteme jedničku k lichému číslu, získáme
číslo sudé.
Induktivní definice / :
/(O) = sudé
1 liché jinak
p/ i i\ _ J sudé pokud f (n) = liché
Příklad 5.
Mějme množinu (abecedu) E = {a}. Konečným posloupnostem prvků (znaků) E budeme
pro stručnost říkat slova nad abecedou E. Prázdnou posloupnost (prázdné slovo, slovo
délky 0) budeme značit e. Uvědomte si, že e je metasymbol, zejména e ^ E. Množinu
E* C E* všech slov nad abecedou E definujme induktivně takto:
*  G E *
* jestliže W G E * , potom wa E E*.
Tato definice je jednoznačná. Všimněte si podobnosti této definice s induktivní definicí
množiny přirozených čísel. Induktivně definujme funkci / : E* --ˇ No, která bude počítat
délku slova nad abecedou E.
* 1(e) = 0
* l(wa) = l(w) + 1
Uvažujme funkci S : E* --ˇ E* definovanou induktivně takto:
* S(e) = a
S(wa) = S(w).aaa
Nechť w E E*. Pomocí funkce / charakterizujte, co počítá funkce S, tj. stanovte, co musí
splňovat u,v ET,*, aby platilo S(u) = v a své tvrzení dokažte (strukturální indukcí).
Příklad 6.
Nechť E je konečná množina symbolů.
a) Podejte jednoznačnou induktivní definici množiny E* všech konečných posloupností
symbolů z množiny E.
b) Nechť wi,W2 E E*. Definujte induktivně množinu všech slov nad abecedou E, která
obsahují podslovo w\ nebo W2- Strukturální indukcí dokažte, že je definice správně.
c) S využitím jednoznačné induktivní definice množiny E* z předchozí části tohoto
příkladu pro každé a G E induktivně definujte funkci # a : E* --ˇ No, která pro každé
8
slovo w e E * vrátí počet symbolů a ve slově w. Strukturální indukcí dokažte, že je funkce
definována správně.
Příklad 7.
Nechť E = {a,b,c}. Uvažujme množinu M C E * danou následující induktivní definicí
* ba, bc, cb, ab E M
* jestliže x,y E M a, x = au a, y = va pro nějaká u,v E T,*, potom xy E M
* jestliže x,y E M a, x = ub a, y = bv pro nějaká u,v E T,*, potom xy E M
a) Rozhodněte, zda abbacbba E M, cbbccbba E M, abbccbba E M, abbabccbabba E M.
Svá tvrzení zdůvodněte.
b) Reverzí slova w E T,*, w = a\... an, kde ai E E pro každé i = 1,..., n, rozumíme
slovo wR
= an ... a\. Například reverzí slova abbc je slovo cbba.
Strukturální indukcí dokažte, že pro každé w E M platí wR
E M, tj. že množina M je
uzavřená na reverzi slov.
Řešení
Pro stručnost budeme induktivní pravidla označovat jako pravidlo 1 a pravidlo 2
podle pořadí, v němž jsou uvedena.
a) Platí cbbccbba ^ M. Slovo mohlo vzniknout pouze použitím pravidla 2 a to dvěma
způsoby: cb.bccbba nebo cbbccb.ba. Slovo bccbba, resp. cbbccb mohlo opět vzniknout pouze
použitím pravidla 2 a to jediným způsobem: bccb.ba, resp. cb.bccb. Ovšem bccb ^ M, takže
neexistuje odvození slova cbbccbba.
Platí abbabccbabba ^ M. Zde je rozbor možností příliš pracný, než abychom jej zde
uváděli. Alternativně lze využít skutečnosti, že obě pravidla slova striktně prodlužují. Je
tedy snadné systematicky odvodit všechna slova délky 12 a přesvědčit se, že mezi nimi
slovo abbabccbabba není.
Platí abbacbba, abbccbba E M. Odvození obou slov provedeme zároveň.
ab E M O) bázový prvek M
ba E M (u) bázový prvek M
bc E M (iii) bázový prvek M
cb E M (iv) bázový prvek M
abba E M (v) z (i), (ii) a pravidla 1
abbc E M (vi) z (i), (iii) a pravidla 2
cbba E M (vii) z (iv), (ii) a pravidla 2
abbacbbaE M (viii) z (v), (vii) a pravidla 1
abbccbbaE M (ix) z (vi), (vii) a pravidla 1
b) Základní krok: ab. Platí (ab) = ba, což je bázový prvek a tedy (ab) E M.R
ab, což je bázový prvek a tedy (ba) E M.Základni krok: ba. Platí (ba)
Základni krok: bc. Platí (bc)R
= cb, což je bázový prvek a tedy (bc)R
E M.
Základní krok: cb. Platí (cb)R
= bc, což je bázový prvek a tedy (cb)R
E M.
Indukční krok: pravidlo 1. Nechť x, y E M, x = au a y = va pro nějaká u, v E T,*
= uR
.a E M a yR
= a.vR
E M. Proto
(a.vR
).(uR
.a) E M
Z indukčního předpokladu plyne, že také xR
(xy)R
= (auva)R
=
9
Indukční krok: pravidlo 2. Nechť x, y E M, x = ub a y = bv pro nějaká u, v E E*.
Z indukčního předpokladu plyne, že také x = b.u E M a y' = v .b E M. Proto
(xy)R
= (ubbv)R
= (vR
.b).(b.uR
) E M
Příklad 8.
Nechť M je množina. Nechť X, Y C M jsou induktivně definované množiny se společnou
množinou B C M bázových prvků, přičemž fi,... , fm jsou funkce induktivních pravidel
z definice X a gi,..., gn jsou funkce induktivních pravidel z definice Y.
Nechť má induktivně definovaná množina Z\ C M množinu bázových prvků X a funkce
induktivních pravidel g\,..., gn.
Nechť má induktivně definovaná množina Z2 C M množinu bázových prvků Y a funkce
induktivních pravidel / i , . . . , fm.
Rozhodněte, zda platí Z\ = Z2 a své tvrzení dokažte.
Příklad 9.
Nechť M je množina. Nechť X,Y C M jsou jednoznačně induktivně definované množiny.
Nechť >x 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) = MB (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