IBOOO Úvod do informatiky — príklady na procvičení Sada 9 — Zadání 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. 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 E N0. \/n E N0. m < n ^ n E M a správnost svého rozhodnutí dokažte. Příklad 3. Uvažujme induktivně definovanou množinu M C No • 0 G M, 1 G M • jestliže x G M, potom 2x G M Tato induktivní definice je zřejmě jednoznačná, takže funkce / : M —► No je korektně určena následující induktivní definicí . /(O) = _L, /(l) = 0 . f(2x) = f(x) + 1 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). Příklad 4. Množinu No C No definujme následující induktivní definicí: • 0 G No • jestliže n E No, potom n + 1 E No Induktivně definujte funkce a)/ No- -+N0) /(n) = n + 3 b)/ No- -►No, f (n) = n2 + 3n- c)/ No- -> No, f (n) = 2n+1 - 1 d)/ No- -> {sudé, liché} /(«) f sudé pokud n je sudé \ liché jinak 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: • eeE* • jestliže w E T,*, 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ť u>i,u>2 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é slovo weE* vráti 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 MCE* 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 E*, potom xy E M • jestliže x,y E M a, x = ub a, y = bv pro nějaká u,v E E*, 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 = ai... an, kde a; G E pro každé i = 1,..., n, rozumíme slovo w = 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. 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 g\,..., 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 Z