■r 4 Techniky matematických důkazů 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 „právě tehdy, když". * Důkazy matematickou indukcí, jejich variace a úskalí. * Metody zesílení tvrzení a rozšírení základu v indukci. □ Petr Hliněný, Fl MU Brno, 2023 1/16 Fl: IB000: Techniky důkazů 4.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é obměnou - „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ů." • 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í.. . " - nějaké zjevně nepravdivé tvrzení, nebo případně - závěr (tj. opak jeho opaku) či opak jednoho z předpokladů. • Matematická indukce. Pokročilá technika. .. Petr Hliněný, Fl MU Brno, 2023 2/16 Fl: IB000: Techniky důkazů Příklad důkazu kontrapozicí Definice: Prvočíslo je celé číslo p > 1, které nemá jiné dělitele než lap. Příklad 4.1. Na důkaz kontrapozicí (obměnou). Věta. Jestliže p je prvočíslo větší než 2, pak p je liché.c Důkaz obměněného tvrzení: Místo uvedeného znění věty budeme dokazovat, že je-li p sudé, pak p 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é. nJsou jen dvě snadno řešitelné možnosti: • fc < 1. Pak p = 2 • A; není větší než 2. • k > 1. Pak p = 2 • k není prvočíslo podle definice. Petr Hliněný, Fl MU Brno, 2023 3/16 Fl: IB000: Techniky důkazů Příklady důkazu sporem Příklad 4.2. Jiný, kratší přístup k Důkazu 4.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] - 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. - 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 4.3. Opět sporem. Věta. Číslo V2 není racionální. Důkaz sporem: Nechť tedy \/2 je racionální, tj. nechť existují nesoudělná celá kladná Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem... Petr Hliněný, Fl MU Brno, 2023 4/16 Fl: IB000: Techniky důkazů 4.2 Věty typu „právě tehdy (když)" • Uvažujme nyní (v matematice poměrně hojné) věty tvaru „Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy, platí-li tvrzení B." • Příklady jiných jazykových formulací téže věty jsou: * Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy, když platí tvrzení B.c * 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. • Plný 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, 2023 5/16 Fl: IB000: Techniky důkazů Příklad 4.4. Na důkaz typu „právě tehdy (když)". Věta. Pro dvě množiny A, B platí, že 2A = 2B právě tehdy když A2 — B2: Důkaz: Nezapomínáme, že našim úkolem je dokázat oba směry tvrzení (implikace zleva doprava a zprava doleva). Přitom obě implikace budeme dokazovat obměnou, symbolicky jako 2A ^ 2B <^=> A2 ^ B2. □ Začneme s prvním směrem: Je-li 2A ^ 2B, pak existuje množina X taková, že X C A a X 2 B (nebo naopak - což se řeší symetricky). nX 2 B přitom podle definice znamená, že pro nějaké y G X platí y 0 B. Zároveň však y G A.c Proto (y, y) G A2, ale {y, y) 0 B2, neboli A2 ^ B2. □ V opačném směru postupujeme z předpokladu A2 7^ B2. Zase z toho odvodíme, že existuje uspořádaná dvojice taková, že (x, y) G A2, ale (x, y) 0 B2.c Z posledního vyplývá, ze x ^ B nebo y ^ B. Opět bez újmy na obecnosti můžeme vzít jen případ x ^ B. Avšak z (x, y) G A2 vidíme, že x G A. Proto {x} G 2A, ale {x} 0 2B, neboli 2A ^ 2B. n Petr Hliněný, Fl MU Brno, 2023 6/16 Fl: IB000: Techniky důkazů 4.3 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 ^— • 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(fco) (tzv. báze neboli základ indukce) * Pro každé k > ko; jestliže platí T (k), (indukční předpoklad) pak platí také T{k + 1). (indukční krok) Petr Hliněný, Fl MU Brno, 2023 7/16 Fl: IB000: Techniky důkazů ■r Příklady důkazů indukcí Příklad 4.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ý. 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 k > 1: Nechť psk pravděpodobnost, že při hodu k kostkami bude výsledný součet sudý, a plk je pravděpodobnost lichého. Podle indukčního předpokladu je * J 1 Pk — Pk — 2 □ Hoďme navíc (k + l)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé číslo, je pravděpodobnost celkového sudého součtu rovna 3 l 3 8 _ 1 6Pk + 6Pk ~ 2 a stejně pro pravděpodobnost celkového lichého součtu. □ Petr Hliněný, Fl MU Brno, 2023 8/16 Fl: IB000: Techniky důkazů ■r Příklad 4.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 -n(n + í) + l oblastí. Důkaz: nPro bázi indukce postačí, že n = 0 přímek dělí rovinu na jednu oblast. (Všimněte si také, že 1 přímka dělí rovinu na dvě oblasti.) Mějme nyní rovinu rozdělenou n — k přímkami na nejvýše \k(k + 1) + 1 oblastí.n Další, (fc + l)-ní přímka je rozdělena průsečíky s předchozími přímkami na nejvýše k + 1 úseků a každý z nich oddělí novou oblast roviny. nCelkem tedy bude rovina rozdělena našimi přímkami na nejvýše tento počet oblastí: ^fc(fc + l) + l + (fc+l) = ifc(fc + l) + ~2(fc+l) + l = + l)(fe + 2) + ln A toto je přesně naše tvrzení pro n = k + 1, takže jsme hotovi. q Petr Hliněný, Fl MU Brno, 2023 9/16 Fl: IB000: Techniky důkazů Příklad 4.8. Další indukční důkaz rozepsaný v podrobných krocích. Věta. Pro každé n > O platí Ej=oÍ = ^^^-^ Důkaz indukcí vzhledem k n. • Báze: Zde musíme dokázat platnost tvrzení pro n := 0, což je v tomto případě rovnost Y^j=o3 ~ ■ Tato rovnost (zjevně) platí. • Indukční krok: Musíme dokázat, pro každé k > 0, že z platnosti tvrzení pro n := k vyplývá platnost pro n := k + 1, což konkrétně znamená: Jestliže Eí=03 = pa* platí3 = (k+l){\+l+l) ■ □ Předpokládejme tedy, že Y^j=o3 = k^k^ a pokusme se dokázat, že pak také v^fc+1 • 0+1)0+1+1) 0+1)0+2) -r - i w Z^j=o3 — 2— ~ 2 ■ 0 uz P'yne pnmocarou úpravou: EJ = I>(*+1) = = ^^^^^^ = ^ + 'f + 2) j=0 j=0 Podle principu matematické indukce je celý důkaz hotov. i-| Petr Hliněný, Fl MU Brno, 2023 10/16 Fl: IB000: Techniky důkazů 4.4 Komentáře k matematické indukci • 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. • Dokud se matematickou indukci teprve učíte, používejte následující. Zaveďte si další proměnnou k a formulujte svá tvrzení a úpravy stylem „platí-li naše tvrzení T(n) pro n := k, pak bude platit i pro n := k + 1". • Pozor, občas je potřeba zesílit tvrzení T(n), aby indukční krok správně „fungoval" (a jsou situace, kde tento trik velmi pomáhá). • Č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, 2023 11/16 Fl: IB000: Techniky důkazů Příklad 4.9. Kdy je vhodné (a v zásadě také nutné) indukční tvrzení zesílit... Věta. Pro každé n > 1 platí , x 1 1 1 1 Důkazn Báze indukce je zřejmá, neboť \ < 1. Co však indukční krok? Předpoklad < 1 je sám o sobě „příliš slabý" na to, aby bylo možno tvrdit také s(n + 1) = s(n) + < 1. □ Neznamená to ještě, že by celé tvrzení nebylo platné, jen je potřeba náš indukční předpoklad zesílit. nBudeme raději dokazovat silnější „Pro každé přirozené n > 1 platí s(n) < 1 — < 1 ."□ To platí pro bázi n = 1, neboť \ < 1 — \, a dále už úpravou jen dokončíme zesílený indukční krok: 1 11 1 S(n+1) s(ri)-{---r < 1---1--— = 1---r V 1 / V / 1 — On 972+1 971+1 Petr Hliněný, Fl MU Brno, 2023 12/16 Fl: IB000: Techniky důkazů Rozšíření předpokladu; silná indukce 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. - 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 tři i více předpokládaných parametrů.c - Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j = fco, ko + 1,..., n najednou a dokazovat T{n + 1) (vznešeně se této variantě indukce říká silná indukce). 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; nejsou o nic „silnější" ve striktním matematickém smyslu a použité rozšířené možnosti pouze zjednodušují formální zápis důkazu. Petr Hliněný, Fl MU Brno, 2023 13/16 Fl: IB000: Techniky důkazů Příklad 4.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 /(n + 2) = 2/(n + l)-/(n). Pokud platí f(0) — la zároveň f(l) = 2, ra/c platí f (n) = n + 1 pro všechna přirozená n > 0. Důkaz: Už samotný pohled na daný vztah /(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é přirozené k > 0; jestliže platí f (n) — n + 1 pro n \— k a zároveň pro n \— k + 1, pak f(n) = n + 1 platí také pro n := k + 2. Báze indukce -□ pozor, zde už musíme ověřit dvě hodnoty pro n:=0an:=l: /(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(k) i f(k + 1), pro ověření požadovaného vztahu pro n := k + 2 /(n) = /(fc + 2) = 2/(fc + l)-/(fc) =2-(fc + l + l)-(fc + l) =fc + 3 = n + l. □ Petr Hliněný, Fl MU Brno, 2023 14/16 Fl: IB000: Techniky důkazů Příklad 4.11. Ukázka s vhodným použitím silné indukce: Věta. Každé přirozené číslo n > 2 lze zapsat jako součin prvočísel (může být jen jednoho a prvočísla nemusí být různá).c Důkaz: Báze indukce. Nechť n = 2, pak n je prvočíslem a součinem jednoho prvočísla, c Indukční krok. Pokud nemá n vlastní dělitele, je n prvočíslem vzhledem k předpokladu n > 2, což je shodné s bází. Jinak napíšeme n = a - b, kde platí a, b > 2 a zároveň a, b < n, a proto lze na obě čísla a, b použít indukční předpoklad. iTudíž každé z nich lze napsat jako součin prvočísel a jelikož ta nemusí být různá, prostě oba součiny sloučíme do jednoho, jehož výsledkem je a • b = n. n Petr Hliněný, Fl MU Brno, 2023 15/16 Fl: IB000: Techniky důkazů Závěrem malý „problém" Příklad 4.12. 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. Důkaz indukcí vzhledem k n. Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.c Indukční krok: Nechť S — {K\,..., Kn+i} je stádo o n +1 koních. Dokážeme, že všichni koně mají stejnou barvu. Uvažme dvě menší stáda: - S' = {KuK2,...,Kn} - S" = {K2,...,Kn,Kn+1} □ Podle indukčního předpokladu mají všichni koně ve stádu Sf 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 Sf, tak i do stáda S". □ □ Ale to už je podvod! Vidíte, kde? Petr Hliněný, Fl MU Brno, 2023 16/16 Fl: IB000: Techniky důkazů