Matematické důkazy Struktura matematiky a typy důkazů

Formální struktura matematiky

Přímý důkaz

Nepřímý důkaz

Matematické důkazy Struktura matematiky a typy důkazů

Petr Liška Masarykova univerzita

18.9.2014

Matematická indukce


Přímý důkaz

Nepřímý důkaz


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é?


Přímý důkaz

Nepřímý důkaz


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 ◮ deﬁnice ◮ věta ◮ tvrzení ◮ lemma

   

důkaz

  

◮ důsledek ◮ poznámka ◮ příklad


Přímý důkaz

Nepřímý důkaz


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ů, deﬁnic 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.”)


Přímý důkaz

Nepřímý důkaz


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


Přímý důkaz

Nepřímý důkaz


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.


Přímý důkaz

Nepřímý důkaz


Příklad Věta: Pro každé n ∈ N platí

1 1 1 − < 2. n n+1 n

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ů.


Přímý důkaz

Nepřímý důkaz


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í.


Přímý důkaz

Nepřímý důkaz


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é.


Přímý důkaz

Nepřímý důkaz


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.


Přímý důkaz

Nepřímý důkaz


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é.


Přímý důkaz

Nepřímý důkaz



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.


Přímý důkaz

Nepřímý důkaz



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á.


Přímý důkaz

Nepřímý důkaz


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.

Matematické důkazy Struktura matematiky a typy důkazů

Recommend Documents