5   Rekurze, Strukturální indukce
Mimo „přímočarých" definic množin a funkcí, jako výčtem prvků či explicitním zadáním, se obzvláště v informatice setkáváme s definicemi nepřímými, které se odvolávají na sebe sama.
Odborně se taková situace nazývá rekurzí a induktivní definicí. □
Stručný přehled lekce
* Posloupnosti a rekurentní vztahy, jejich řešení.
* Induktivní definice množin a funkcí, použití strukturální indukce.
* Nazpět k matematické logice:
sémantika výrokové logiky a formální převod do normálního tvaru.
Petr Hliněný, Fl MU Brno, 2018
1/21
Fl: IB000: Strukturální indukce
5.1   Posloupnosti a rekurentní vztahy
• Uspořádané fc-tice z daného oboru hodnot H jsou nazývány konečnými posloupnostmi délky k (nad H).
• Pojem posloupnosti zobecňuje toto pojetí na „nekonečnou délku" takto:
Definice 5.1. Posloupnost (nekonečná) je zobrazením z přirozených čísel N do oboru hodnot H, neboli
p : N -> H.
Místo „funkčního" zápisu n-tého členu posloupnosti jako p(n) častěji používáme „indexovou" formu jako pn, ve které se celá posloupnost zapíše (pn)neN-c
Oborem hodnot H posloupnosti obvykle bývá nějaká číselná množina, ale může to být i jakákoliv jiná množina. □
Poznámka: Třebaže to není zcela formálně přesné, běžně se setkáme s posloupnostmi
indexovanými od nuly nebo od jedničky, jak se to v aplikacích hodí.
I my se budeme tímto řídit a vždy si určíme počáteční index podle potřeby.
Petr Hliněný, Fl MU Brno, 2018
2/21
Fl: IB000: Strukturální indukce
Příklady posloupností
• po — 0, pi = 2,... ,pi = 2i,... je posloupnost sudých nezáporných čísel,c
• (3, 3.1, 3.14, 3.141,...) je posl. postupných dekadických rozvojů 7r,c
• třeba (jablko, hruška, švestka, hruška, hruška,...) je posloupnost nad druhy ovoce coby oborem hodnot.c
• (1, —1, 1, —1,...) je posloupnost určená vztahem pi = (—l)z, i > 0,
• avšak pokud bychom chtěli stejnou posloupnost (1, —1, 1, —1,...) určit indexy od jedné, tj. zadat ji jako g^, i > 1, tak vztah bude qi — (—1)2_1.
Definice: Posloupnost (pn)ne^ Je
* rostoucí pokud pn+i > Pn a nerostoucí pokud pn+i ^ Pn>
* klesající pokud pn+i < Pn a neklesající pokud pn+i > Pn
platí pro všechna n.
Petr Hliněný, Fl MU Brno, 2018
3/21
Fl: IB000: Strukturální indukce
Rekurentní zadání posloupnosti
Definice: Říkáme, že posloupnost (pn)n^ je zadána rekurentně, pokud je dán její počáteční člen po (či několik počátečních členů) a dále máme předpis, jak určit hodnotu členu        z hodnot     pro nějaká i < n.
Ukázky rekurentně zadaných posloupností:
• Zadáme-li posloupnost pn počátečním členem po = 1 a rekurentním vztahem        = 2pn pro n > 0, pak platí pn = 2n pro všechna n.
• Funkce „faktoriál" (na přirozených číslech) je dána počáteční hodnotou 0! = 1 a rekurentním vztahem (n + 1)! = (n + 1) • n\ pro n > 0.
• Známá Fibonacciho posloupnost je zadaná počátečními členy f1 = f2 = l a vztahem fn+2 = fn+i + fn pro n > 1. □
Všimněte si v poslední ukázce, že není potřeba doslova dodržovat formu rekurentního vztahu „pn+i z hodnot p^", ale vždy je třeba hodnotu následujícího členu posloupnosti odvozovat z předchozích (tj. už určených) členů, v tom případě z hodnot     i = n, n + 1".
Petr Hliněný, Fl MU Brno, 2018
4/21
Fl: IB000: Strukturální indukce
■f-
Řešení rekurentní posloupnosti
Příklad 5.2. Posloupnost f : N —> 7L je zadaná rekurentní definicí
/(O) =3    a    /(n + l)=2-/(n) + l
pro všechna přirozená n. Určete hodnotu f(n) vzorcem v závislosti na n.
Řešení: V první fázi řešení takového příkladu musíme nějak „uhodnout" hledaný vzorec pro f(n). Jak? Zkusíme vypočítat několik prvních hodnot a uvidíme...
/(I) = 2./(0) + l = 2.3 + l = 7
f (2) = 2-/(1)+ 1 = 2-7 + 1 = 15
/(3) = 2-/(2)+ 1 = 2-15 + 1 = 31
/(4) = 2 • /(3) + 1 = 2 • 31 + 1 = 63
Nepřipomínají nám tato čísla něco? Co třeba výrazy 8 — 1, 16 — 1, 32 — 1, 64 — 1... ? Bystrému čtenáři se již asi podařilo uhodnout, že půjde o mocniny dvou snížené o 1. Přesněji, f(n) = 2n+2 - 1. □
Ve druhé fázi nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n. □
Petr Hliněný, Fl MU Brno, 2018
5/21
Fl: IB000: Strukturální indukce
Příklad 5.2. Posloupnost f : N —>> 7L je zadaná rekurentní definicí
/(O) =3    a    /(n + l)=2-/(n) + l
pro všechna přirozená n. Určete hodnotu f(n) vzorcem v závislosti na n. Řešení: ...
Bystrému čtenáři se již asi podařilo uhodnout, že půjde o mocniny dvou snížené o 1. Přesněji, f(n) = 2n+2 - 1.
Ve druhé fázi nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n.
• Báze pro n := 0 říká /(O) = 2°+2 -1=4-1 = 3 = /(O), což platí. □
• Indukční krok využije indukční předpoklad platnosti vztahu f(n) = 2n+2 — 1 pro n := i (tj. f (i) = 22+2 — 1) a pokračuje úpravou ze zadaného rekurentního vzorce
f (i + 1) = 2 • /(i) + 1 = 2- (2i+2 - 1) + 1 = 2 • 2i+2 - 2 + 1 = 2(i+1)+2 - 1, což po dosazení pro n := i + 1 znamená opět požadovaný vztah /(n) = 2n+2 — lx
Podle principu matematické indukce je nyní dokázáno, že pro zadanou rekurentní posloupnost / platí f(n) = 2n+2 — 1 pro všechna přirozená n. □
Petr Hliněný, Fl MU Brno, 2018
6/21
Fl: IB000: Strukturální indukce
Příklad 5.3. Posloupnost (sn)neN je zadaná rekurentní definicí
so = O    a    sn = sn-i + n2 pro všechna n > 1. n Dokažte, že sn = |n(n + l)(2n + 1) pro všechna přirozená n.
Řešení: Opět postupujeme matematickou indukcí podle n.
• Báze n := 0: s0 = ± • 0 • (0 + 1)(2 • 0 + 1) = 0, což platí. □
• Indukční krok: za využití Sí-i = \ {i — l)(i — 1 + l)(2z — 2 +1) = |(i — l)i(2i — 1), což je indukční předpoklad pro n := i -  1 a libovolné i > 1, upravujeme
1 1
= sí-i + i2 = -(i - l)i(2i - 1) + i2 = -i (2i2 - 3i + 1) + i2
= U (2i2 - 3i + 1 + 6i) =       + l)(2i + 1), což dokazuje požadovaný vztah sn = \n(n + l)(2n + 1) také pro n := i.
□
Poznámka: Výsledek Příkladu 5.3 je ukázkou tzv. sumačního vzorce pro řadu
l
l2 + 22 + • • • + n2 = -n(n + l)(2n + 1).
6
Jinou ukázkou je už dříve zmíněný základní vztah 1 + 2 + • • • + n = ^n(n + 1).
Petr Hliněný, Fl MU Brno, 2018
7/21
Fl: IB000: Strukturální indukce
5.2   Induktivní definice množin a funkcí
Přímým zobecněním rekurentních definic posloupností je následující koncept. Definice 5.4. Induktivní definice množiny.
Jedná se obecně o popis (nějaké) množiny M v následujícím tvaru:
• Je dáno několik pevných {bázických) prvků ai, a2,..., a& £ M.
• Je dán soubor induktivních pravidel typu
Jsou-li (libovolné prvky) xi,... ,xt £ M, pak také y £ M. V tomto případě je y typicky funkcí y = fi(xi,..., xt).
Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující všem těmto pravidlům.
Petr Hliněný, Fl MU Brno, 2018
8/21
Fl: IB000: Strukturální indukce
■r
Několik ukázek. ..
• Pro nejbližší příklad induktivní definice se obrátíme na množinu všech přirozených čísel, která je formálně zavedena následovně.
- 0 G N
- Je-li i G N, pak také succ{i) G N (kde následník succ{i) odpovídá
Pro každé y E N můžeme definovat jinou množinu My C N induktivně:
- y e My
- Jestliže x G My a x + 1 je liché, pak x + 2 G My. □ Pak například M3 = {3}, nebo M4 = {4 + 2i \ i G N}. □
Dalším příkladem induktivní definice je už známé zavedení výrokových formulí z Oddílu 1.4. Uměli byste teď přesně říci, co tam byly bázické prvky a jaká byla induktivní pravidla? A jaká byla v definici formulí role závorek?
Petr Hliněný, Fl MU Brno, 2018
9/21
Fl: IB000: Strukturální indukce
Jednoznačnost induktivních definic
Definice: Řekneme, že daná induktivní definice množiny M je jednoznačná, právě když každý prvek M lze odvodit z bázických prvků pomocí induktivních pravidel právě jedním způsobem.
• Definujme například množinu M C N induktivně takto:
- 2,3 G M
- Jestliže x, y G M a x < y, pak také x2 + y2 a x • y jsou prvky M. Proč tato induktivní definice není jednoznačná? nNapříklad číslo 8 G M lze odvodit způsobem 8 = 2 • (2 • 2), ale zároveň zcela jinak 8 = 22 + 22.
• V čem tedy spočívá důležitost jednoznačných induktivních definic množin? Je to především v dalším možném využití induktivní definice množiny jako „základny" pro odvozené vyšší definice, viz následující.
Petr Hliněný, Fl MU Brno, 2018
10/21
Fl: IB000: Strukturální indukce
Definice 5.5. Induktivní definice funkce z induktivní množiny. Nechť množina M je dána jednoznačnou induktivní definicí. Pak říkáme, že funkce T : M       X je definována induktivně (vzhledem k induktivní definici M), pokud je řečeno:
• Pro každý z bázických prvků ai, 0,2,...,    G M je určeno F{ai) — q.
• Pro každé induktivní pravidlo typu
"Jsou-li (libovolné prvky) xi,..., x£ G M, pak také /(xi,..., a^) G M" je definováno
^( / (#1? • • • 5 ^)) na základě hodnot T(x\),..., T{xt)^
Ilustrujme si induktivní definici funkce dětskou hrou na „tichou poštu". Definičním oborem je řada sedících hráčů, kde ten první je bázickým prvkem a každý následující (mimo posledního) odvozuje hráče sedícího hned za ním jako další prvek hry.
Hodnotou bázického prvku je první (vymyšlené) posílané slovo. Induktivní pravidlo pak následujícímu hráči přiřazuje slovo, které je odvozeno („zkomolením") ze slova předchozího hráče. Výsledkem hry pak je hodnota-slovo posledního hráče.
Petr Hliněný, Fl MU Brno, 2018
11/21
Fl: IB000: Strukturální indukce
■r
Pro další příklad se podívejme třeba do manuálu unixového příkazu test
No, problematická je otázka jednoznačnosti této definice - jednoznačnost není vynucena (jen umožněna) syntaktickými pravidly, jinak je pak dána nepsanými konvencemi implementace příkazu.
To je pochopitelně z matematického hlediska špatně, ale přesto jde o pěknou ukázku z praktického života informatika.
EXPRESSION:
EXPRESSION is true or false ( EXPRESSION ) ! EXPRESSION
EXPRESSI0N1 -a EXPRESSI0N2 EXPRESSI0N1 -o EXPRESSI0N2 [-n] STRING STRING1 = STRING2
and sets exit status.    It is one of: EXPRESSION is true EXPRESSION is false
both EXPRESSI0N1 and EXPRESSI0N2 are true either EXPRESSI0N1 or EXPRESSI0N2 is true the length of STRING is nonzero the strings are equal
□
Petr Hliněný, Fl MU Brno, 2018
12/21
Fl: IB000: Strukturální indukce
5.3   Použití strukturální indukce
Příklad 5.6. Jednoduché aritmetické výrazy a jejich význam.
Nechť je dána abeceda E = {0,1, 2, 3,4, 5, 6, 7,8,9, 0, 0, (,)}. Definujme množinu jednoduchých výrazů SExp C E* induktivně takto:
* Dekadický zápis každého přirozeného čísla n je prvkem SExp (bázické prvky).
* Jestliže x,y £ SExp, pak také (x) 0 (y) a (x) 0 (y) jsou prvky SExp.
* Jak snadno nahlédneme, díky nucenému závorkování je tato induktivní definice jednoduchých výrazů SExp jednoznačná.
Tímto jsme aritmetickým výrazům přiřadili jejich „formu", tedy syntaxi.
Pro přiřazení „významu", tj. sémantiky aritmetického výrazu, následně definujme funkci vyhodnocení Val: SExp —> N induktivně takto:
* Pro bázické prvky: Va/(n) = n, kde n je dekadický zápis přirozeného čísla n.
* První induktivní pravidlo: Val((x) 0 (y)) = Val(x) + Val(y).
* Druhé induktivní pravidlo: Val((x) 0 (y)) = Val(x) • Val(y).
Co je pak „správným významem" (hodnotou) uvedených aritmetických výrazů? □
Petr Hliněný, Fl MU Brno, 2018
13/21
Fl: IB000: Strukturální indukce
Příklad 5.7. Důkaz správnosti přiřazeného „významu" Val: SExp —)► N.
Věta. Pro každý výraz <j £ SExp je hodnota Val(cr) číselně rovna výsledku vyhodnocení výrazu <j podle běžných zvyklostí aritmetiky.^
Jelikož pojednáváme o induktivně definované funkci Val, je přirozené pro důkaz jejích vlastností aplikovat matematickou indukci. Avšak na rozdíl od dříve probíraných příkladů zde nevidíme žádný celočíselný „parametr n", a proto si jej budeme muset nejprve definovat podle struktury výrazu <j.
Přesněji, naši indukci povedeme podle „délky i odvození výrazu <r" definované jako počet aplikací induktivních pravidel potřebných k odvození <j £ SExp.
□
Důkaz: V bázi indukce ověříme vyhodnocení bazických prvků. Platí Va/(n) = n, což skutečně odpovídá zvyklostem aritmetiky.
V indukčním kroku se podíváme na vyhodnocení Val((x) 0 (y)) = Val(x) + Val(y). Podle běžných zvyklostí aritmetiky by hodnota Val((x) 0 (y)) měla být rovna součtu vyhodnocení výrazu x, což je podle indukčního předpokladu rovno Val(x) [x má zřejmě kratší délku odvození), a vyhodnocení výrazu y, což je podle indukčního předpokladu rovno Val(y). nTakže skutečně Val((x) 0 (y)) = Val(x) + Val(y).
Druhé pravidlo Val((x) 0 (y)) se dořeší analogicky. n
Petr Hliněný, Fl MU Brno, 2018
14/21
Fl: IB000: Strukturální indukce
5.4   Nazpět k matematické logice
Vybaveni aparátem induktivních definic, můžeme nyní podat matematicky přesnější definici formulí výrokové logiky z Oddílu 1.4 a jejich sémantiky.
Definice: Nechť V — {A, £>,C,...} je množina výrokových proměnných. Množina ^výrokových formulí je dána těmito pravidly induktivní definice:
* Bázickými prvky T jsou proměnné V, tj. X G J- pro každé X G V.
* {negace) Je-li (p G J7, pak také        je prvkem .F.c
* (implikace) Je-li 92,^ G J7, pak také (^) je prvkem .F.c
Zároveň platí, že závorky okolo (p lze vynechat pouze pokud (p G V nebo <^ bylo vytvořeno induktivním pravidlem negace. To stejné platí pro vynechávání závorek okolo ^.
Poznámka: Již nad rámec předchozí definice patří dříve uvedené syntaktické zkratky
* (p\/ifj    (disjunkce / „nebo") je jiný zápis formule =^> ip,
* cpAip    (konjunkce/„a") je jiný zápis formule —>(—V ~'V7)-
* cp     ip    (ekvivalence) je jiný zápis formule    (cp =^> ip) A (ip =^> cp).
Petr Hliněný, Fl MU Brno, 2018
15/21
Fl: IB000: Strukturální indukce
Sémantika výrokové logiky
Na základě jednoznačné induktivní definice množiny J7 výrokových formulí nyní můžeme podat přesnou induktivní definici funkce vyhodnocení (logické hodnoty formulí). Nechť valuace (ohodnocení) je funkce v : V —>> {0,1}.
Definice 5.8. Sémantika (význam) výrokové logiky. Pro každou valuaci v definujeme funkci
Sv\ .F->{0,1},
zvanou vyhodnocení formule a vzhledek k v, ninduktivně takto:
• SV{X) := v{X) pro každé IeP.
o í    \ 1   jestliže Sv(ld) — 0;
# S"(^ := \ 0 jinak.
. SJ<p     M := í ?  JeSt!ÍŽe SÁif) = 1 3 SvW = °; V7^      ^y 1 jinak.
Petr Hliněný, Fl MU Brno, 2018
16/21
Fl: IB000: Strukturální indukce
Převod formulí do normálního tvaru
V dalším se vrátíme k logickým formulím v normálním tvaru (viz Oddíl 2.2), tedy k formulím, ve kterých se negace vztahuje pouze k výrokovým proměnným.
Tvrzení 5.9. Každou výrokovou formuli lze převést do normálního tvaru, pokud k     povolíme i užívání odvozených spojek a a v.
• Pro ilustraci, k formuli ~^(A =^> B) je ekvivalentní normální tvar A a -iB,
• k formuli -.(C a (-^4     B)) je ekvivalentní -.C v (-^4 a -.B), □
• k formuli -.((A => B)     C) je ekvivalentní (A    B) a -iC.
Petr Hliněný, Fl MU Brno, 2018
17/21
Fl: IB000: Strukturální indukce
■r
Metoda 5.10. Převod formule p do normálního tvaru ÍF{p)-Používáme T{X) jako „je pravda, že X" a Q{X) jako „nenípravda, že X".
T{A) =   A G{A) = -iA
H-v)     = g{p) g (-v) =
rivAý) = %)aj(^) g(<pAii>) = g{y)vg{ip) ^vv)  = %)vj(^)      £(<ŕ>vv)  = g{y)f\g{ip)
Hv&tí) = Hv)<*H-<l>)      G(v&ý) = (^)aW))v(%)ajW)o
Pro predikátové formule toto rozšíříme ještě o pravidla:
j-~(\/x. (p) = \/x. g (yx. <p) = 3x. g (p)
J-~(3x. p)   =   3x. ÍF{p) g(3x.p)   = \/x.g(p)c
Uvažme formuli -*(A => ~^{B v —'(C => -*Ä))). Užitím uvedeného postupu získáme:
F(-,(A =>->(B V->(C =>-.A)))) = G (A => ->(B v -i(C => ->A))) =□
ÍF(Ä) A g(^(B v -i(C => -*Ä))) = A A F(B v -i(C => -<Á)) =□
A a (F(B) v J7(-i(C => -*Ä))) = A A (B V g (C => ~<A)) =□
A A (B V (F(C) A g(^A))) = A A (B v (C a T(A))) =□ A A (B V (C A A))
Petr Hliněný, Fl MU Brno, 2018
18/21
Fl: IB000: Strukturální indukce
Důkaz pro normální tvar formule
Na závěr následuje další ilustrativní ukázka důkazu strukturální indukcí.
Věta 5.11. Pro libovolnou výrokovou formuli (p platí (viz Metoda 5.10), že
a) J~((f) je formule v normálním tvaru ekvivalentní k (p
b) a G(ip) je formule v normálním tvaru ekvivalentní negaci -op.
Důkaz povedeme indukcí ke struktuře formule, neboli indukci povedeme podle „délky" i - počtu aplikací induktivních pravidel při sestavování formule (p.
• Báze indukce (í — 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě platí, že T{Ä) — A je ekvivalentní A a G(Á) = -^A je ekvivalentní ->A
• V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule (p délky nejvýše £. Vezmeme si formuli i/; délky £ + 1, která je utvořená jedním z následujících způsobů:
Petr Hliněný, Fl MU Brno, 2018
19/21
Fl: IB000: Strukturální indukce
ý = -.<£.
Podle výše uvedeného induktivního předpisu je J7^) = J7^^) — G(<p)-Podle indukčního předpokladu pak je G(ip) formule v normálním tvaru ekvivalentní -op = ý.
Obdobně pro funktor Q vyjádříme G{^) — Gi^p) = J7^). Podle indukčního předpokladu pak je J~((f) formule v normálním tvaru ekvivalentní (f a to je dále ekvivalentní -i-i<^ = -i^ podle Tvrzení 1.11.
* ý = (<^i ip2).
Podle výše uvedeného induktivního předpisu je J7^) = ^{tpi     ^2) = ^(^1)      Jr((fi2)- Podle indukčního předpokladu jsou ^(^1) i ^(^2) formule v normálním tvaru ekvivalentní      a <^2- Potom i J-^i) J-((f2) je v normálním tvaru dle definice a podle sémantiky     je ta ekvivalentní formuli ((fi     (^2) = V7-
Obdobně rozepíšeme G(ip) = G(<Pi ^2) = ^(^í) ^G(<P2)- Jelikož A je pro nás jen zkratka, výraz dále rozepíšeme G{^) — _,(^r(^i) -ič/((^2))- Podle indukčního předpokladu (a dvojí negace) jsou J7((fi) a ~^G(ip2) P° řadě ekvivalentní formulím (fi a <^2- Tudíž nakonec odvodíme, že G(i/>) je ekvivalentní negaci formule tpi (^2, což jsme zde měli dokázat.
Petr Hliněný, Fl MU Brno, 2018
20/21
Fl: IB000: Strukturální indukce
* ý = {ifi V ip2).
Zde si musíme opět uvědomit, že spojka V je pro nás jen zkratka, a přepsat ^ = (-^pi ^2)- Potom podle předchozích dokázaných případů víme, že Jr(^) = F(~^(pi ^2) — ^r(_,(^i) =^ ^{^2) je ekvivalentní formuli (-"(^í (^2) — V7- c°ž bylo třeba dokázat. Stejně tak = (/("^í ^2) = ^r(_,(^i) A ^((^2) je podle předchozích případů důkazu ekvivalentní        A -"(^2) —
* ^ = ((^! A (^2) a ^ = (<^i     ^2) už dokončíme analogicky.
Petr Hliněný, Fl MU Brno, 2018
21/21
Fl: IB000: Strukturální indukce