Princip úplné matematická indukce pro přirozená čísla (ÚMI)
Jde o metodu důkazu toho, že nějaké tvrzení T platí pro všechna přirozená čísla.
Tento princip říká:
Platí-li
(1) T(0) a
(2) Pro všechna n e N platí následující implikace: (Pro všechna k e N, k <n platí T (k))     T (n + 1),
potom pro každé n G N platí T (n).
ÚMI se samozřejmě dá formulovat různě. Například místo (1) a (2) můžeme mít:
(3) Pro všechna n e N platí následující implikace: (Pro všechna k G N, k < n platí T (k)) => T (n)
Původní (1) je zde "schována" v (3) při volbě n = 0.
Doporučuji se zamyslet: Proč tento princip platí?
Jaký je rozdíl mezí principem matematické indukce a principem úplné matematické indukce?
Platí tento princip i pro libovolnou jinou nekonečnou posloupnost? Co je potřeba změnit při důkazu, že T platí pro všechna kladná přirozená čísla?
1
Příklad 1 Dokažte, že slovo w = (A —>• B) V (C A D) není formulí výrokové logiky. Řešení
Nejprve zaveďme značení: Necht pro libovolné slovo x nad abecedou výrokové logiky značí z(x) počet závorek a b(x) počet binárních spojek ve slově x.
Dokážeme, že pro každou formuli p platí z(p) = 2 * b(p). Tím dokážeme, že w není formule, nebot pro w tato rovnost neplatí. Důkaz povedeme úplnou matematickou indukcí vzhledem k délce vytvořující posloupnosti. Dokážeme tedy, že pro každé n G N+ a každou formuli s vytvořující posloupností délky n platí daná rovnost. Rovnost proto platí pro každou formuli.
(1) Necht p je libovolná formule s vytvořující posloupností délky 1. Tedy p = A, kde A je výroková proměnná. Platí z(p) = 2 * b(p), nebot obě strany rovnice jsou 0.
(2) Necht ip je libovolná formule s vytvořující posloupností lpi, ip2, ipn-i, f kde n G N, n > 1 (n je tedy délka této vytvořující posloupnosti). Z definice formule víme, že ip má jeden z těchto tří tvarů:
(i) p = A, kde A je výroková proměnná nebo
(ii) p = —'ipi, kde 1 < i < n nebo
(iii) p = (lpi oipj), kde 1 < i < n, 1 < j < n, o je některá z binárních spojek. Pokud platí (i), pak z(p) =0 = 2* b(p).
Pokud platí (ii), pak z(p) = z(\pi), b(p) = b(\pi). ipi,ip2, -;ipi je vytvořující posloupnost formule lpi délky i < n. Z indukčního předpokladu: z(ipi) = 2 * b(\pi), proto i z(p) = 2 * b(p).
Pokud platí (iii), pak (*) z(p) = z(%pi)+z(%pj)+2 (závorky ve p jsou všechny ty v podformulích lpi a ipj, navíc dvě vnější). Podobně jako v předchozím případě, pro lpi a ipj existuje vytvořující posloupnost délky < n, a proto pro ně platí z indukčního předpokladu: z(ipi) = 2 * b(ipi) a z(ipj) = 2 * b(ipj). Tyto rovnosti dohromady s (*) dávají: z(p) = z(%pi) + z(%pj) + 2 = 2*b(ipi) + 2*(ipj) + 2 = 2 * (1 + b(%pi) + b(%pj)) = 2 * b(p) (binární spojky ve p jsou všechny ty v podformulích lpi a ipj, navíc jedna, která tyto podformule spojuje).
Dokázali jsme tedy, že pro každou formuli p platí rovnost z(p) = 2 * b(p). Pro slovo w tato rovnost neplatí, a proto není formulí. □
Všimněte si, co je jádrem důkazu. Je vlastně potřeba dokázat, že
(1) Formule A (kde A je libovolná výroková proměnná) má danou vlastnost.
(2) Pokud formule ip má danou vlastnost, pak i formule —tip má danou vlas-ntost.
(3) Pokud formule ip a p mají danou vlastnost, pak i formule (ip o p) má danou vlasntost, kde o je libovolná binární spojka (v našem jazyce výrokové logiky).
Tomuto typu důkazu říkáme indukce vzhledem ke struktuře formule (zkráceně strukturální indukce). Z (meta)konjunkce (1), (2) a (3) plyne, že každá formule má danou vlastnost. Jak je vidět na příkladu 1, princip strukturální indukce se opírá o princip úplné matematické indukce. Indukční krok úplné matematické indukce vzhledem k délce vytvořující posloupnosti se "rozpadne" na 3 případy - všechny možné struktury formule.
2
Příklad 2 Pro každé n G N+ (přirozené kladné číslo) označme Mn množinu všech formulí, pro které existuje vytvořující posloupnost délky n. Dále necht / : N+ —>• N+ je funkce definovaná následovně: f(n) = max{\p\ \ p G Mn}. Dokažte, že pro všechna n G N+ platí: f(n) = 2n+1 — 3.
Řešení
Rovnost dokážeme jako dvě nerovnosti:
(1) f(n) > 2n+1 - 3
(2) f(n) < 2n+1 - 3
Důkaz (1): Najdeme pro každé n G N+ formuli pn takovou, že \pn\ = 2n+1 — 3 a pn G Mn. Když v Mn leží formule délky x, pak maximální délka formule v Mn je alespoň x, proto f(n) > 2n+1 — 3.
Necht ipi = A a pro každé n G N, n > 1: pn = (pn-i fn-i)- Matematickou indukcí vzhledem k n dokážeme, že \ipn \ = 2n+1 — 3.
Pro n = 1: \Vl \ = \A\ = 1 = 21+1 - 3.
Necht pro n G N+ platí \ipn\ = 2n+1 - 3. Pak |v?„+i| = 2 * \ipn \ + 3 (dvě závorky, jedna binární spojka, dvě podformule) = 2*(2™+1 — 3)+ 3 (z indukčního předpokladu) = 2ÍJl+1^+1 — 3 (aritmetická úprava).
(Kdybychom chtěli být hodně precizní, ještě bychom dokázali, že pro všechna n G N+ je ipn formule, ne jen slovo. Je to nicméně celkem 'zřejmé').
Důkaz (2): Důkaz povedeme matematickou indukcí vzhledem k n.
Pro n = 1 nerovnost platí: /(l) = 1 (V množině M\ jsou právě formule délky 1) < 21+1 - 3.
Necht n G N+ a platí f(n) < 2n+1 - 3. Mějme nyní libovolnou formuli (f G Mn+\. Pro ip tedy existuje vytvořující posloupnost délky n + 1, označme ji -01,-02, ■■■,'4'n, f- Podle definice formule musí být p jednoho z následujících tří tvarů:
(1) p = A. Nerovnost pak zřejmě platí: \A\ = 1 < 2ÍJl+1^+1 — 3 pro všechna n G N+.
(2) p = —tipi pro nějaké i G N+, i < n. lpi patří do Mn, lpi, ip2, ipi—i, ipi Je její vytvořující posloupnost. (Je jasné, že když i < n, můžeme k této vytvořující posloupnosti na začátek přidat například formule Ai,Ä2, ...,An-i a tím získat vytvořující posloupnost formule lpi délky n). Z indukčního předpokladu pak platí: f(n) < 2n+1 - 3, proto i \ipt\ < 2n+1 - 3. Platí tedy \p\ = \ipt\ + 1 < 2«+i _ 3 + i < 2(«+i)+i _ 3 pro všechna n G N+.
(3) p = (lpi o ipj) pro nějaká i, j G N+, i, j < n, o je nějaká binární spojka, ipi, -pj patří do Mn (stejně jako -pi ve (2) ). Z indukčního předpokladu platí: f(n) < 2n+1 - 3, proto i |V>i| < 2™+1 - 3 a \ipA < 2n+1 - 3. Platí tedy W\ =      + \~Pjl + 3 < 2 * (2™+1 - 3) + 3 = 2(™+1)+1 - 3. □
Protože jsme si všimli, že p G Mi => p G Mn pro i < n, stačila nám (neúplná) matematická indukce. Pokud bychom si toho nevšimli/vedli důkaz trochu jinak, potřebovali bychom úplnou matematickou indukci, abychom měli nerovnost pro všechny formule ve vytvořující posloupnosti formule p, ne jen pro tu předposlední.
3