* 2   Důkazové techniky, Indukce
Náš hlubší úvod do matematických formalismů pro informatiku začneme základním přehledem technik matematických důkazů. Z nich pro nás asi nejdůležitější je technika důkazů matematickou indukcí, která je svou podstatou velmi blízká počítačovým programům (jako iterace cyklů).
Stručný přehled lekce
* Základní důkazové techniky: přímé, nepřímé a sporem. Důkazy „tehdy a jen tehdy".
* Důkazy matematickou indukcí, jejich variace a úskalí.
* Metody zesílení tvrzení a rozšíření základu v indukci.
Petr Hliněný, Fl MU Brno, 2014
1/15
Fl: IB000: Důkazy. Indukce
2.1   Přehled základních důkazových technik
• Přímé odvození. To je způsob, o kterém jsme se dosud bavili.
• Kontrapozice (také obrácením či nepřímý důkaz). Místo věty
„Jestliže platí předpoklady, pak platí závěr." budeme dokazovat ekvivalentní větu
„Jestliže neplatí závěr, pak neplatí alespoň jeden z předpokladů." c
• Důkaz sporem. Místo věty
„Jestliže platí předpoklady, pak platí závěr."
budeme dokazovat větu
„Jestliže platí předpoklady a platí opak závěru, pak platí opak jednoho z předpokladů (nebo platí jiné zjevně nepravdivé tvrzení)." c
• Matematická indukce. Pokročilá technika. ..
Petr Hliněný, Fl MU Brno, 2014
2/15
Fl: IB000: Důkazy. Indukce
Příklad důkazu kontrapozicí
Definice: Prvočíslo je celé číslo p > 1 a nemá jiné dělitele než lap.
Příklad 2.1.  A/a důkaz kontrapozicí (obrácením).
Věta. Jestliže p je prvočíslo větší než 2, pa/c p je liché.c
Důkaz: Obráceného tvrzení- budeme tedy dokazovat, že
je-li p sudé, pak p bud' není větší než 2, nebo p není prvočíslo.
Připomínáme, že podle definice je p sudé, právě když lze psát p = 2 • k, kde k je celé. Jsou dvě možnosti:
• k < 1. Pak p = 2k není větší než 2.
• > 1. Pak p = 2 ■ k není prvočíslo podle definice.
□
Petr Hliněný, Fl MU Brno, 2014
3/15
Fl: IB000: Důkazy. Indukce
Příklady důkazu sporem
Příklad 2.2. Jiný přístup k Důkazu 2.1.
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché.c
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2-k pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo}
Důkaz sporem: Nechť tedy \/2 je racionální, tj. nechť existují nesoudělná celá kladná
- Pak 2 — r2/s2, tedy r2 — 2 ■ s2, proto r2 je dělitelné dvěma. Z toho plyne, že i r je dělitelné dvěma (proč?).
- Jelikož r je dělitelné dvěma, je r2 dělitelné dokonce čtyřmi, tedy r2 — 4 • m pro nějaké m. Pak ale také 4 • m — 2 ■ s2, tedy 2 • m — s2 a proto s2 je dělitelné dvěma.c
- Z toho plyne, že s je také dělitelné dvěma. Celkem dostáváme, že r i s jsou dělitelné dvěma, jsou tedy soudělná a to je spor. □
Příklad 2.3. Opět sporem.
Věta. Číslo 72 není racionální.
čísla r, s taková, že \/2 — r/s.
Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem.. . "
Petr Hliněný, Fl MU Brno, 2014
4/15
Fl: IB000: Důkazy. Indukce
2.2   Vity typu „tehdy a jen tehdy"
• Uvažujme nyní (v matematice poměrně hojné) věty tvaru
„Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy, platí-li tvrzení B."c
• Příklady jiných jazykových formulací téže věty jsou:
* Za předpokladů P je tvrzení B nutnou a postačující podmínkou pro platnost tvrzení A.c
* Za předpokladů P je tvrzení A nutnou a postačující podmínkou pro platnost tvrzení B.c
* Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy když platí tvrzení Bx
• Důkaz vět tohoto tvaru má vždy dvě části(!). Je třeba dokázat:
* Jestliže platí předpoklady P a tvrzení A, pak platí tvrzení B.
* Jestliže platí předpoklady P a tvrzení B, pak platí tvrzení A.
Petr Hliněný, Fl MU Brno, 2014
5/15
Fl: IB000: Důkazy, Indukce
Příklad 2.4.  Na důkaz typu „tehdy a jen tehdy".
Věta. Dokažte, že pro každá dvě celá čísla a, b platí, že a < b právě tehdy, když 2a <2b.n
Důkaz: Nezapomínáme, že našim úkolem je dokázat oba směry tvrzení (implikace zleva doprava a zprava doleva). Začneme s prvním: Předpoklad a < b je definičně ekvivalentní tomu, že b = a + k pro nějaké přirozené k > 0. Potom
2b = 2a+k = 2a . 2k = £ . 2a prQ ngjaké pfirozené £ = 2k > 2, 3 tudíž
2b - 2a = (£ - 1) • 2a > 1 • 2a > 0. Tím je první část důkazu hotova, c
V opačném směru postupujeme z předpokladu 2a < 2b. Vydělením obou stran nerovnosti kladným číslem 2a získáme
2b/2a = 2b~a > 1 .c
Dále postupujeme sporem. Nechť tedy a > b, neboli a — b = m > 0. Potom máme 2a-b = 2_... 2 > 1. Avšak celkově 1 = 2° = 2a-b ■ 2^a > 1 • 1 = 1 je
mx
sporné. Proto zbývá požadovaný závěr a < b. a
Petr Hliněný, Fl MU Brno, 2014
6/15
Fl: IB000: Důkazy. Indukce
Matematická indukce
Jde o důkazovou techniku aplikovatelnou na tvrzení tohoto typu:
„Pro každé přirozené (celé) n > ko platí T {n). "
Zde ko je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. n.c
Příkladem je třeba tvrzení:
Pro každé n > 0 platí, že n přímek dělí rovinu nejvýše na \n{n + 1) + 1 oblastí.^
Princip matematické indukce říká (coby axiom), že k důkazu věty
„Pro každé přirozené (celé) n > ko platí T {n). " stačí ověřit platnost těchto dvou tvrzení:
* T(ko) (tzv. báze neboli základ indukce)
* Pro každé n > k$; jestliže platí T(n), (indukční předpoklad) pak platí také T(n + 1). (indukční krok)c
Příklady důkazů indukcí
Příklad 2.6.  Velmi jednoduchá a přímočará indukce.
Věta. Pro každé přiroz. n > 1 je stejná pravděpodobnost, že při současném hodu n kostkami bude výsledný součet sudý, jako, že bude lichý, c
Důkaz: Základ indukce je zde zřejmý: Na jedné kostce (poctivé!) jsou tři lichá a tři sudá čísla, takže obě skupiny padají se stejnou pravděpodobností.
Indukční krok pro n > 1: Nechť psn pravděpodobnost, že při hodu n kostkami bude výsledný součet sudý, a pln je pravděpodobnost lichého. Podle indukčního předpokladu je
s _ J  _ 1
Pn Pn
2
Hoďme navíc (n + l)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé číslo, je pravděpodobnost celkového sudého součtu rovna
3 z      3 . 1
a stejně pro pravděpodobnost celkového lichého součtu. a
Petr Hliněný, Fl MU Brno, 2014
8/15
Fl: IB000: Důkazy, Indukce
Příklad 2.7.  Ukázka skutečné důkazové „síly" principu matematické indukce. Věta. Pro každé n > O platí, že n přímek dělí rovinu nejvýše na
1
n(n + 1) + 1
oblastí.
Důkaz: nPro bázi indukce stačí, že 0 přímek dělí rovinu na jednu část. (Všimněte si také, že 1 přímka dělí rovinu na dvě části, jen pro lepší pochopení důkazu.)
Mějme nyní rovinu rozdělenou n přímkami na nejvýše \n(n + 1) + 1 částí.c Další, (n + l)-ní přímka je rozdělena průsečíky s předchozími přímkami na nejvýše n + 1 úseků a každý z nich oddělí novou část roviny. Celkem tedy bude rovina rozdělena našimi přímkami na nejvýše tento počet oblastí:
:n(n + l) + l + (n + l)
1   ,       .    1 ,
-n(n + l) + --2(n + l) + l
(n + l)(n + 2) + l
□
Petr Hliněný, Fl MU Brno, 2014
9/15
Fl: IB000: Důkazy. Indukce
Příklad 2.8. Další indukční důkaz rozepsaný v podrobných krocích. Věta. Pro každé n > O platí YTj=q3 = -c
Důkaz indukcí vzhledem k n.
• Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost Y^j=q3 = ■ Tato rovnost (zjevně) platí.
• Indukční krok: Musíme dokázat následující tvrzení pro n > 0:
Jestliže £UJ = ^IT^ Pak Platí EU J = g = n + 1. □
Předpokládejme tedy, že ^ľ=oÍ = n^n2+1^  a pokusme se dokázat, že pak také
;j=0J ~ 2
„• _ q(q+l) _ (n+l)(n "j=0 •
V^g      •      9(9+1)       (n+l)(n+2)      -r     - 1
Uj=qJ =    2    = -2- uz P'vne úpravou:
A.      A.    ,     ^      n(n+l)   , n(n+l) + 2(n+l)       (n+l)(n + 2)
= 2>+(n+1) =       2     +(n+1) = - 2 - = -2-^'
j=o j=0
Podle principu matematické indukce je celý důkaz hotov. a
Petr Hliněný,  Fl MU Brno, 2014
10/15
Fl: IB000: Důkazy, Indukce
2.4   Komentáře k matematické indukci
Pro správné a úspěšné použití indukce v dokazování je vhodné si zapamatovat několik cenných rad:
• Základní trik všech důkazů matematickou indukcí je vhodná reformulace tvrzení T{n + 1) tak, aby se „odvolávalo" na tvrzení T(n).
* Dobře se vždy podívejte, v čem se liší tvrzení T{n + 1) od tvrzení T(n). Tento „rozdíl" budete muset v důkaze zdůvodnit, c
• Pozor, občas je potřeba „zesílit" tvrzení T(n), aby indukční krok správně „fungoval".
• Často se chybuje v důkazu indukčního kroku, neboť ten bývá většinou výrazně obtížnější než báze,
ale o to zrádnější jsou chyby v samotné zdánlivě snadné bázi!
* Dejte si dobrý pozor, od které hodnoty n > ko je indukční krok univerzálně platný a jestli báze nezahrnuje více než jednu hodnotu...
Petr Hliněný,  Fl MU Brno, 2014
11/15
Fl: IB000: Důkazy, Indukce
Příklad 2.9. Když je nutno indukční krok zesílit... Věta. Pro každé n > 1 platí
,,111 1
s(n) =--1---1---1-----1----- < 1.
v 7     1-22-33-4 n(n + l)
Důkaz:n Báze indukce je zřejmá, neboť ^ < 1.
Co však indukční krok? Předpoklad s(n) < 1 je sám o sobě „příliš slabý" na to, aby bylo možno tvrdit s(n + 1) = s(n) + (n+1^n+2) < 1- 1
Neznamená to ještě, že by tvrzení nebylo platné, jen je potřeba náš indukční předpoklad zesílit. Budeme dokazovat
„Pro každé přirozené n > 1 platí s(n) < 1 —       < 1 ."c
To platí pro n = 1 a dále už úpravou jen dokončíme zesílený indukční krok:
, ,              1                       1 1 s(n+l) = s{n) + ----- < 1---h
(n + l)(n + 2) ~ n + 1 (n + l)(n + 2) 1 ,   ~(n + 2) + l   = x 1
(n + l)(n + 2) n + 2 □
Petr Hliněný,  Fl MU Brno, 2014
12/15
Fl: IB000: Důkazy, Indukce
Rozšíření báze a předpokladu
Mimo zesilování tvrzení indukčního kroku jsme někdy okolnostmi nuceni i k rozšiřování samotné báze indukce a s ní indukčního předpokladu na více než jednu hodnotu parametru n. c
- Můžeme například předpokládat platnost (parametrizovaných) tvrzení T(n) i T{n + 1) zároveň, a pak odvozovat platnost T{n + 2).
Toto lzesamozř. zobecnit na jakýkoliv počet předpokládaných parametrů.
- Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j = ko, ko + 1,..., n najednou a dokazovat T{n + 1).
Toto typicky využijeme v případech, kdy indukční krok „rozdělí" problém T{n + 1) na dvě menší části a z nich pak odvodí platnost T{n + 1).
Fakt: Obě prezentovaná „rozšíření" jsou v konečném důsledku jen speciálními instancemi základní matematické indukce; použité rozšířené možnosti pouze zjednodušují formální zápis důkazu.
Petr Hliněný,  Fl MU Brno, 2014
13/15
Fl: IB000: Důkazy, Indukce
Příklad 2.10. Když je nutno rozšířit bázi a indukční předpoklad...
Věta. Necht funkce f pro každé n > 0 splňuje vztah f(n + 2) = 2f(n + 1) - f(n). Pokud platí f(0) = 1 a zároveň /(l) = 2, tak platí f{n) = n + 1 pro všechna přirozená n > 0. c
Důkaz: Už samotný pohled na daný vztah f(n + 2) = 2/(n + 1) — /(n) naznačuje, že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé n > 0; jestliže platíT(n); neboli f(n) = n + 1, a zároveň p/arv T(n + 1); /(n + 1) = n + 2, pak platí také T(n + 2); f(n + 2) = n + 3.
Saze indukce -i pozor, zde už musíme ověřit dvě hodnoty
/(O) =0 + 1 = 1,    /(l) = 1 + 1 = 2.
Náš indukční krok tak nyní může využít celého rozšířeného předpokladu, znalosti hodnot f(n) i }'{n + 1), pro ověření
/(n + 2) = 2/(n + 1) - f(n) = 2-(n+l + l)-(n+l)=n + 3 = n + 2 + l.
□
Jak by tento důkaz měl být formulován v „tradiční" indukci? □(„Substitucí".)
Petr Hliněný,  Fl MU Brno, 2014
14/15
Fl: IB000: Důkazy. Indukce
Závěrem malý „problém"
Příklad 2.11. Aneb jak snadno lze v matematické indukci udělat chybu. Věta. („nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.c Důkaz indukcí vzhledem k n.
Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Indukční krok: Nechť S = {K±,..., Kn+{\ je stádo o n + 1 koních. Dokážeme, že všichni koně mají stejnou barvu. Uvažme dvě menší stáda:
Podle indukčního předpokladu mají všichni koně ve stádu S' stejnou barvu B'. Podobně všichni koně ve stádu S" mají podle indukčního předpokladu stejnou barvu B". □Dokážeme, že B' = B", tedy že všichni koně ve stádu S mají stejnou barvu. To ale plyne z toho, že koně K2, ■ ■ ■, Kn patří jak do stáda S', tak i do stáda S", c n
- S'
- S"
{KuKg,...,^} {K2, ...,Kn,Kn+1} c
Ale to už je podvod! Vidíte, kde?
Petr Hliněný,  Fl MU Brno, 2014
15/15
Fl: IB000: Důkazy, Indukce