* 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, 2011 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, 2011 2/15 Fl: IB000: Důkazy. Indukce Příklad důkazu kontrapozicí Definice: Prvočíslo p > 1 nemá jiné dělitele než lap. Příklad 2.1. na důkaz kontrapozicí (obrácením). Věta. Jestliže p je prvočíslo větší než 2, pak 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, 2011 3/15 Fl: IB000: Důkazy. Indukce Poznámka: Důkazy kontrapozicí pracují s negací(opakem) předpokladů a závěru. Je-li např. závěr komplikované tvrzení tvaru „z toho, že z A a B plyne C, vyplývá, že z A nebo C plyne A a není pouhou intuicí snadné zjistit, co je vlastně jeho negací. Jak uvidíme v pozdějších lekcích, užitím jednoduché induktivní metody lze podobná tvrzení negovat zcela mechanicky. Petr Hliněný, Fl MU Brno, 2011 4/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. 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, 2011 5/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 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, 2011 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ín 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 Pozor, v tomto předmětu počítáme 0 za přirozené číslo! Příklady důkazů indukcí Příklad 2.5. Velmi jednoduchá a přímočará indukce. Věta. Pro každé 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ý. 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 psn = pln = \. c 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, 2011 8/15 Fl: IB000: Důkazy. Indukce Příklad 2.6. Ukázka 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í: 1 n(n + l) + l + (n + l) 1 , . 1 , -n(n + l) + --2(n + l) + l 1 n + l)(n + 2) + l □ Petr Hliněný, Fl MU Brno, 2011 9/15 Fl: IB000: Důkazy, Indukce Příklad 2.7. 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 <7 = J2°j=o3 = ■ Tato rovnost (zjevně) platí. • Indukční krok: Musíme dokázat následující tvrzení: Jestliže platíjyj=0j = kde i > 0, pak platili j = (m)2(ž+2). Předpokládejme tedy, že ^}=oÍ = a pokusme se dokázat, že pak také V^í+l • (J+l)(i+l+l) (í+1)(í+2) -p | l^j=o3 = — 2- = —2— ■ ^° uz P'vne úpravou: g, = ±JHí+1) = i ko je indukční krok univerzálně platný. .. Petr Hliněný, Fl MU Brno, 2011 11/15 Fl: IB000: Důkazy, Indukce Příklad 2.8. 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 = 1 1 (n + l)(n + 2) n+ 2 □ Petr Hliněný, Fl MU Brno, 2011 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 lze samozř. zobecnit na jakýkoliv počet předpokládaných parametrů. c - 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, 2011 13/15 Fl: IB000: Důkazy, Indukce Příklad 2.9. Když je nutno rozšířit bázi a indukční předpoklad... Věta. Necht funkce f pro každé n > O 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 /(n + 2) = 2f(n + 1) — f(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ň platí T(n + 1); f(n + 1) = n + 2, pa/c platí také T(n + 2); /(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) - /(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, 2011 14/15 Fl: IB000: Důkazy, Indukce Závěrem malý „problém" Příklad 2.10. 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' {KuKz,...,^} {K2,...,Kn,Kn+1} c - S' Ale to už je podvod! Vidíte, kde? Petr Hliněný, Fl MU Brno, 2011 15/15 Fl: IB000: Důkazy, Indukce