1 Matematika — krátký přehled důkazových metod Podobně jako prací chirurga je kromě zdravotní prevence i řezat a prací poštovního doručovatele je doručování korespondence, prací matematickou je kromě počítání i dokazování či zdůvodňování zákonitostí, které platí a na jejichž základě se dějí různé početní algoritmy a odehrává se veškerý svět matematických pojmů a skutečností. Věnujme se v tomto krátkém přehledu čtyřem typům zdůvodnovacích-dokazovacích technik: 1) přímý důkaz implikace, 2) nepřímý důkaz implikace, 3) důkaz sporem, 4) důkaz úplnou matematickou indukcí. Základní kategorie při výstavbě matematiky Matematika je věda o přesném vyjadřování, a my se nyní tento jazyk budeme učit -jinými slovy, budeme se učit a) přesně formulovat pojmy, b) přesně formulovat, ze kterých jednoduchých a platných faktů vycházíme, c) dokazovat platnost nových faktů na základě faktů samozřejmých nebo dokázaných už dříve. (matematická) definice je přesné vymezení pojmu, z něhož je patrno, které objekty toto vymezení splňují a které ne (např. bod, úsečka, přímka, kružnice, úhel, rovnoběžka ... to vše jsou pojmy, které musíme jednoznačně definovat v tzv. Euklidovské geometrii). (matematický) axiom je tvrzení o vlastnostech pojmů či o vztazích mezi pojmy, které se nedokazuje, nýbrž všeobecně přijímá jako pravdivé (např. axiomy Euklidovské geometrie). (matematická) věta je tvrzení o vlastnostech pojmů či vztazích mezi pojmy, které musíme dokázat pomocí axiomů, definic a vět dokázaných již dříve. Typ důkazu číslo 01: Přímý důkaz implikace A =>- B. Při přímém důkazu implikace A =>- B vyjdeme z toho, že platí výrok A; na základě posloupnosti zřejmých implikací pak vyvozujeme další skutečnosti, až dospějeme k výroku B. Příklad 1. Dokažte: Pro přirozená čísla a, 6, c platí: a\b A a\c =>- a\(b + c) (pro neznalce značek symbolických: Jestliže číslo a je dělitelem čísla b a současně číslo a je dělitelem čísla c, tak také číslo a je dělitelem součtu čísel (b + c)). Důkaz: Uvedený výrok z oblasti dělitelnosti je celkem triviální a běžně ho používáme, ale i ten by matematický přístup měl dokázat zdůvodnit. Výrok A v našem případě říká: a\b A a\c. Z toho zřejmě plyne: existují přirozená čísla k, l taková, že b = k-a a současně c = l-a. Z toho zřejmě plyne: zkoumejme nyní, zda je číslo (6 + c) dělitelné číslem a: b + c = k- a + l- a= (k + 1) ■ a. 2 Z toho, že (b+c) = a-(k + l), plyne, že číslo a je dělitelem čísla (b+c). Důkaz je hotov. □ Typ důkazu číslo 2: NEpřímý důkaz implikace A =>- B. Při NEpřímém důkazu implikace A =>- B vlastně dokazujeme platnost logicky s ní ekvivalentní formy -iB =>• ->A. Forma -iB =>• ->A se nazývá obměna implikace A ^ B1. Dokažte matematickou větu: Pro každé přirozené číslo n platí: 2\n2 2\n (pro neznalce matematických symbolů: jestliže číslo 2 je dělitelem čísla n2, tak také je číslo 2 dělitelem čísla n). Důkaz: Máme dokázat implikaci typu A =>- B. Někdy (a to bude právě v našem případě) je ovšem jednodušší dokazovat logickou obměnu -iB =>• ->A neboli výrok 2 /n =>• 2 /n2 (pro neznalce: Jestliže číslo 2 není dělitelem čísla n, tak také číslo 2 není dělitelem čísla Vycházíme nyní z výroku ->B: 2 /n; Z toho zřejmě plyne: tedy n je liché a lze je psát ve tvaru n = 2k + 1, kde A; je přirozené číslo nebo nula. Z toho zřejmě plyne: n2 lze vyjádřit ve tvaru n2 = (2k + l)2 = 4k2 + 4k + 1; odtud je evidentní, že n2 je číslo liché, a tedy není dělitelné dvěma. Důkaz je hotov: tím, že jsme prokázali platnost výroku -iB =>• ->A, prokázali jsme současně i platnost výroku k němu logicky ekvivalentního, tj. A =^ B. □ Typ důkazu číslo 03: Důkaz sporem. Předpokládáme platnost negace daného tvrzení a logicky správně z této negace pomocí řetězce přímých implikací (jako u důkazu přímého) odvozujeme další věci, které zřejmě platí, dokud nedojdeme k nesmyslu, který neplatí. Protože jsme pracovali logicky naprosto správně, tak kořen rozporu je ve startovacím předpokladu — nyní víme, že předpoklad - B vlastně znamená provést přímý důkaz její obměny => —iA. 3 Důkaz: budeme předpokládat negaci zadaného výroku, tj. že log2 3 je racionální číslo, tj. lze tuto hodnotu vyjádřit zlomkem: i q m log2 3 = — n pro m G Z a n G N. Potom z definice logaritmu plyne 2» = 3. Z toho zřejmě plyne umocněním vztahu na n-tou: 2m = 3n, a na obou stranách této rovnosti se přitom vyskytují přirozená čísla. Odtud zřejmě plyne: Protože číslo 2 je dělitelem čísla 2m a platí 2m = 3n, musí být číslo 2 také dělitelem čísla 3n - ale to je spor se známým faktem, že číslo 2 není dělitelem žádného lichého čísla (a číslo 3n jako násobek n lichých čísel je liché). Naprosto korektními úvahami jsme přišli k nesmyslu, tj. nesprávný byl náš výchozí předpoklad - a tedy platí jeho negace: log2 3 není racionální číslo. □ Typ důkazu číslo 04: Důkaz úplnou matematickou indukcí. Při matematické indukci dokazujeme tzv. univerzální výrok, který platí většinou pro všechna přirozená čísla, která jsou větší nebo rovna přirozenému číslu n0, tj. výroky typu Vn > n0 : V(n). Platnost tohoto univerzálního výroku dokazujeme ve dvou krocích: a) Dokážeme platnost výroku V(rio) pro nejmenší možné přirozené číslo, pro které výrok platí. Obvykle n0 = 1. b) Dokážeme platnost implikace V(n) =^ V(n + 1). Pokud platí obě tyto věci, bude tím dokázána platnost výroku V(n) pro jakékoli přirozené číslo n. Příklad 4. Dokažte indukcí: Pro každé přirozené číslo n platí: 3|(n3 + 2n) (číslo 3 je dělitelem čísla (n3 + 2n)). Důkaz: a) V^l): pro n = 1 ... 3|(13 + 2-1) ... tento výrok evidentně platí. b) Dokážeme platnost implikace V(n) =^ V(n + 1). Pro výrok tohoto příkladu implikace nabývá tvar 3|(n3 + 2n) =>■ 3|((n + l)3 + 2(n + 1)). 4 Dokažme tuto implikaci některým ze způsobů důkazu implikace, většinou to bude důkaz typu 1, tj. důkaz přímý: Předpokládejme, že 3|(n3 + 2n) a chceme pomocí řetězce zřejmých implikací dokázat platnost výroku 3\((n + l)3 + 2(n + 1)): Prozkoumejme blíže číslo {{n + l)3 + 2(n + 1)): ((n + l)3 + 2(n + 1) = n3 + 3n2 + 3n + 1 + 2n + 2 = (n3 + 2n) + (3n2 + 3n + 3). A nyní: první z obou sčítaných závorek je dělitelná třemi, na základě toho, že jsme tuto skutečnost předpokládali na začátku tohoto důkazu (jedná se o výrok V(n)). Druhá z obou sčítaných závorek je dělitelná třemi proto, že ji lze upravit do tvaru 3 • (n2 + n + 1). A tedy (podle tvrzení v příkladu 1) i součet dvou těchto závorek je dělitelný třemi. Příklad 5. Dokažte indukcí: Pro každé přirozené číslo n platí: n • (n + 1) l + 2 + 3 + --- + n =-K—- Důkaz: i) n = 1 - dosadíme do obou stran rovnosti: 1 = ... platí2 ii) Předpokládáme platnost indukčního předpokladu: Vzorec platí pro n, tj. n • (n + 1) A odtud nyní dokážeme platnost vztahu (= chceme dokázat) pro (n + 1): (n + l)-(n + 2) l + 2 + -- - + n + (n + l)= 1 2 • Zkusme upravit levou stranu dokazované rovnosti s využitím pravé strany indukčního předpokladu (a poté převedeme na společného jmenovatele a vytkneme člen (n + 1) v čitateli): 1+ 2 + ...+ „.+(„.+!) "t" !LÍl±i)+(n+1) = "■'" + 1» + 2''" + 1» = '" + 1)2'" + 2». _ n(n+l) ~ 2 A to jsme chtěli dokázat, důkaz je hotov. S využitím platnosti vztahu pro n jsme jej dokázali pro (n + 1). 2Při tomto prvním kroku důkazu indukcí stačí dokázat platnost pro n = 1; podívejme se ovšem nyní už „mimo plán" na případy n = 2, n = 3, protože z nich bude zřejmé, jak se pak konstruuje rovnice pro obecné n: n = 2 - dosadíme do obou stran: 1 + 2 = ^ ... platí. n = 3 - dosadíme do obou stran: 1 + 2 + 3 = ^ ... platí.