Nepřímé důkazy
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:
- Důkaz jednoduchého výroku sporem
- Důkaz obměněnou implikací
- Důkaz implikace sporem
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ášť.
Důkaz jednoduchého výroku sporem
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 \(\mathbf{B}\), budeme předpokládat, že platí jeho negace, tj. ¬\(\mathbf{B}\). Odvodíme řetězec pravdivých implikací: \(\mathrm{¬\mathbf{B}}\Rightarrow \mathrm{\mathrm{\mathbf{C}}\Rightarrow \mathrm{\mathrm{…}\Rightarrow \mathrm{\mathbf{B}}}}\), popř. řetězec \(\mathrm{¬\mathbf{B}}\Rightarrow \mathrm{\mathrm{\mathbf{C}}\Rightarrow \mathrm{\mathrm{…}\Rightarrow \mathrm{\mathbf{A}}}}\), kde \(\mathbf{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 \(\mathbf{B}\), tabulka má v tomto případě jen dva řádky, protože není možné, aby výroky \(\mathbf{B}\) a ¬\(\mathbf{B}\) měly stejnou pravdivostní hodnotu:
| ¬B | B | ¬B \(\Rightarrow\) B |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
Vidíme, že má-li platit implikace \(\mathrm{¬\mathbf{B}}\Rightarrow \mathrm{\mathbf{B}}\), pak musí být výrok \(\mathbf{B}\) pravdivý. Najdeme-li tedy pravdivou implikaci \(\mathrm{¬\mathbf{B}}\Rightarrow \mathrm{\mathbf{B}}\), dokážeme tím výrok \(\mathbf{B}\).
Nyní se podívejme na tabulku pro případ, kdy řetězec implikací končí nepravdivým výrokem \(\mathbf{A}\). Výrok \(\mathbf{A}\) je nepravdivý, implikace ¬B \(\Rightarrow\) A je pravdivá. Takové situaci v tabulce pravdivostních hodnot implikace odpovídá jediný řádek (modře vyznačený):
| ¬B | A | ¬B \(\Rightarrow\) 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 ¬\(\mathbf{B}\) musí být nepravdivý, a tak je pravdivý výrok \(\mathbf{B}\), který dokazujeme.
Příklad 6
Dokažte: \(\forall (n \in \mathbb{N})\): 2\(\mid\)(\(n\)\(^3\) − 11\(n\))
Řekli jsme si, že budeme předpokládat, že platí negace dokazovaného výroku. Tedy předpokládejme, že \(\exists (n \in \mathbb{N})\): 2\(∤\)(\(n\)\(^3\) − 11\(n\)). 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:
- Je-li číslo \(n\) sudé, pak jej můžeme zapsat jako 2\(k\), kde \(k\) je přirozené číslo. Dosadíme-li 2\(k\) za \(n\) do výrazu z dokazované věty, získáme (2\(k\))\(^3\) − 11(2\(k\)). Zkusíme-li tento výraz postupně upravovat, získáme výraz 8\(k\)\(^3\) − 22\(k\), což je ale číslo sudé (rozdíl dvou sudých čísel je opět sudé číslo) a to je ve sporu s naším předpokladem, že 2 nedělí \(n\)\(^3\) − 11\(n\). Právě jsme totiž zjistili, že toto číslo je sudé a tedy dělitelné dvěma.
- Je-li \(n\) liché, pak jej můžeme zapsat jako 2\(k\) − 1, kde \(k\) je opět nějaké přirozené číslo. Opět dosadíme do výrazu \(n\)\(^3\) − 11\(n\), získáme (2\(k\) − 1)\(^3\) − 11(2\(k\) − 1), což můžeme dále upravovat: 8\(k\)\(^3\) − 12\(k\)\(^2\) + 6\(k\) − 1 − 22\(k\) + 11 = 8\(k\)\(^3\) − 12\(k\)\(^2\) − 16\(k\) + 10. To je opět sudé číslo a tak se dostáváme ke stejnému sporu, jako v bodě 1. Předpokládali jsme totiž, že toto číslo není dělitelné dvěma.
V obou případech jsme došli ke sporu. To, co jsme předpokládali, tj. \(\exists (n \in \mathbb{N})\): 2\(∤\)(\(n\)\(^3\) − 11\(n\)), je tedy nepravdivý výrok, a tak platí jeho negace, což je věta, kterou jsme měli dokázat.
☒
Příklad 7
Dokažte, že číslo \(\sqrt{2}\) je iracionální (tj. nenáleží do \(\mathbb{Q}\)).
Předpokládejme, že platí \(\sqrt{2}\)\(\in\)\(\mathbb{Q}\). Z toho plyne, že číslo \(\sqrt{2}\) lze zapsat zlomkem, tedy existuje celé číslo \(p\) a přirozené číslo \(q\) tak, že \(\sqrt{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\) = \(\sqrt{2}\)\(q\). Umocníme-li tento vztah na druhou, získáme \(p\)\(^2\) = 2\(q\)\(^2\). Z toho plyne, že \(p\)\(^2\) 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\)\(\in\)\(\mathbb{Z}\) tak, že \(p\) = 2\(r\).
Dosadíme-li 2\(r\) za \(p\) do rovnosti \(p\)\(^2\) = 2\(q\)\(^2\), získáme rovnost 4\(r\)\(^2\) = 2\(q\)\(^2\), tedy 2\(r\)\(^2\) = \(q\)\(^2\). 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 \(\sqrt{2}\)\(\in\)\(\mathbb{Q}\) je nepravdivý a tedy dokazovaný výrok je pravdivý.
☒
Důkaz obměněnou implikací
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 \(\mathrm{\mathbf{A}}\Rightarrow \mathrm{\mathbf{B}}\), pak obměněnou implikací je výrok \(\mathrm{¬\mathbf{B}}\Rightarrow \mathrm{¬\mathbf{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 \(\Rightarrow\) B | ¬B \(\Rightarrow\) ¬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:
Příklad 8
Dokažte: \(\forall (n \in \mathbb{N})\): 5\(\mid\) (\(n\)\(^2\) + 1) \(\Rightarrow\) 5\(∤\)\(n\).
Nejprve zkonstruujeme obměněnou implikaci (kvantifikátor se nemění): \(\forall (n \in \mathbb{N})\): 5\(\mid\)\(n\) \(\Rightarrow\) 5\(∤\)(\(n\)\(^2\) + 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\) = 5\(k\), kde \(k\) je nějaké přirozené číslo. Nyní dosaďme (5\(k\)) za \(n\) do výrazu (\(n\)\(^2\) + 1) a pokusme se prokázat, že tak získáme číslo, které není dělitelné pěti:
\(n\)\(^2\) + 1 = (5\(k\))\(^2\) + 1 = 25\(k\)\(^2\) + 1 = 5(5\(k\)\(^2\)) + 1
Můžeme říci, že existuje přirozené číslo \(r\) takové, že 5\(k\)\(^2\) = \(r\). Pak lze psát \(n\)\(^2\) + 1 = 5\(r\) + 1. Je zřejmé, že číslo (5\(r\) + 1) není dělitelné pěti, tedy i číslo (\(n\)\(^2\) + 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.
Příklad 9
Dokažte, že pro každé přirozené číslo \(n\) platí: Jestliže je \(n\)\(^2\) 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ů: \(\forall (n \in \mathbb{N})\): 2\(\mid\)\(n\)\(^2\) \(\Rightarrow\) 2\(\mid\)\(n\).
K důkazu opět použijeme obměněnou implikaci, budeme tedy dokazovat větu: \(\forall (n \in \mathbb{N})\): 2\(∤\)\(n\) \(\Rightarrow\) 2\(∤\)\(n\)\(^2\)
Je-li \(n\) liché (tedy nedělitelné dvěma), pak je možné psát \(n\) = 2\(k\) + 1, kde \(k\) je nějaké přirozené číslo nebo nula. Zkusíme-li toto číslo umocnit na druhou, získáme:
(2\(k\) + 1)\(^2\) = 4\(k\)\(^2\) + 4\(k\) + 1 = 2(2\(k\)\(^2\) + 2\(k\)) + 1
Označíme-li přirozené číslo (2\(k\)\(^2\) + 2\(k\)) jako \(r\), zjistíme, že číslo (2\(k\) + 1)\(^2\) je rovno číslu (2\(r\) + 1), které jistě dělitelné dvěma. Tím jsme dokázali obměněnou a tedy i původní implikaci.
☒
Důkaz implikace sporem
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 \(\mathrm{\mathbf{A}}\Rightarrow \mathrm{\mathbf{B}}\), budeme dokazovat výrok \(\mathbf{A} \wedge ¬\mathbf{B}\) (který je její negací) a pokusíme se dojít ke sporu. Při negování nesmíme zapomenout znegovat také kvantifkátory.
Příklad 10
Dokažte: \(\forall (n \in \mathbb{N})\): 2\(\mid\)\(n\)\(^2\) \(\Rightarrow\) 2\(\mid\)\(n\).
Ukažme si, jak bychom mohli sporem dokázat větu z Příkladu 9. Vytvořme její negaci: \(\exists (n \in \mathbb{N})\): 2\(\mid\)\(n\)\(^2\) \(\wedge\) 2\(∤\)\(n\). Předpokládejme, že tato negace platí.
Jestliže je \(n\) liché, víme, že \(n\)\(^2\) 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 \(n\)\(^2\) je sudé. Získáváme spor, čímž je důkaz hotov.
☒
Příklad 11
Dokažte: \(\forall (n \in \mathbb{N})\): 3\(∤\)(\(n\)\(^4\) + 2) \(\Rightarrow\) 3\(\mid\)\(n\).
Opět nejdříve vytvoříme negaci dané věty: \(\exists (n \in \mathbb{N})\): 3\(∤\)(\(n\)\(^4\) + 2) \(\wedge\) 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 (3\(k\) + 1), nebo (3\(k\) + 2), kde \(k\) je přirozené číslo nebo nula. Zkusme ověřit, jak pro oba tyto zápisy vypadá číslo (\(n\)\(^4\) + 2):
- Jestliže \(n\) = 3\(k\) + 1, pak: \(n\)\(^4\) + 2 = (3\(k\) + 1)\(^4\) + 2 = 81\(k\)\(^4\) + 108\(k\)\(^3\) + 54\(k\)\(^2\) + 12\(k\) + 1 + 2 = 3(27\(k\)\(^4\) + 36\(k\)\(^3\) + 14\(k\)\(^2\) + 4\(k\) +1). Číslo (\(n\)\(^4\) + 2) je v tomto případě dělitelné třemi.
- Jestliže \(n\) = 3\(k\) + 2, pak: \(n\)\(^4\) + 2 = (3\(k\) + 2)\(^4\) + 2 = 81\(k\)\(^4\) + 216\(k\)\(^3\) + 216\(k\)\(^2\) + 96\(k\) + 16 + 2 = 3(27\(k\)\(^4\) + 72\(k\)\(^3\) + 72\(k\)\(^2\) + 32\(k\) +6). Číslo (\(n\)\(^4\) + 2) je i v tomto případě dělitelné třemi.
Vyzkoušeli jsme obě možnosti, jak číslo \(n\) může vypadat, a u obou nám vyšlo, že číslo (\(n\)\(^4\) + 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.
