V této kapitole se budeme věnovat problematice, na kterou jsme již vlastně narazili, ale nevěnovali jsme jí pozornost. V matematice totiž často formulujeme tvrzení, u nichž není na první pohled zřejmé, že jsou opravdu platná. Přesněji řečeno tvoříme výroky, u kterých nám obvykle není hned známa jejich pravdivostní hodnota. Uvažujme např. tvrzení:
„Pro každé tři množiny A, B a C platí: [C ∪ (A ∩ C)] ∪ [A ∪ [B ∩ (A ∪ B)]] = A ∪ B ∪ C.“
U takového výroku (v matematice se často používá pojem věta) na první pohled neumíme rozhodnout, zda platí. Po chvilce ověřování to však zvládneme např. s využitím Vennových diagramů (navíc tato rovnost vychází z posledního příkladu předchozí kapitoly, kde jsme ji odvodili). V předchozí kapitole jsme několikrát ověřovali i další rovnosti množinových zápisů apod. A právě o tento proces ověřování nám v této kapitole půjde. Tomuto procesu totiž v matematice říkáme důkaz a naším úkolem nyní bude ukázat si, jaké obecné principy důkazů existují a jak pomocí nich ověřit (tedy dokázat) některé věty. Pochopení smyslu důkazů je nutné k pochopení způsobu výstavby celé matematiky.
Může to být (kvantifikovaný i nekvantifikovaný) jednoduchý výrok nebo (kvantifikovaný i nekvantifikovaný) výrok složený. Způsob dokazování se podle toho bude lišit. U jednotlivých typů důkazů si ukážeme, jak jimi dokázat větu ve tvaru jednoduchého výroku a ve tvaru implikace. Co s větami, které jsou složenými výroky s jinými spojkami? Půjde-li o konjunkci, budeme dokazovat oba jí spojované výroky jako samostatné věty a má-li věta platit, musí se nám podařit dokázat oba. Obdobně budeme postupovat u disjunkce, avšak stačí nám dokázat jen jeden z výroků jí spojených, aby celá věta platila. Obvykle je však nutné dokázat oba disjunkcí spojované výroky, protože věty ve tvaru disjunkce obvykle v jednotlivých částech popisují různé varianty, které mohou nastat za různých okolností (jako příklad uveďme větu „Pro každé přirozené číslo platí, že je liché, nebo sudé.“). Ekvivalenci budeme dokazovat jako dvě implikace (ukazovali jsme si, že ekvivalenci lze nahradit konjunkcí implikací), musí opět platit obě.
Způsob dokazování se také bude lišit podle toho, zda věta obsahuje kvantifikátory a popř. jaké. Nekvantifikované výroky neobsahují proměnné a práce s nimi tak bude jiná, než u výroků, které proměnné obsahují, u nichž není možné pracovat s konkrétním objektem. Je-li věta formulována jako výrok s existenčním kvantifikátorem, stačí nalézt vhodný objekt, který tvrzení splňuje, zatímco u kvantifikátoru obecného musíme prokázat, že výrok platí pro všechny přípustné hodnoty vázané proměnné.
Ještě než se budeme věnovat jednotlivým typům důkazů, zaveďme si některé pojmy, o kterých jsme se zatím nezmínili. Tyto pojmy se budou týkat implikací, které v dokazování hrají důležitou roli.
Uvažujme implikaci A ⇒ B. Výroku A pak říkáme postačující podmínka pro B, výroku B pak říkáme nutná podmínka pro A. Proč tato pojmenování? Podívejme se na tabulku pravdivostního ohodnocení pro implikaci:
| A | B | A ⇒ B |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Zaměřme se na řádky tabulky, v nichž je pravdivá implikace A ⇒ B, neboli předpokládejme, že tato implikace je pravdivá (tento předpoklad platí až do konce odstavce, nebudeme na něj již znovu upozorňovat; příslušné řádky jsou vyznačeny modře). Vidíme, že pokud je v těchto řádcích pravdivý výrok A, je pravdivý i výrok B. Proto je A postačující podmínkou pro B (platí-li A, postačuje to pro to, abychom mohli říci, že platí i B). To ovšem nic neříká o situaci, kdy A není pravdivé. Naopak, podíváme-li se na výrok B, vidíme, že výrok A je pravdivý pouze v situaci, kdy je B také pravdivé. Nastává i situace, kdy B je pravdivé a A nikoli. Avšak nenastává situace, kdy by B bylo nepravdivé a A bylo pravdivé (to by neplatila implikace a my předpokládáme opak). Proto říkáme, že B je nutnou podmínkou pro platnost A (aby platilo A, musí nutně platit B; platnost A však není platností B zaručena).
Ukažme si vše na konkrétním příkladu. Mějme větu:
∀(n∈ℕ): 6∣n ⇒ 3∣n
Poznámka: Zápis „m∣n“ říká, že přirozené číslo m dělí přirozené číslo n, neboli číslo m je dělitelné číslem n. Chceme-li naopak zapsat, že nějaké přirozené číslo p nedělí přirozené číslo q, pak využijeme symbol „∤“ a píšeme „p∤q“.
Větu si přečtěme: „Pro každé přirozené n platí: Jestliže číslo 6 dělí n, pak také číslo 3 dělí n.“ Jde o pravdivou implikaci, z dělitelnosti šesti přímo plyne dělitelnost třemi.
Výrok ∀(n∈ℕ): 6∣n má být postačující podmínkou pro výrok ∀(n∈ℕ): 3∣n. A je tomu tak. Víme-li o nějakém (libovolně zvoleném) čísle n, že je dělitelné šesti, pak toto číslo musí být dělitelné také třemi. Naopak, dělitelnost čísla n třemi nezaručuje to, že číslo n bude dělitelné šesti. Aby však bylo dělitelné šesti, musí být dělitelné také třemi (jinak dělitelné šesti být nemůže). Dělitelnost čísla n třemi je tedy nutnou podmínkou pro dělitelnost čísla n šesti.
V tomto typu důkazu přímo dokážeme z již ověřených a známých faktů platnost dané věty. Chceme-li dokázat výrok B, základní myšlenka (známá jako odvozovací pravidlo modus ponens) je následující: Platí-li výrok A a výrok A ⇒ B, pak musí platit také výrok B. Takový postup nám může připadat zvláštní, protože doposud jsme byli zvyklí posuzovat pravdivost implikace tak, že jsme zjišťovali pravdivost jí spojovaných výroků a poté vyhodnotili pravdivost této implikace. Takovým postupem bychom však museli zjistit pravdivost výroku B dříve než pravdivost této implikace. Potom by však dokazování výroku B bylo zbytečné, byl by již dokázán. Abychom pochopili princip přímého důkazu, je nutné si připustit, že pravdivost implikace můžeme dokázat i jinak bez znalosti pravdivosti jednotlivých výroků, které spojuje.
Připomeňme si, jak vypadá tabulka pravdivostních hodnot implikace:
| A | B | A ⇒ B |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Modře je zvýrazněn jediný řádek tabulky, v němž jsou výrok A i implikace A ⇒ B zároveň pravdivé. Z tabulky je vidět, že v takové situaci musí být pravdivý i výrok B. Pokud se nám tedy podaří najít výrok A tak, že A i A ⇒ B jsou pravdivé, dokážeme tím výrok B.
Přímý důkaz jednoduchého výroku vychází z pravidla modus ponens uvedeného výše. Budeme-li dokazovat výrok B, musíme nejdříve najít nějaký výrok A, o němž víme, že je pravdivý, a dále pravdivou implikaci A ⇒ B. Takovou implikaci obvykle hned nenajdeme, ale sestavíme ji postupně z několika dílčích, u kterých víme, že jsou pravdivé, např.: A ⇒ C, C ⇒ D, D ⇒ E, E ⇒ F a F ⇒ B. Pokud jsou pravdivé všechny tyto implikace, pak i implikace A ⇒ B musí být pravdivá (to je možné ověřit nejen úvahou ale i tabulkou pravdivostních hodnot).
Podívejme se na konkrétní příklad. Máme dokázat, že platí:
√7 + √7 ≥ 1 + √7 − √7
Nyní si ukážeme přímý důkaz tohoto výroku. Musíme tedy najít nějaký pravdivý výrok a dále se pak postupnými implikacemi (také pravdivými) dostat až k dokazovanému výroku. Zkusme za počáteční výrok vzít tvrzení:
29 ≥ 28
To je jistě pravdivý výrok, můžeme s ním začít. Nyní ještě potřebujeme pravdivou implikaci. Protože pravdivost implikace 29 ≥ 28 ⇒ √7 + √7 ≥ 1 + √7 − √7 není zřejmá, budeme ji muset nahradit několika dílčími implikacemi, jak jsme již naznačili v obecném popisu přímého důkazu. První taková implikace může být třeba následující:
| 29 ≥ 28 | ⇒ | 29 − 4√7 ≥ 28 − 4√7 |
Tato implikace je také pravdivým výrokem, podívejme se, jak lze postupovat dále. Zapíšeme sérii dalších (pravdivých) implikací, které na sebe postupně navazují:
| 29 − 4√7 ≥ 28 − 4√7 | ⇒ | 29 − 4√7 ≥ 4(7 − √7) |
| 29 − 4√7 ≥ 4(7 − √7) | ⇒ | (2√7 − 1)2 ≥ 4(7 − √7) |
| (2√7 − 1)2 ≥ 4(7 − √7) | ⇒ | 2√7 − 1 ≥ 2√7 − √7 |
| 2√7 − 1 ≥ 2√7 − √7 | ⇒ | 2√7 − 1 + 8 − √7 ≥ 2√7 − √7 + 8 − √7 |
| 2√7 − 1 + 8 − √7 ≥ 2√7 − √7 + 8 − √7 | ⇒ | 7 + √7 ≥ 1 + 2√7 − √7 + 7 − √7 |
| 7 + √7 ≥ 1 + 2√7 − √7 + 7 − √7 | ⇒ | 7 + √7 ≥ 1 + 2√7 − √7 + (√7 − √7)2 |
| 7 + √7 ≥ 1 + 2√7 − √7 + (√7 − √7)2 | ⇒ | 7 + √7 ≥ (1 + √7 − √7)2 |
| 7 + √7 ≥ (1 + √7 − √7)2 | ⇒ | √7 + √7 ≥ 1 + √7 − √7 |
Pravá strana poslední implikace je náš dokazovaný výrok a uvedeným postupem jsme ho dokázali pomocí přímého důkazu. Důležité je, že jsme začali pravdivým výrokem a pokračovali sérií pravdivých implikací, které na sebe navazují (pravá strana každé implikace je levou stranou implikace následující). Přesto však při předvedení takového důkazu vyvstává řada otázek. Zkusme si odpovědět alespoň na dvě z nich: Zda je možné zjednodušit zdlouhavý zápis a především jak přijít na výchozí výrok, ze kterého začneme odvozovat implikace. Na obě otázky si odpovíme, ukážeme si na totožném zadání, jak se taková úloha skutečně řeší v praxi.
Dokažte: √7 + √7 ≥ 1 + √7 − √7
Jsme-li postaveni před takovou úlohu a chceme-li použít metodu přímého důkazu, pravděpodobně nás nenapadne, jakým pravdivým výrokem začít a jakými implikacemi dále pokračovat. Existuje ovšem způsob, jak k těmto výrokům dospět. Provedeme rozbor, tzn. budeme předpokládat, že dokazovaný výrok platí a pokusíme se z něj odvodit pravdivý výrok, který potom prohlásíme za výrok výchozí. Budeme-li postupovat ekvivalentními úpravami, můžeme pak celý postup obrátit a získat tak přímý důkaz.
Začněme tedy dokazovaným výrokem a pokusme se z něj odvodit výrok, který je pravdivý, a to ekvivalentními úpravami (v dalším textu se ještě vrátíme ke zdůvodnění použití právě těchto úprav). Máme nerovnost:
√7 + √7 ≥ 1 + √7 − √7
Umocníme obě strany na druhou (obě strany nerovnosti jsou kladné, takže tato úprava je ekvivalentní):
7 + √7 ≥ (1 + √7 − √7)2
Pravou stranu rozepíšeme podle vzorce (a + b)2:
7 + √7 ≥ 1 + 2√7 − √7 + (√7 − √7)2
Upravíme mocninu na pravé straně:
7 + √7 ≥ 1 + 2√7 − √7 + 7 − √7
Převedeme √7 na jednu stranu, sečteme, co lze, a upravíme:
2√7 − 1 ≥ 2√7 − √7
Umocníme obě strany na druhou (opět jsou obě strany kladné, díky čemuž jde o ekvivalentní úpravu):
28 − 4√7 + 1 ≥ 4(7 − √7)
Upravíme:
29 − 4√7 ≥ 28 − 4√7
K oběma stranám přičteme 4√7:
29 ≥ 28
Dopracovali jsme se k pravdivému výroku a získali jsme tak konstrukci celého důkazu. Jak je možné, že jsme získali konstrukci celého důkazu? Postupovali jsme pomocí ekvivalentních úprav a to znamená, že jsme tvořili ekvivalence. Začali jsme výrokem √7 + √7 ≥ 1 + √7 − √7 (označme jej B) a z něj ekvivalentní úpravou vytvořili výrok 7 + √7 ≥ (1 + √7 − √7)2 (označme jej C). Tímto postupem jsme vytvořili nejen výrok C, ale také ekvivalenci B ⇔ C. Tato ekvivalence je pravdivá, a to nezávisle na pravdivosti výroků B a C. Tyto výroky jsou totiž buď oba pravdivé nebo oba nepravdivé (právě díky tomu, že jeden vznikl z druhého ekvivalentní úpravou).
Máme výroky B, C a pravdivou ekvivalenci B ⇔ C. Další ekvivalentní úpravou, tentokrát výroku C, můžeme vytvořit výrok D (tj. v našem příkladě 7 + √7 ≥ 1 + 2√7 − √7 + (√7 − √7)2) a také pravdivou ekvivalenci C ⇔ D. Takto můžeme pokračovat dále a vytvořit tak řetězec pravdivých ekvivalencí B ⇔ C, C ⇔ D, D ⇔ …, … ⇔ X, X ⇔ A. Pokud se nám podaří dosáhnout výroku A, který je pravdivý (a to se nám v příkladu povedlo, tím výrokem je 29 ≥ 28), je jisté, že i všechny ekvivalencemi spojované výroky jsou pravdivé (protože je-li ekvivalence pravdivá, a jeden z jí spojovaných výroků také – výrok A, musí být pravdivý i druhý spojovaný výrok). Z toho vyplývá, že i výrok B je pravdivý, chceme-li však podat korektní přímý důkaz, musíme náš postup otočit a takto důkaz zapsat.
Víme, že ekvivalence je vlastně konjunkcí dvou implikací. Této vlastnosti nyní využijeme. Začneme výrokem A a vytvoříme sérii implikací A ⇒ X, X ⇒ …, … ⇒ D, D ⇒ C, C ⇒ B, čímž vytvoříme přímý důkaz výroku B.
Ještě než tento důkaz zapíšeme, odpovězme si na druhou otázku – jak takový zápis zkrátit. Většinou se nepoužívá zápis všech jednotlivých implikací, z nichž je důkaz složen (jak jsme to udělali v naší ukázce přímého důkazu), ale tyto implikace se zapisují schematicky A ⇒ X ⇒ Y ⇒ … ⇒ B. Takový zápis my použijeme při našem zápisu důkazu výroku √7 + √7 ≥ 1 + √7 − √7, který vychází z rozboru, jenž jsme provedli:
29 ≥ 28 ⇒
⇒ 29 − 4√7 ≥ 28 − 4√7 ⇒
⇒ 28 − 4√7 + 1 ≥ 4(7 − √7) ⇒
⇒ 2√7 − 1 ≥ 2√7 − √7 ⇒
⇒ 7 + √7 ≥ 1 + 2√7 − √7 + 7 − √7 ⇒
⇒ 7 + √7 ≥ 1 + 2√7 − √7 + (√7 − √7)2 ⇒
⇒ 7 + √7 ≥ (1 + √7 − √7)2 ⇒
⇒ √7 + √7 ≥ 1 + √7 − √7
☒
Pro přehlednost jsou jednotlivé kroky uvedeny na samostatných řádcích, mohli bychom je však samozřejmě zapisovat i do řádků za sebou. Znakem ☒ budeme označovat konec důkazu, neboli situaci, kdy jsme výrok dokázali.
Shrňme si ještě jednou, jak jsme příklad řešili. Dostali jsme za úkol dokázat nerovnost. Ekvivalentními úpravami jsme z této nerovnosti postupně vytvořili nerovnost, o níž víme, že platí (tedy je pravdivým výrokem). Následně jsme postup otočili (což můžeme učinit díky ekvivalentnosti úprav) a zapsali vlastní důkaz. Rozbor není nutné provádět vždy, avšak v situacích, jako je tato, nás rychle dovede k vlastnímu důkazu.
Podívejme se na další příklad, tentokrát již s proměnnými.
Dokažte: ∀(a, b∈ℝ): (a + b)2 = a2 + 2ab + b2
Poznamenejme, že zápis „∀(a, b∈ℝ)“ budeme brát jako zkratku za zápis „∀(a∈ℝ)∀(b∈ℝ)“. Ale vraťme se k vlastnímu důkazu:
Opět bychom mohli udělat rozbor, zkusit z daného výroku ekvivalentními úpravami odvodit pravdivý výrok a obrátit postup. Tentokrát však rozbor vynecháme a rovnou si řekneme, že je vhodné začít výrokem ∀(a, b∈ℝ): (a + b)2 = (a + b)2. Na tento výrok bychom pravděpodobně rozborem přišli a zároveň je to výrok evidentně pravdivý. Začněme s ním a pokusme se najít řetězec implikací vedoucí k dokazovanému výroku:
∀(a, b∈ℝ): (a + b)2 = (a + b)2 ⇒ ∀(a, b∈ℝ): (a + b)2 = (a + b)(a + b) ⇒
⇒ ∀(a, b∈ℝ): (a + b)2 = a2 + ab + ab + b2 ⇒ ∀(a, b∈ℝ): (a + b)2 = a2 + 2ab + b2
☒
K dokazovanému výroku jsme se dostali po několika drobných úpravách pravé strany dokazované rovnosti. Je vidět, že i tento důkaz je poněkud zdlouhavý – ačkoli upravujeme jen pravou stranu, vždy opisujeme celý výrok. Dokazujeme-li rovnost dvou výrazů přímým důkazem, často používáme způsob, kdy se pomocí vhodných úprav pokusíme jednu stranu rovnosti upravit tak, abychom získali výraz, který je na druhé straně rovnosti. I potom se jedná o přímý důkaz, přestože zde není úplně zřejmý řetězec implikací. Přesto postup takového důkazu odpovídá myšlence přímého důkazu, je to totiž jen zkrácený zápis důkazu, který zde byl předveden.
Můžeme si ale ukázat také jiný přímý důkaz téměř totožného tvrzení, který využívá geometrické představivosti. Omezíme se ale pouze na kladná reálná čísla. Máme tedy opět dokázat: ∀(a, b∈ℝ+): (a + b)2 = a2 + 2ab + b2:
Zkusme si představit čtverec, který má stranu délky (a + b). To znamená, že strana tohoto čtverce se bude skládat ze dvou úseček o délkách a a b. Obsah takového čtverce pak bude (a + b)2:
Čtverec o straně (a + b) a tedy obsahem (a + b)2
V tomto čtverci snadno najdeme dva disjunktní (tj. nepřekrývající se) čtverce, jejichž obsah je roven a2 a b2:
Čtverec o straně (a + b), uvnitř pak čtverce o stranách a a b
K pokrytí původního velkého čtverce nám chybí dva obdélníky o stranách a a b, obsah každého tohoto obdélníku je tedy ab:
∀(a, b∈ℝ+): (a + b)2 = a2 + 2ab + b2
Čtverec o obsahu (a + b)2 jsme rozdělili na čtyři obrazce a zjistili jsme obsahy těchto obrazců. Obsah celého původního čtverce (tj. (a + b)2) musí být roven součtu obsahů těchto čtyř obrazců (tj. a2 + b2 + ab + ab). Vzhledem k tomu, že délky a a b mohou být libovolná kladná reálná čísla (v tuto chvíli používáme předpoklad, že a a b jsou kladná, protože délky stran nemohou být záporné), platí ∀(a, b∈ℝ+): (a + b)2 = a2 + 2ab + b2.
☒
I takto může vypadat přímý důkaz jednoduchého výroku. Kdybychom jej chtěli přesně nasadit na schéma, které jsme si při zavádění přímého důkazu uváděli, asi bychom hledali, co je oním úvodním pravdivým výrokem, z něhož jsme vyšli. V tomto případě to může být např. výrok říkající, že obsah čtverce je roven druhé mocnině délky jeho strany, společně s poznatkem, že rozdělíme-li obrazec na několik nepřekrývajících se částí, je jeho obsah roven součtu obsahů těchto částí.
Připomeňme ještě, že všechna „ověření“ vztahů mezi množinovými zápisy, jež jsme prováděli v minulé kapitole, byly vlastně také přímé důkazy jednoduchých výroků. Nyní se však už podívejme, jak přímým důkazem dokážeme implikaci.
Implikaci dokazujeme přímým důkazem velmi podobně jako jednoduchý výrok, avšak za úvodní výrok, ze kterého vyjdeme, nebudeme brát nějaký pravdivý výrok, ale „levou stranu“ implikace. Neboli, máme-li dokázat implikaci A ⇒ B, pak vyjdeme z výroku A a vytvoříme řetězec pravdivých implikací A ⇒ C ⇒ D ⇒ … ⇒ B. Proč právě tento postup? Nejdříve si zopakujme tabulku pravdivostního ohodnocení implikace:
| A | B | A ⇒ B |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Bude-li výrok A nepravdivý, bude implikace A ⇒ B vždy pravdivá. Otázkou je, zda bude pravdivá i v případě, kdy A bude pravdivým výrokem. Pak je tato implikace pravdivá pouze v případě, že B je také pravdivým výrokem. Musíme tedy ověřit, zda vždy, když platí výrok A, bude pravdivý i výrok B. A to učiníme právě výše uvedeným postupem.
Podívejme se na tento typ důkazu opět na příkladech:
Dokažte: ∀(a∈ℕ): 2∣a ⇒ 2∣a2
Tato věta vlastně říká, že pro každé přirozené číslo platí, je-li sudé, pak i jeho druhá mocnina je sudá. Je obecně známo, že taková vlastnost platí. Ukažme si však, jak ji dokázat přímým důkazem pro implikaci.
Podle toho, jak jsme si přímý důkaz implikace zavedli, musíme vyjít z poznatku 2∣a a postupně pravdivými implikacemi dojít k tomu, že 2∣a2.
Předně si musíme uvědomit, že je-li nějaké přirozené číslo a sudé, pak existuje přirozené číslo k, které získáme jako výsledek po vydělení čísla a dvěma. Číslo a lze tedy zapsat jako součin dvojky a čísla k:
∀(a∈ℕ)∃(k∈ℕ): 2∣a ⇔ a = 2k
Využijeme tohoto zápisu čísla a k tomu, abychom ukázali, že i po umocnění zůstane dvojka jeho dělitelem. Kvantifikátory, které vážou proměnné a a k, zapíšeme na začátek následujícího řetězce implikací a tomuto zápisu budeme rozumět tak, že se kvantifikátory vztahují na celý tento řetězec:
∀(a∈ℕ)∃(k∈ℕ): a = 2k ⇒ a2 = (2k)2 ⇒ a2 = 4k2 ⇒ a2 = 2(2k2) ⇒ 2∣a2
☒
Větu jsme dokázali, navíc bychom z důkazu mohli snadno odvodit, že druhá mocnina libovolného sudého čísla je nejen číslo sudé, ale dokonce dělitelné čtyřmi. Zkusme ještě jiný příklad:
Dokažte: ∀(x, y∈ℝ): x < y ⇒ x < (x + y)/2 < y
Tato věta vlastně říká, že máme-li dvě různá reálná čísla, pak jejich artimetický průměr leží mezi nimi.
V důkazu opět musíme začít „levou stranou“ implikace. Máme dojít k „dvojité“ nerovnosti, proto si důkaz rozdělíme na dvě části, abychom mohli dokázat obě nerovnosti zvlášť. Základní myšlenka důkazu spočívá v tom, že přičteme-li k oběma stranám nerovnosti stejné číslo, nic to nezmění na platnosti této nerovnosti. Dále ještě využijeme poznatku, že vydělení obou stran nerovnosti dvojkou opět nezmění pravdivost nerovnosti. Opět také budeme chápat platnost kvantifikátoru na celou sérii implikací:
☒
Obě nerovnosti jsme dokázali odvodit a věta je tak během několika málo kroků dokázána. U obou nerovností jsme k oběma stranám výchozí nerovnosti x < y přičetli stejné číslo (v prvním případě x, v druhém y), po úpravě jsme pak obě strany vydělili dvojkou.
Dokažte, že pro libovolný trojúhelník ABC platí: Jestliže je trojúhelník ABC pravoúhlý, pak obsah čtverce nad jeho přeponou je roven součtu obsahů čtverců nad odvěsnami.
Pravdivost této věty měla být zřejmá každému, kdo již slyšel o Pythagorově větě, stejně tak by mělo být jasné, že platí i obrácená implikace. Bez důkazu bychom však o pravdivosti mluvit nemohli. Proto si jej ukažme alespoň u této implikace. A opět do důkazu zamícháme trochu geometrie.
Musíme vyjít z přepokladu, že trojúhelník ABC je pravoúhlý. Proto si takový trojúhelník narýsujme, přeponu označme c, odvěsny pak budou a a b:
Pravoúhlý trojúhelník ABC
Nyní ještě narýsujme čtverec CDEF tak, aby úsečka CA ležela na straně CD a úsečka BC ležela na straně FC. Strana čtverce musí mít délku (a + b):
Pravoúhlý trojúhelník ABC ve čtverci CDEF
Do čtverce dále dorýsujeme trojúhelníky ADG, GEH a HFB tak, aby každý z nich „zapadl“ do jednoho z rohů čtverce (viz následující obrázek). Tyto trojúhelníky jsou shodné s trojúhelníkem ABC.
Čtyři shodné trojúhelníky ve čtverci
Nyní si všimněme, že se nám uvnitř čtverce CDEF objevil čtverec AGHB. To, že se jedná opravdu o čtverec snadno ověříme. Všechny strany jsou stejně dlouhé, jejich délka je c. Zbývá ověřit velikost jeho vnitřních úhlů. Vezměme si např. ∢BAG. Je vidět, že |∢BAG| = 180° − (|∢CAB| + |∢GAD|). My ale víme, že |∢GAD| = |∢ABC|, z čehož plyne, |∢CAB| + |∢GAD| = 90°, a tedy i |∢BAG| = 90°. Velikost ostatních vniřních úhlů čtverce AGHB ověříme analogicky.
Čtverec AGHB má tedy stranu délky c a tedy obsah c2. Obsah jednotlivých pravoúhlých trojúhelníků známe také, každý z nich má obsah ab/2. Celý čtverec CDEF má obsah (a + b)2, tedy (a2 + 2ab + b2). Stejně tak ale můžeme obsah tohoto čtverce vyjádřit jako součet obsahů trojúhleníků ABC, ADG, GEH, HFB a čtverce AGHB. Sečteme-li obsahy trojúhelníků ABC, ADG, GEH a HFB, získáme výraz 2ab. Víme, že obsah čtverce CDEF je (a2 + 2ab + b2), takže čtverec AGHB musí mít obsah (a2 + b2). Víme také, že čtverec ABGH má obsah c2, tedy platí a2 + b2 = c2. Neboli, obsah čtverce nad přeponou c je roven součtu obsahů čtverců nad odvěsnami a a b.
☒
Přímý důkaz však není zdaleka jedinou důkazovou technikou. Je ale ze všech těchto technik nejpřirozenější, protože z nějakého jasného předpokladu postupně odvozujeme dokazovanou větu. Na mnoho matematických vět však tato technika nestačí a je nutné je dokazovat technikami jinými.
Další možností jak dokazovat věty, jsou nepřímé důkazy. Zde nebudeme dokazovat pravdivost věty přímo, ale „oklikou“, např. přes důkaz neplatnosti její negace. Budeme rozlišovat tyto nepřímé důkazy:
Někdy se za nepřímý důkaz označuje pouze důkaz obměněnou implikací a důkazy sporem se vyčleňují zvlášť.
U důkazu sporem nebudeme dokazovat přímo zadanou větu, ale pokusíme se dokázat její negaci. Přesněji řečeno dokážeme, že tato negace je nepravdivá, z čehož plyne, že původní věta je pravdivá. Jak dokážeme, že negace je nepravdivá? Budeme předpokládat, že tato negace platí, a odvodíme z ní spor, neboli tvrzení, které je buď v rozporu s tímto předpokladem, nebo je evidentně nepravdivé. Toto odvození budeme provádět obdobně jako přímý důkaz.
Máme-li dokázat výrok B, budeme předpokládat, že platí jeho negace, tj. ¬B. Odvodíme řetězec pravdivých implikací: ¬B ⇒ C ⇒ … ⇒ B, popř. řetězec ¬B ⇒ C ⇒ … ⇒ A, kde A je výrok, který je nepravdivý. Rozeberme si obě situace v tabulce pravdivostních hodnot (řetězec implikací zde nahradíme implikací jedinou). Začněmeme situací, kdy řetězec implikací končí výrokem B, tabulka má v tomto případě jen dva řádky, protože není možné, aby výroky B a ¬B měly stejnou pravdivostní hodnotu:
| ¬B | B | ¬B ⇒ B |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
Vidíme, že má-li platit implikace ¬B ⇒ B, pak musí být výrok B pravdivý. Najdeme-li tedy pravdivou implikaci ¬B ⇒ B, dokážeme tím výrok B.
Nyní se podívejme na tabulku pro případ, kdy řetězec implikací končí nepravdivým výrokem A. Výrok A je nepravdivý, implikace ¬B ⇒ A je pravdivá. Takové situaci v tabulce pravdivostních hodnot implikace odpovídá jediný řádek (modře vyznačený):
| ¬B | A | ¬B ⇒ A |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
Ve vyznačeném řádku je také dobře vidět, že výrok ¬B musí být nepravdivý, a tak je pravdivý výrok B, který dokazujeme.
Dokažte: ∀(n∈ℕ): 2∣(n3 − 11n)
Řekli jsme si, že budeme předpokládat, že platí negace dokazovaného výroku. Tedy předpokládejme, že ∃(n∈ℕ): 2∤(n3 − 11n). Takové číslo n musí být buď liché, nebo sudé (každé přirozené číslo je buď sudé, nebo liché). Zkusme si probrat oba tyto případy:
V obou případech jsme došli ke sporu. To, co jsme předpokládali, tj. ∃(n∈ℕ): 2∤(n3 − 11n), je tedy nepravdivý výrok, a tak platí jeho negace, což je věta, kterou jsme měli dokázat.
☒
Dokažte, že číslo √2 je iracionální (tj. nenáleží do ℚ).
Předpokládejme, že platí √2∈ℚ. Z toho plyne, že číslo √2 lze zapsat zlomkem, tedy existuje celé číslo p a přirozené číslo q tak, že √2 = p/q. Přepokládejme navíc, že jsou tato čísla nesoudělná (kdyby nebyla, stačí zlomek zkrátit, takže taková čísla musí existovat). Platí tedy, že p = √2q. Umocníme-li tento vztah na druhou, získáme p2 = 2q2. Z toho plyne, že p2 je sudé číslo. Z toho ovšem plyne, že i p je sudé číslo (tento vztah si dokážeme v Příkladu 9), tedy existuje r∈ℤ tak, že p = 2r.
Dosadíme-li 2r za p do rovnosti p2 = 2q2, získáme rovnost 4r2 = 2q2, tedy 2r2 = q2. Z toho ovšem plyne, že i číslo q je sudé, a tedy čísla p a q nejsou nesoudělná. My jsme však předpokládali, že jsou nesoudělná, a tak jsme se dostali do sporu s předpokladem, čímž jsme dokázali, že náš předpoklad √2∈ℚ je nepravdivý a tedy dokazovaný výrok je pravdivý.
☒
Tento typ důkazu lze použít pouze u vět, které jsou ve tvaru implikace, jednoduché výroky takto dokazovat nemůžeme. V kapitole o složitějších výrocích jsme si řekli, že existuje tzv. obměněná implikace, která má stejnou pravdivostní hodnotu, jako implikace původní. Máme-li implikaci A ⇒ B, pak obměněnou implikací je výrok ¬B ⇒ ¬A. Využijeme této znalosti k dokazování vět. Princip důkazu obměněnou implikací spočívá právě v tom, že místo původní věty ve tvaru implikace dokážeme její obměněnou implikaci (obvykle přímým důkazem). Protože obměněná implikace má stejnou pravdivostní hodnotu jako implikace původní, dokážeme tímto i původní implikaci. Připomeňme si ještě, jak obměněná implikace vypadá v tabulce pravdivostních hodnot:
| A | B | ¬A | ¬B | A ⇒ B | ¬B ⇒ ¬A |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 |
Znovu vidíme, že původní a obměněná implikace jsou výroky ekvivalentní, neboli pokud dokážeme jednu z těchto implikací, pak je vlastně dokážeme obě. I tento postup si ukážeme na příkladech:
Dokažte: ∀(n∈ℕ): 5∣ (n2 + 1) ⇒ 5∤n.
Nejprve zkonstruujeme obměněnou implikaci (kvantifikátor se nemění): ∀(n∈ℕ): 5∣n ⇒ 5∤(n2 + 1). Tuto větu budeme nyní dokazovat (přímým důkazem). Musíme tedy vyjít z předpokladu, že n je dělitelné pěti. Můžeme tedy psát n = 5k, kde k je nějaké přirozené číslo. Nyní dosaďme (5k) za n do výrazu (n2 + 1) a pokusme se prokázat, že tak získáme číslo, které není dělitelné pěti:
n2 + 1 = (5k)2 + 1 = 25k2 + 1 = 5(5k2) + 1
Můžeme říci, že existuje přirozené číslo r takové, že 5k2 = r. Pak lze psát n2 + 1 = 5r + 1. Je zřejmé, že číslo (5r + 1) není dělitelné pěti, tedy i číslo (n2 + 1) není dělitelné pěti. Tím jsme dokázali obměněnou implikaci a díky ní i původní větu.
☒
Vidíme, že důkaz obměněnou implikací se zde od přímého důkazu lišil pouze tím, že jsme nezačali ihned dokazovat původní větu, ale nejprve jsme z ní vytvořili obměněnou implikaci a tu teprve dokazovali.
Dokažte, že pro každé přirozené číslo n platí: Jestliže je n2 sudé, pak n je také sudé.
Budeme tedy dokazovat větu, jíž jsme využili v důkazu v Příkladu 7. Tentokrát jsme ji formulovali slovy, můžeme však přidat také symbolický zápis, jaký najdeme ve většině ostatních příkladů: ∀(n∈ℕ): 2∣n2 ⇒ 2∣n.
K důkazu opět použijeme obměněnou implikaci, budeme tedy dokazovat větu: ∀(n∈ℕ): 2∤n ⇒ 2∤n2
Je-li n liché (tedy nedělitelné dvěma), pak je možné psát n = 2k + 1, kde k je nějaké přirozené číslo nebo nula. Zkusíme-li toto číslo umocnit na druhou, získáme:
(2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1
Označíme-li přirozené číslo (2k2 + 2k) jako r, zjistíme, že číslo (2k + 1)2 je rovno číslu (2r + 1), které jistě dělitelné dvěma. Tím jsme dokázali obměněnou a tedy i původní implikaci.
☒
Důkaz obměněnou implikací není jediným způsobem, jak dokázat implikaci nepřímým důkazem. Můžeme ji také dokazovat sporem, tedy pokusíme se dokázat její negaci a dojít ke sporu. Máme-li dokázat implikaci A ⇒ B, budeme dokazovat výrok A ∧ ¬B (který je její negací) a pokusíme se dojít ke sporu. Při negování nesmíme zapomenout znegovat také kvantifkátory.
Dokažte: ∀(n∈ℕ): 2∣n2 ⇒ 2∣n.
Ukažme si, jak bychom mohli sporem dokázat větu z Příkladu 9. Vytvořme její negaci: ∃(n∈ℕ): 2∣n2 ∧ 2∤n. Předpokládejme, že tato negace platí.
Jestliže je n liché, víme, že n2 je také liché (to jsme si ukázali jako součást důkazu v Příkladu 9). To je ovšem spor s naším předpokladem, protože my jsme předpokládali, že n2 je sudé. Získáváme spor, čímž je důkaz hotov.
☒
Dokažte: ∀(n∈ℕ): 3∤(n4 + 2) ⇒ 3∣n.
Opět nejdříve vytvoříme negaci dané věty: ∃(n∈ℕ): 3∤(n4 + 2) ∧ 3∤n. Předpokládejme, že tato negace platí.
Jestliže číslo n není dělitelné třemi, může být buď ve tvaru (3k + 1), nebo (3k + 2), kde k je přirozené číslo nebo nula. Zkusme ověřit, jak pro oba tyto zápisy vypadá číslo (n4 + 2):
Vyzkoušeli jsme obě možnosti, jak číslo n může vypadat, a u obou nám vyšlo, že číslo (n4 + 2) je dělitelné třemi. My jsme však předpokládali, že toto číslo dělitelné třemi není, a tak se dostáváme ke sporu. Přepokládaný výrok tedy neplatí, ale platí jeho negace, čili výrok, jenž jsme měli dokázat.
☒
Postup u důkazu implikace sporem je tedy shodný jako u důkazu jednoduchého výroku sporem, liší se pouze tím, že předpokládáme platnost negace implikace namísto negace jednoduchého výroku.
Důkaz matematickou indukcí se používá pro věty, které se týkají (téměř) všech přirozených čísel nebo jsou na nich nějak závislé. Přesněji řečeno, používáme jej pro věty typu ∀(n∈ℕ), n ≥ n0: A(n), kde A(n) je výrokový vzorec s volnou proměnnou n reprezentující typicky nějakou vlastnost přirozených čísel a kde n0 je nějaké konkrétní přirozené číslo, od něhož výše má daná vlastnost platit. Často má A(n) platit pro každé přirozené číslo, pak je n0 = 1 a podmínku n ≥ n0 neuvádíme. Důkaz matematickou indukcí sestává ze dvou kroků:
Opravdu stačí tyto dva kroky k dokázání vět v uvedeném tvaru? Zkusme si situaci trochu rozebrat:
Mějme větu, která říká, že nějaká vlastnost platí pro všechna přirozená čísla (např. že 2∣(n3 − 11n)). V prvním kroku dokážeme, že tato věta platí pro číslo 1. Poté dokážeme, že pokud tato věta platí pro nějaké přirozené číslo k, pak platí i pro k + 1. Víme tedy, že věta platí pro číslo 1. Díky dokázané implikaci ale také dokážeme odvodit, že platí i pro dvojku (platí-li výrok A a současně A ⇒ B, pak platí i výrok B). Když víme, že platí pro dvojku, můžeme stejným způsobem odvodit, že platí i pro číslo tři, a takto bychom mohli pokračovat dále a dokázat větu pro všechna přirozená čísla. Zmiňované dva kroky tedy stačí.
Dokažte: ∀(n∈ℕ): 1 + 2 + … n = ½ · (n + 1) · n.
Prvním krokem je ověření platnosti pro číslo 1. Dosadíme tedy toto číslo do rovnosti. Levá strana bude 1, pravá strana bude ½ · 1 · (1 + 1), což je opět 1. Pro číslo 1 tedy věta platí.
Přichází na řadu indukční krok. Předpokládejme, že tato věta platí pro nějaké přirozené číslo k, tedy že pro toto k platí:
1 + 2 + … k = ½ · (k + 1) · k
Nyní musíme dokázat, že za tohoto předpokladu platí věta i pro (k + 1), tedy že platí:
1 + 2 + … k + (k + 1) = ½ · (k + 2)(k + 1).
Levá strana je 1 + 2 + … k + (k + 1). My však z našeho předpokladu víme, že 1 + 2 + … k = ½ · (k + 1) · k, a tak můžeme psát:
1 + 2 + … k + (k + 1) = ½ · (k + 1) · k + (k + 1)
Modrou barvou je naznačeno, u které části výrazu došlo k aplikaci našeho předpokladu. Pokud budeme výraz dále upravovat (vytkneme závorku (k + 1)), získáme:
½ · (k + 1) · k + (k + 1) = (k + 1)(½ · k + 1) = ½ · (k + 2)(k + 1).
Dostali jsme se od levé strany dokazované rovnosti k pravé, dokázali jsme, že platí:
1 + 2 + … k + (k + 1) = ½ · (k + 2)(k + 1).
Provedli jsme oba kroky důkazu a věta je tak dokázána.
☒
Dokažte: ∀(n∈ℕ): 2∣(n3 + 11n).
Pokud za n dosadíme 1, tvrzení platí. První krok je splněn.
Předpokládejme, že tvrzení platí pro nějaké přirozené číslo k, tedy že 2∣(k3 + 11k). Zkusme dokázat, že platí i pro (k + 1). Dosaďme tedy (k + 1) za n do výrazu (n3 + 11n):
(k + 1)3 + 11(k + 1) = k3 + 3k2 + 3k + 1 + 11k + 11 = k3 + 11k + 3k2 + 3k + 12
Modře označený výraz je podle našeho předpokladu dělitelný dvěma. Abychom prokázali, že i celý výraz (k3 + 11k + 3k2 + 3k + 12) je dělitelný dvěma, zbývá dokázat, že (3k2 + 3k + 12) je také dělitelné dvěma. Můžeme výraz ještě upravit: 3(k2 + k + 4). Číslo tři není dělitelné dvěma, musíme tedy dokázat, že číslo dvě dělí číslo (k2 + k + 4).
Je-li k sudé, jeho druhá mocnina bude také sudé číslo, takže výraz (k2 + k + 4) bude součtem tří sudých čísel, což je opět číslo sudé, a tedy dělitelné dvěma. Je-li k liché, pak jeho druhá mocnina je také liché číslo. Náš výraz tak bude součtem dvou lichých čísel (která dohromady dají číslo sudé) a jednoho čísla sudého, což je dohromady opět číslo sudé. (k2 + k + 4) je tedy jistě sudé číslo, číslo dvě dělí (k3 + 11k + 3k2 + 3k + 12). Vztah platí i pro (k + 1), věta je dokázána.
☒
Dokažte: ∀(n∈ℕ): 6∣(n3 + 5n).
Pokud za n dosadíme 1, tvrzení opět platí. První krok je splněn.
Předpokládejme, že pro nějaké přirozené číslo k platí: 6∣(k3 + 5k). Dosadíme-li za n výraz (k + 1), získáme:
(k + 1)3 + 5(k + 1) = k3 + 3k2 + 3k + 1 + 5k + 5 = k3 + 5k + 3k2 + 3k + 6
Z předpokladu víme, že 6∣(k3 + 5k). Zbývá dokázat, že 6∣(3k2 + 3k + 6). Ale 3k2 + 3k + 6 = 3(k2 + k + 2) a 6 = 2 · 3. Zbývá tedy dokázat, že 2∣(k2 + k + 2), což můžeme provést rozborem, zda je k liché nebo sudé, totožně jako v přechozím příkladu. Tím bude věta opět dokázána.
☒
Na závěr této kapitoly se ještě krátce zmiňme o tom, jaké použití mají poznatky z matematické logiky, které jsme v této i v předchozích kapitolách probrali. Vše, co jsme si zde ukazovali, slouží jako nástroj pro výstavbu matematiky ve vysokoškolském pojetí.
Vysokoškolská matematika bývá stavěna pomocí axiomů, definic, vět a důkazů.
Axiomy jsou tvrzení, u nichž je předem dáno, že musí být pravdivá. Jsou to jakési „základní kameny“ teorie, které chceme budovat. Budeme-li se např. zabývat výstavbou geometrie, budeme pravděpodobně využívat axiomu:
„Každými dvěma body v rovině je určena právě jedna přímka.“
V teorii, kde bychom chtěli používat přirozená čísla, bychom mohli použít např. axiom:
„Každé přirozené číslo má svého následníka.“
Budujeme-li nějakou část matematiky, vycházíme obvykle z několika axiomů.
Definice používáme k zavádění nových pojmů. Ukažme si definici na zavedení operace průniku množin:
„Průnikem množin A, B, který značíme A ∩ B, budeme rozumět množinu {x∈U; x∈A ∧ x∈B}.“
Věty a jejich důkazy již známe, věty slouží k popisu poznatků, které nejsou z dosavadních poznatků (axiomů a již dokázaných vět) zřejmé, důkazy pak používáme k ověření a prokázání platnosti vět.
Tímto jsme si v krátkosti nástínili základní princip výstavby vysokoškolské matematiky (a také smysl matematické logiky), hlubší probrání této tematiky je již mimo rozsah tohoto textu.
| Typ důkazu | Dokazovaný výrok | Schéma postupu důkazu |
|---|---|---|
| Přímý důkaz jednoduchého výroku | B | Vyjdeme z pravdivého výroku A a vytvoříme řetězec pravdivých implikací A ⇒ C ⇒ D ⇒ … ⇒ B. |
| Přímý důkaz implikace | A ⇒ B | Předpokládáme, že platí A a vytvoříme řetězec pravdivých implikací A ⇒ C ⇒ D ⇒ … ⇒ B. |
| Důkaz jednoduchého výroku sporem | B | Předpokládáme, že platí ¬B a vytvoříme řetězec pravdivých implikací ¬B ⇒ C ⇒ D ⇒ … ⇒ B nebo ¬B ⇒ C ⇒ D ⇒ … ⇒ A, kde A je nepravdivý výrok. |
| Důkaz obměněnou implikací | A ⇒ B | Přímým důkazem dokážeme implikaci ¬B ⇒ ¬A |
| Důkaz implikace sporem | A ⇒ B | Předpokládáme platnost konjunkce A ∧ ¬B a odvodíme spor podobně jako u důkazu jednoduchého výroku sporem. |
| Důkaz matematickou indukcí | ∀(n∈ℕ), n ≥ n0: A(n) | První krok: dokážeme A(n0). Druhý krok: dokážeme ∀(k∈ℕ): A(k) ⇒ A(k + 1). |