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 nas asi nejd ů leZitejší je technika důkazů matematickou indukcí, která je svou podstatou velmi blízká pocítacovým program ů m (jako iterace cýkl ů ). StruCny 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 rozS ířen í zakladu v indukci. 'etr Hliněný. FI MU Brne_I: 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. c • Kontrapozice (take obrécením či nepřímé důkaz). Místo vety „JestliZe platí předpoklady, pak platí zaver." budeme dokazovat ekvivalentní vetu „JestliZe neplatí zaver, pak neplatí alespoň jeden z předpokladů." c • Důkaz sporem. M ísto vety „Jestlize platí předpoklady, pak platí zaver." budeme dokazovat vetu „Jestlize platí predpoklady a platí opak zaveru, pak platí opak jednoho z predpokladu (nebo platí jine zjevne nepravdive tvrzení)." c • Matematické indukce. Pokročilá technika... Petr Hliněný, FI MU Brno___FI: IB000: Důkazy, Indukce Příklad důkazu kontrapozicí Definice: Prvočíslo p > 1 nema jiné dělitele nez 1 a p. Příklad 2.1. na důkaz kontrapozicí (obrácením). Veta. Jestliže p je prvočíslo větsí nez 2, pak p je lichém Důkaz: Obraceného tvrzeni - budeme tedy dokazovat, že je-li p sude, pak p bud' není vetSí než 2, nebo p není prvočíslo. Jsou dve možnosti: • p < 2. Pak p nen í vetsí než 2. • p > 2. Pak p = 2 • k pro nejake cele k > 1, tedy p nen í prvoč íslo. c □ Poznámka: Dukazy kontrapozic í pracuj í s negací (opakem) predpokladu a zaveru. Je-li např. zaver komplikovane tvrzen í tvaru „z toho, ze z A a B plyne C, vyplýva, ze z A nebo C plyne A a B", nen í pouhou intuic í snadne zjistit, co je vlastne jeho negací. Jak uvid íme v pozdejsích lekcích, uzitím jednoduche induktivn í metody lze podobna tvrzen í negovat zcela mechanicky. Petr Hliněný. FI MU Brno___FI: IB000: Důkazy. Indukce r. Příklady důkazu sporem Příklad 2.2. Jiný přístup k Důkazu 2.1. Veta. Jestliže p je prvočíslo větší nez 2, pak p je lichí.c Důkaz sporem: Necht tedy p je prvočíslo větší než 2, ktere je sude. Pak p = 2 • k - Pak 2 = r2/s2, tedy r2 = 2 • s2, proto r2 je delitelne dvema. Z toho plyne, že i r je delitelne dvema (proč?). c - Jelikož r je delitelne dvema, je r2 delitelne dokonce čtyřmi, tedy r2 =4 • m pro nejake m. Pak ale take 4 • m = 2 • s2, tedy 2 • m = s2 a proto s2 je delitelne dvema.c - Z toho plyne, že s je take delitelne dvema. Celkem dostavame, že r i s jsou delitelne dvema, jsou tedy soudelna a to je spor. □ Nevíte-li, jak nejakou vetu dokažat, žkuste dukaž sporem.. . " Petr Hliněný. FI MU Brno I: IB000: Důkazy, Indukce 2.2 Věty typu „tehdy a jen tehdy" • Uvazujme nyn í (v matematice poměrně hojne) věty tvaru „Nechť platí předpoklady P. Pak tvrzen í A platí tehdy a jen tehdy, plat í-li tvrzen í B."c • Příklady jinych formulac í teZe vety jsou: * Za předpokladu P je tvrzen í B nutnou a postačující podm ínkou pro platnost tvrzen í A.c * Za předpokladu P je tvrzen í A nutnou a postacuj ící podm ínkou pro platnost tvrzen í B.c * Necht platí předpoklady P. Pak tvrzen í A platí právě tehdy kdyz platí tvrzen í B.c • Dukaz vet tohoto tvaru ma vzdy dve casti(!). Je treba dokazat: * Jestlize plat í predpoklady P a tvrzen í A, pak plat í tvrzen í B. * Jestliřze plat í přredpoklady P a tvrzen í B, pak plat í tvrzen í A. Petr Hliněný, FI MU Brno__: Důkazy, Indukce r. 2.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 nejake pevne přir. Číslo a T (n) je tvrzení parametrizovane Cís. n.c Příkladem je treba 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 ríka (coby axiom), ze k důkazu vety „Pro kaZde přirozene (cele) n > k0 platí T (n). " stacř í ovřeřrit platnost třechto dvou tvrzen í: * T(k0) (tzv. baze neboli zaklad indukce) * Pro každe n > k0; jestliže platí T (n), (indukční předpoklad) pak platí take T (n + 1). (indukční krok)c • Pozor, v tomto predmetu poďtáme 0 za přirozené ďslo! 'etr Hliněný, FI MU Brno I: IB000: Důkazy, Indukce r. Příklady důkazů indukcí Příklad 2.5. Velmi jednoduchá a přímočará indukce. Veta. Pro každé n > 1 je stejná pravděpodobnost, že při současnem hodu n kostkami bude výsledný součet sudý, jako, že bude lichý. c Důkaz: Zaklad indukce je zde zřejmý: Na jedne kostce (poctivé!) jsou tri licha a tri suda Čísla, takZe obe skupiny padají se stejnou pravdepodobností. c Indukční krok pro n > 1: Necht psn pravdepodobnost, Ze pri hodu n kostkami bude výsledný soucet sudý, a pln je pravdepodobnost licheho. Podle indukcního předpokladu je psn = pln = \. c Hod'me navíc (n + 1)-ní kostkou. Podle toho, zda na ní padne liche nebo sude císlo, je pravdepodobnost celkoveho sudeho souctu rovna l 3 s Vri r P n 1 2 a stejnře pro pravdřepodobnost celkoveho licheho souřctu. □ Petr Hliněný. FI MU Brno I: IB000: Důkazy, Indukce Příklad 2.6. Ukázka důkazové „síly" principu matematické indukce. Věta. Pro kazdé n > 0 platí, ze n přímek dél é rovinu nejváše na 1 ~-n(n + 1) + 1 oblastí Důkaz: aPro bazi indukce stačí, ze 0 přímek dělí rovinu na jednu část. (Všimněte si take, Ze 1 přímka delí rovinu na dve části, jen pro lepší pochopení dUkazu.) Mějme nyní rovinu rozdělenou n přímkami na nejvýše \n{n + 1) + 1 částí.c Dalsí, (n + 1)-ní přímka je rozdelena prusečíky s předchozími prímkami na nejvýše n + 1 useku a kazdy z nich oddelí novou čast roviny. aCelkem tedy bude rovina rozdelena nasimi přímkami na nejvyse tento počet oblastí: n(n + 1) + 1 + (n+1) 11 -n(n + l) + --2(n+l) + l J(n + l)(n + 2) + l □ Petr Hliněný. FI MU Brno -I: IB000: Důkazy, Indukce Příklad 2.7. Další indukční dUkaz rozepsaný v podrobných krocích. ri(ri+l) 2 Věta. Pro každé n>0 platíY,j=oJ = Důkaz indukci vzhledem k n. Baze: Musíme dokízat tvrzení T(0), coz je v tomto případě rovnost .0 • _ 0(0+ 3=0 J - 2 , j = 0(-02hl->. Tato rovnost (zjevně) platí Indukcn í krok: Musíme dokízat nísledující tvrzení: Jestliže platí Z)=oJ = ^ kde i > 0, pak platilo.i = (m)2(t+2) c Předpokládejme tedy, že Yľj=oJ = % k0 je indukcní krok uni-verzaílnňe platníy. . . 3etr Hliněný, FI MU Brno_10_FI: IB000: Důkazy, Indukce Příklad 2.8. Když je nutno indukční krok zesílit... Věta. Pro každe n > 1 platí s(n) = T^ + ^3 + 314 + --- + ^TT) 1 platí s(n) < 1 — < 1 ."c To platí pro n = 1 a dale uz Úpravou jen dokončíme zesílený indukční krok: ^1 1 1 Sin + 1) = Sin) +---r < 1---h--r-.-r = v ' K ' (n + l)(n + 2) ~ n + 1 (n + l)(n + 2) -(w + 2) + 1 _ 1 i - 1+ , v \~> ' x = 1 (n + 1)(n + 2) n + 2 □ Petr Hliněný, FI MU Brno_11_FI: IB000: Důkazy, Indukce Rozšíření baze a předpokladů Mimo zesilovan í tvrzen í indukcn ího kroku jsme nekdy okolnostmi nuceni i k rozsirovan í samotne baze indukce a s n í indukcn ího predpokladu na více nez jednu hodnotu parametru n. c - Muzeme například předpokladat platnost (parametrizovanych) tvrzen í T (n) i T (n + 1) zaroveř, a pak odvozovat platnost T (n + 2). Toto lze samozrejme zobecnit na jakykoliv pocet predpokladanych parametru. c - Muzeme dokonce předpokladat platnost tvrzen í T (j) pro vsechna j = ko, ko + 1,..., n najednou a dokazovat T (n + 1). (Toto typicky vyuzijeme v případech, kdy indukcn í krok „rozdel í" problem T (n + 1) na dve mensí casti a z nich pak odvod í platnost T (n + 1).) c Fakt: Obe prezentovana „rozsíren í" jsou v konecnem dusledku jen specialn ími instancemi zakladn í matematicke indukce; pouzite rozsírene moznosti pouze zjednodusuj í formaln í zapis dukazu. Petr Hliněný. FI MU Brno_12_FI: IB000: Důkazy. Indukce r. Příklad 2.9. Kdyz je nutno rozsíěit bízi a indukčnípěedpoklad... Věta. Necht funkce f pro kaěde n > 0 splňuje vztah f (n + 2) = 2 f(n + 1) - f (n). Pokud platí f (0) = 1 a zároven f (1) = 2, tak platí f (n) = n + 1 pro všechna píirozená n > 0. c DUkaz: Uz samotny pohled na dany vztah f (n + 2) = 2 f (n + 1) — f (n) naznacuje, ze bychom meli rozsírit indukcn í predpoklad (a krok) zhruba takto: Pro kazde n > 0; jestliže platí T (n); neboli f (n) = n + 1, a zároven platí T (n + 1); f (n + 1) = n + 2, pak platítakí T (n + 2); f (n + 2) = n + 3. Bíze indukce -c pozor, zde uz musíme overit dve hodnoty Nas indukcní krok tak nyn í muze vyuz ít celeho rozsíreneho předpokladu, znalosti hodnot f (n) i f (n + 1), pro overen í f (n + 2) = 2f (n + 1) — f (n) = 2 • (n +1 + 1) — (n +1)= n + 3 = n + 2 + 1. Jak by tento dukaz mel byt formulovan v „tradičn í" indukci? („Substitucí".) f (0) =0 + 1 = 1, f (1) = 1 + 1 = 2 .c □ 'etr Hliněný, FI MU Brno I: IB000: Důkazy, Indukce r. 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 kazdem stádu o n > 1 koních mají véichni kone stejnou barvu.c Důkaz indukcí vzhledem k n. Baze: Ve stadu o jednom koni mají všichni kone stejnou barvu.c Indukcn í krok: Necht S = [K\,..., Kn+1} je stado o n +1 koních. DokaZeme, Ze všichni kone mají stejnou barvu. UvaZme dve menší stada: - S' = {Kl,K2,...,Kn} - S'' = {K2,...,Kn,Kn+l} □ Podle indukcního předpokladu majívsichni kone ve stadu S' stejnou barvu B'. Podobne vsichni kone ve stadu S'' maj í podle indukcn ího předpokladu stejnou barvu B''. cDokaZeme, Ze B' = B'', tedy Ze vsichni kone ve stadu S maj í stejnou barvu. To ale plyne z toho, Ze kone K2,..., Kn patří jak do stada S', tak i do stada S''. □ Ale to uZ je podvod! Vid íte, kde? Petr Hliněný, FI MU Brno I: IB000: Důkazy, Indukce