Důkazy
Porozumění
Důkazy
Důkaz je formální způsob, jak doložit, že dané tvrzení je pravdivé.
Přímý důkaz je přímá cesta od pravdivých předpokladů k tvrzení, které máme dokázat. O nějakém tvrzení víme, že je pravdivé, z něj vyplývá další tvrzení atd. až z předposledního pomocného tvrzení vyplývá přímo to, co máme dokázat. A \Rightarrow B \Rightarrow \ldots \Rightarrow X
Příklad přímého důkazu – pravoúhlý trojúhelník
Dokažte: Obsah pravoúhlého trojúhelníku, který má odvěsny o délkách a a b, má obsah: \dfrac{a \cdot b}{2}
- Pravoúhlý trojúhelník má odvěsny a,b.
- Doplněním druhého shodného trojúhelníku dostaneme slepením přepon k sobě obdélník o stranách a a b.
- Obsahy trojúhelníků jsou stejné a jejich součet je obsah obdélníku. Obsah obdélníku je roven a\cdot b.
- Obsah daného trojúhelníku je polovina z obsahu vzniklého obdélníku: \dfrac{a \cdot b}{2}
Příklad přímého důkazu – dělitelnost
Dokažte: Přirozené číslo n, které je druhou mocninou nějakého lichého přirozeného čísla, dává zbytek 1 po dělení čtyřmi.
- Předpokládejme, že n je druhou mocninou nějakého lichého přirozeného čísla m. n= m^2
- Z toho, že je m liché, vyplývá, že můžeme m zapsat jako 2k+1 pro nějaké nezáporné celé číslo k.
- Potom můžeme n zapsat jako: n = (2k+1)^2
- Potom bude rovnost platit, i když pravou stranu upravíme (umocníme závorku podle vzorce (a+b)^2=a^2 +2ab+b^2 pro a=2k a b=1): n = 4k^2+4k+1
- Z toho vyplývá (vytkneme čtyřku): n= 4(k^2+k) + 1
- Proto má n zbytek 1 po dělení čtyřmi.
Nepřímý důkaz provádíme, když místo tvrzení ve tvaru implikace A \Rightarrow B dokazujeme k němu ekvivalentní tvrzení \neg B \Rightarrow \neg A (obměnu původního tvrzení).
Příklad nepřímého důkazu – sudá a lichá čísla
Dokažte: Je-li součet m a n lichý, pak aspoň jedno z čísel m,n je sudé.
- Obměna tohoto tvrzení je: „Jsou-li m, n obě lichá čísla, pak jejich součet je sudý.“
- Předpokládejme, že m, n jsou lichá čísla. Můžeme napsat jako: m=2k+1, n=2p+1
- Součet takovýchto čísel je roven: m+n=2k+1+2p+1=2k+2p+2
- Vytknutím dvojky získáme ekvivalentní vyjádření: m+n=2(k+p+1)
- Součet m+n je tedy sudé číslo.
Důkaz sporem probíhá takto: Předpokládáme, že zadané tvrzení neplatí a platí tedy jeho negace. Snažíme se odvodit z této negace nějaký nepravdivý nesmysl – tomu se říká dojít ke sporu. Pokud se nám to podaří, víme, že předpoklad byl nesprávný. Negace zadaného tvrzení neplatí, takže zadané tvrzení platí.
Příklad důkazu sporem – prvočísla
Dokažte: Prvočísel je nekonečně mnoho.
- Předpokládejme pro spor, že zadané tvrzení není pravda. Tedy, předpokládejme, že prvočísel je konečně mnoho. Označme si počet prvočísel n.
- Můžeme si prvočísla uspořádat podle velikosti a označit p_1<p_2< \ldots < p_n.
- Všechna větší čísla než p_n by tedy měla být složená čísla.
- Vezměme si následující číslo: k = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1
- k dává nenulový zbytek 1 po dělení libovolným z čísel p_1, p_2 \ldots p_n.
- Takže k není dělitelné žádným prvočíslem a zároveň je větší než p_n.
- Našli jsme číslo k, které má také vlastnost prvočísel, ale není to žádné z p_1, \ldots, p_n. To je spor s předpokladem, že p_1,\ldots, p_n jsou všechna prvočísla.
- Ke každé konečné množině prvočísel dokážeme najít další prvočíslo, které v této množině ještě není, celkově tedy prvočísel nemůže být konečně mnoho. Je jich nekonečně mnoho.
Důkaz matematickou indukcí používáme nejčastěji, když chceme nějaké tvrzení dokázat pro všechna přirozená čísla nebo pro všechna přirozená čísla větší nebo rovna nějakému n_0. Při důkazu matematickou indukcí postupujeme ve dvou krocích:
- Báze indukce – ověříme platnost tvrzení pro nejmenší číslo, pro které má tvrzení platit.
- Indukční krok – odvodíme, že z platnosti tvrzení pro n (indukčního předpokladu) vyplývá platnost tvrzení pro n+1 (tento krok může být někdy výhodné odvodit ve tvaru, kdy z platnosti tvrzení pro všechna čísla menší nebo rovna n odvodíme platnost tvrzení pro n+1).
Příklad důkazu matematickou indukcí – počet podmnožin
Dokažte: Pro každé přirozené číslo n platí, že n prvková množina má 2^n podmnožin.
- Báze indukce: Pro n=1 víme, že každá jednoprvková množina má dvě podmnožiny – prázdnou množinu a sebe samu, to odpovídá 2^1, takže báze indukce platí.
- Indukční krok:
- Předpokládejme, že každá nprvková množina má 2^n podmnožin.
- Vezměme si nějakou n+1 prvkovou množinu M a označme si jeden její prvek x.
- Kromě x je v množině M ještě n jiných prvků. Víme tedy, že množina M \setminus \{x\} má 2^n podmnožin.
- Podmnožiny M jsou dvojího typu – podmnožiny M \setminus \{x\} (neobsahují prvek x, je jich 2^n) a podmnožiny M, které obsahují prvek x.
- Podmnožiny, které obsahují prvek x získáme přesně z podmnožin M \setminus \{x\} přidáním tohoto jednoho prvku ke každé z nich. Je jich tedy také 2^n.
- Proto má (n+1)prvková množina M celkem 2^n+2^n = 2^{n+1} podmnožin.
- Dokázali jsme bázi i indukční krok, takže zadané tvrzení platí pro každé přirozené číslo n.
