Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Matematické důkazy Struktura matematiky a typy důkazů Petr Liška Masarykova univerzita 18.9.2014 Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Motto: Matematika je tvořena z 50 procent formulemi, z 50 procent důkazy a z 50 procent představivostí. Euklidovská geometrie Jedná se (nejspíše) o první ucelený systém matematické teorie (viz Základy, asi 300 př.n.l.; Eukleides, asi 325–260 př.n.l). Byla založena na 5 postulátech: 1) každé dva různé body spojuje jediná přímka 2) každou úsečku lze prodloužit na přímku 3) lze sestrojit kružnici s libovolným poloměrem a se středem v libovolném bodě 4) všechny pravé úhly jsou shodné 5) jestliže přímka p protíná další přímky q, r a vytváří s nimi na své jedné straně vnitřní úhly, jejichž součet je menší dva úhly pravé, pak se na této straně přímky p přímky q, r protínají. Na základě těchto postulátů lze logicky odvodit celou řadu známých tvrzení. Jsou všechny axiomy nutné? Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Motto: Nejkrásnější chvíle v životě matematika jsou ty po dokončení důkazu, avšak předtím než objeví chybu. Struktura matematic- kého textu ◮ axióm ◮ definice ◮ věta ◮ tvrzení ◮ lemma ◮ důsledek    důkaz ◮ poznámka ◮ příklad Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Axiom matematický výrok, který je považován za pravdivý a nedokazuje se (v matematice též postulát, v řecké matematice se tyto pojmy rozlišovaly) Věta pravdivý (netriviální) výrok, který je odvozen na základě axiomů, definic a dříve dokázaných vět (slabší výroky: tvrzení, lemma, důsledek, . . . ) Důkaz posloupnost “formulí” taková, že každý člen této posloupnosti je buď axiomem nebo tautologií Tautologie: vždy pravdivý složený výrok (P ⇔ P; P ∨ ¬P; ¬¬P ⇔ P) Kontradikce (oxymóron): vždy nepravdivý složený výrok (kulatý čtverec; Karel Hynek Mácha /Máj/: “Mrtvé milenky cit, zbortěné harfy tón.”) Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Tvary matematických vět ◮ obecná věta „∀x ∈ M : V (x)“ ◮ existenční věta „∃x ∈ M : V (x)“ (příp. „∃! x ∈ M : V (x)“) ◮ implikace „∀x ∈ M : A(x) ⇒ B(x)“ (A...předpoklad, B...závěr; A...nutná podmínka, B...postačující podmínka) ◮ ekvivalence „A(x) ⇔ B(x)“ neboli „A(x) ⇒ B(x) ∧ A(x) ⇐ B(x)“ (často věty typu: „Jestliže platí P, pak tvrzení A1, A2, . . . An jsou ekvivalentní“; důkaz obvykle A1 ⇒ A2 ⇒ · · · ⇒ An ⇒ A1, přičemž nezáleží na pořadí) Metody matematických důkazů ◮ přímý důkaz (T.: A ⇒ B. D.: A ⇒ A1 ⇒ · · · ⇒ B) ◮ nepřímý důkaz • obměna (kontrapozice): A ⇒ B ⇐⇒ ¬B ⇒ ¬A • spor: A ⇒ B ⇐⇒ ¬(A ∧ ¬B) ◮ matematická indukce Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Přímý důkaz Přímý důkaz Důkaz tvrzení A ⇒ B pomocí posloupnosti přijatých axiomů a/nebo vět ve tvaru Ai ⇒ Ai+1, i = 0, . . . , n, kde A0 = A a An+1 = B, tj. A = A0 ⇒ A1 ⇒ A2 ⇒ · · · ⇒ An−1 ⇒ An ⇒ An+1 = B. Je tedy potřeba najít „jednodušší tvrzení“ (mezikroky). Taková metoda uvažování se nazývá deduktivní. Příklad Věta: Nechť m ∈ Z je sudé a p ∈ Z. Potom součin mp ∈ Z je sudé číslo. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Příklad Věta: Pro každé n ∈ N platí 1 n − 1 n + 1 < 1 n2 . Příklad Dokažte, že v každém čtverci s rozměry 10 × 10 cm, kde je zakresleno 101 různých bodů, existuje trojúhelník o obsahu 1 cm2 , který obsahuje alespoň dva z daných bodů. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Nepřímý důkaz A ⇒ B obrácená (opačná) implikace obměněná implikace (kontrapozice) Opačné tvrzení Uvažujme tvrzení P : A ⇒ B (tj.: jestliže platí předpoklad A, pak je splněn závěr B). Opačné tvrzení k P je výrok B ⇒ A, které zaměňuje předpoklad a závěr tvrzení. Příklad Zcela přirozeně platí, že, je-li tvrzení P pravdivé, pak opačný výrok nemusí být splněn. Např.: A: studuji na ESF MU (n je prvočíslo větší než 2) B: mám přístup do IS MU (n je liché číslo) Pak tvrzení A ⇒ B je pravdivé, ale opačné tvrzení B ⇒ A již pravdivé být nemusí. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Nepřímý důkaz Ekvivalence Jestliže tvrzení A ⇒ B i opačné tvrzení B ⇒ A jsou obě pravdivá, řekneme, že A platí tehdy a jen tehdy, když (právě tehdy, když) platí B (nebo „A je ekvivalentní B“), a píšeme A ⇔ B. Příklad A: n je sudé prvočíslo B: n = 2 Příklad Dokažte, že číslo n ∈ N je sudé právě tehdy, když číslo n2 je sudé. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Nepřímý důkaz Obměna Tvrzení ¬B ⇒ ¬A se nazývá obměnou (též kontrapozicí) tvrzení A ⇒ B. Z výrokové logiky plyne, že (A ⇒ B) ⇐⇒ (¬B ⇒ ¬A) Příklad Tvrzení: Jestliže mám uspět u zkoušky z mikroekonomie, věnuji svoji pozornost i matematice. Obměna: Jestliže nevěnuji svoji pozornost i matematice, neuspěji u zkoušky z mikroekonomie. Příklad Jestliže p ∈ N je prvočíslo větší než 2, pak p je liché. Příklad Pro libovolné prvočíslo p platí: p | n2 ⇒ p | n. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Nepřímý důkaz Spor Obměnou jsme ukázali, že tvrzení A ⇒ B je platné právě tehdy, když tvrzení ¬B ⇒ ¬A je platné. Tuto myšlenku můžeme rozšířit:pravdivost závěru B můžeme potvrdit tak, že budeme uvažovat všechny alternativy k B. Pokud všechna taková tvrzení povedou ke sporu se základními axiomy nebo známými tvrzeními, musí být závěr B pravdivý. Takovému způsobu se říká důkaz sporem (reductio ad absurdum). Chceme vlastně ukázat, že neplatí A ∧ ¬B (tj. A ⇒ B ⇐⇒ ¬(A ∧ ¬B)). Příklad Neexistuje nejmenší kladné racionální číslo. Příklad Číslo √ 2 je iracionální. Příklad Jestliže číslo p je prvočíslo větší než 2, pak číslo p je liché. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Matematická indukce Motivace Uvažujme skupinu 100 mužů seřazených za sebou do řady. Každý zašeptá své jméno muži za sebou, přičemž my víme pouze dvě věci: (∗) první muž v řadě se jmenuje David (+) přímo za každým mužem, který se jmenuje David, stojí jiný muž se jménem David. Z toho můžeme vyvodit, že všichni muži mají jméno David. Proč? Dle (∗) víme, že první muž je David (+) =⇒ za ním stojí také David (+) =⇒ . . . (+) =⇒ poslední muž v řade je David. I kdyby byl počet mužů v řadě nekonečný a výroky (∗), (+) by byly pravdivé, mohli bychom stále tvrdit, že všichni muži se jmenují David. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Matematická indukce Jak to funguje? Uvažujme řadu výroků očíslovanou přirozenými čísly tak, že první tvrzení je P(1), druhé tvrzení je P(2), . . . , n-té tvrzení je P(n). Předpokládejme, že o těchto výrocích můžeme dokázat: 1) výrok P(1) je splněn (tzv. báze nebo základ indukce) 2) kdykoli je platné tvrzení P(k) pro nějaké k ∈ N (tzv. indukční předpoklad), pak platí také P(k + 1) (tzv. indukční krok). Chceme vlastně ukázat, že z platnosti výroků P(1) ∧ P(2) ∧ · · · ∧ P(k) plyne P(k + 1) Potom můžeme snadno dospět k závěru, že všechna tvrzení jsou pravdivá. Formální struktura matematiky Přímý důkaz Nepřímý důkaz Matematická indukce Matematická indukce Příklad Pro n ∈ N platí: 1 + 2 + 3 + · · · + n = n(n+1) 2 . Příklad Součet prvních n lichých přirozených čísel je n2 , tj. 1 + 3 + 5 + · · · + (2n − 1) = n2 . Příklad Pro každé n ≥ 1 je při současném hodu n kostkami stejná pravděpodobnost toho, že výsledný součet bude sudý nebo lichý. Příklad Každé přirozené číslo větší než 1 může být vyjádřeno jako součin prvočísel. Příklad V každém stádu o n ≥ 1 koních mají všichni koně stejnou barvu.