Petr Hliněný, FI MU Brno 1 FI: IB000: Důkazy, Indukce 2 Důkazové techniky, Indukce2 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ů). 2 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ý, FI MU Brno 2 FI: IB000: Důkazy, Indukce 2.1 Přehled základních důkazových technik2.1 Přehled základních důkazových technik * Přímé odvození. To je způsob, o kterém jsme se dosud bavili. 2 * 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ů. 2 * 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í). 2 * Matematická indukce. Pokročilá technika. . . Petr Hliněný, FI MU Brno 3 FI: IB000: Důkazy, Indukce Příklad důkazu kontrapozicí Definice: Prvočíslo p > 1 nemá jiné dělitele než 1 a p. 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é.2 Důkaz: Obráceného tvrzení ­ budeme tedy dokazovat, že je-li p sudé, pak p buď není větší než 2, nebo p není prvočíslo. Jsou dvě možnosti: * p 2. Pak p není větší než 2. * p > 2. Pak p = 2.k pro nějaké celé k > 1, tedy p není prvočíslo. 2 2 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 B , 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ý, FI MU Brno 4 FI: 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é.2 Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2k pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo).2 2 Příklad 2.3. Věta. Číslo 2 není racionální.2 Důkaz sporem: Nechť tedy 2 je racionální, tj. nechť existují nesoudělná celá kladná čísla r, s taková, že 2 = r/s. 2 ­ 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č?). 2 ­ 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.2 ­ 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. 2 2 ,,Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem. . . Petr Hliněný, FI MU Brno 5 FI: IB000: Důkazy, Indukce 2.2 Věty typu ,,tehdy a jen tehdy2.2 Věty 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. 2 * 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.2 Za předpokladů P je tvrzení A nutnou a postačující podmínkou pro platnost tvrzení B.2 Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy když platí tvrzení B.2 * 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ý, FI MU Brno 6 FI: IB000: Důkazy, Indukce 2.3 Matematická indukce2.3 Matematická indukce * Jde o důkazovou techniku aplikovatelnou na tvrzení tohoto typu: ,,Pro každé přirozené (celé) n k0 platí T(n). Zde k0 je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. n.2 Příkladem je třeba tvrzení: Pro každé n 0 platí, že n přímek dělí rovinu nejvýše na 1 2n(n + 1) + 1 oblastí.2 * Princip matematické indukce říká (coby axiom), že k důkazu věty ,,Pro každé přirozené (celé) n k0 platí T(n). stačí ověřit platnost těchto dvou tvrzení: T(k0) (tzv. báze neboli základ indukce) Pro každé n k0; jestliže platí T(n), (indukční předpoklad) pak platí také T(n + 1). (indukční krok)2 * Pozor, v tomto předmětu počítáme 0 za přirozené číslo! Petr Hliněný, FI MU Brno 7 FI: IB000: Důkazy, Indukce Příklady důkazů indukcí Příklad 2.4. 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ý. 2 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í. 2 Indukční krok pro n 1: Nechť ps n pravděpodobnost, že při hodu n kostkami bude výsledný součet sudý, a pl n je pravděpodobnost lichého. Podle indukčního předpokladu je ps n = pl n = 1 2. 2 Hoďme navíc (n + 1)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé číslo, je pravděpodobnost celkového sudého součtu rovna 3 6 pl n + 3 6 ps n = 1 2 a stejně pro pravděpodobnost celkového lichého součtu. 2 Petr Hliněný, FI MU Brno 8 FI: IB000: Důkazy, Indukce Příklad 2.5. Ukázka důkazové ,,síly principu matematické indukce. Věta. Pro každé n 0 platí, že n přímek dělí rovinu nejvýše na 1 2 n(n + 1) + 1 oblastí. Důkaz: 2Pro 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 1 2 n(n+1)+1 částí. Další, (n + 1)-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. 2Celkem tedy bude rovina rozdělena našimi přímkami na nejvýše tento počet oblastí: 1 2 n(n + 1)+1+(n+1) = 1 2 n(n + 1)+ 1 2 2(n+1)+1 = 1 2 (n + 1)(n + 2)+1 2 Petr Hliněný, FI MU Brno 9 FI: IB000: Důkazy, Indukce Příklad 2.6. Další indukční důkaz rozepsaný v podrobných krocích. Věta. Pro každé n 0 platí n j=0 j = n(n+1) 2 .2 Důkaz indukcí vzhledem k n. * Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost 0 j=0 j = 0(0+1) 2 . Tato rovnost (zjevně) platí.2 * Indukční krok: Musíme dokázat následující tvrzení: Jestliže platí i j=0 j = i(i+1) 2 kde i 0, pak platí i+1 j=0 j = (i+1)(i+2) 2 . 2 Předpokládejme tedy, že i j=0 j = i(i+1) 2 a pokusme se dokázat, že pak také i+1 j=0 j = (i+1)(i+1+1) 2 = (i+1)(i+2) 2 . To už plyne úpravou: i+1 j=0 j = i j=0 j +(i+1) = i(i + 1) 2 +(i+1) = i(i + 1) + 2(i + 1) 2 = (i + 1)(i + 2) 2 2 Podle principu matematické indukce je celý důkaz hotov. 2 Petr Hliněný, FI MU Brno 10 FI: IB000: Důkazy, Indukce 2.4 Komentáře k matematické indukci2.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. 2 * Pozor, občas je potřeba ,,zesílit tvrzení T(n), aby indukční krok správně ,,fungoval .2 * Č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 k0 je indukční krok univerzálně platný. . . Petr Hliněný, FI MU Brno 11 FI: IB000: Důkazy, Indukce Příklad 2.7. Když je nutno indukční krok zesílit. . . Věta. Pro každé n 1 platí s(n) = 1 1 2 + 1 2 3 + 1 3 4 + . . . + 1 n(n + 1) < 1 . Důkaz:2 Báze indukce je zřejmá, neboť 1 12 < 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) + 1 (n+1)(n+2) < 1. 2 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 n+1 < 1 . 2 To platí pro n = 1 a dále už úpravou jen dokončíme zesílený indukční krok: s(n + 1) = s(n) + 1 (n + 1)(n + 2) 1 - 1 n + 1 + 1 (n + 1)(n + 2) = = 1 + -(n + 2) + 1 (n + 1)(n + 2) = 1 - 1 n + 2 2 Petr Hliněný, FI MU Brno 12 FI: 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. 2 ­ 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řejmě zobecnit na jakýkoliv počet předpokládaných parametrů. 2 ­ Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j = k0, k0 + 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).) 2 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ý, FI MU Brno 13 FI: IB000: Důkazy, Indukce Příklad 2.8. Když je nutno rozšířit bázi a indukční předpoklad. . . Věta. Nechť 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ň f(1) = 2, tak platí f(n) = n + 1 pro všechna přirozená n 0. 2 Důkaz: Už samotný pohled na daný vztah f(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, pak platí také T(n + 2); f(n + 2) = n + 3. Báze indukce ­2 pozor, zde už musíme ověřit dvě hodnoty f(0) = 0 + 1 = 1, f(1) = 1 + 1 = 2 .2 Náš indukční krok tak nyní může využít celého rozšířeného předpokladu, znalosti hodnot f(n) i f(n + 1), pro ověření f(n + 2) = 2f(n + 1) - f(n) = 2 (n + 1 + 1) - (n + 1) = n + 3 = n + 2 + 1 . 2 Jak by tento důkaz měl být formulován v ,,tradiční indukci? 2(,,Substitucí .) Petr Hliněný, FI MU Brno 14 FI: IB000: Důkazy, Indukce Závěrem malý ,,problém Příklad 2.9. 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.2 Důkaz indukcí vzhledem k n. Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.2 Indukční krok: Nechť S = {K1, . . . , Kn+1} je stádo o n + 1 koních. Dokážeme, že všichni koně mají stejnou barvu. Uvažme dvě menší stáda: ­ S = {K1, K2, . . . , Kn} ­ S = {K2, . . . , Kn, Kn+1} 2 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. 2Dokáž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. 2 2 Ale to už je podvod! Vidíte, kde?