Pojem důkazu
Co je důkaz?
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\) \(\cup\) (\(A \cap C\))] \(\cup\) [\(A\) \(\cup\) [\(B\) \(\cap\) (\(A\cup B\))]] = \(A\) \(\cup\) \(B\cup 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.
Jaké věty dokazujeme?
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.
