Čo je dôkaz
Dôkaz je postupnosť logicky správnych krokov, ktorá z predpokladov a už dokázaných tvrdení odvodí platnosť vety. Pravdivosť nestačí „vidieť" na pár príkladoch.
Axióma
Tvrdenie pokladané za zrejmé — nedokazuje sa.
Definícia
Presné vymedzenie nového pojmu.
Veta
Tvrdenie, ktoré dokazujeme z axióm a definícií.
Väčšina viet má tvar implikácie predpoklad ⇒ tvrdenie — „Ak (predpoklad), tak (tvrdenie)." Napr. Ak je n párne, tak n² je párne.
Axióma, definícia, veta, či hypotéza? Rozhodni a hneď uvidíš prečo.
Dôkaz a výroková logika
Každá metóda vyplýva z toho, kedy je implikácia pravdivá, a z dvoch platných úsudkov z Výrokov. Toto je srdce celej témy.
Implikácia A ⇒ B je nepravdivá jedine v prípade A platí, B neplatí (1 ⇒ 0). Všetko ostatné je pravdivé.
Z A ⇒ B a platného A vyplýva B. Priamy dôkaz je reťazec modus ponens.
Z A ⇒ B a ¬B vyplýva ¬A. Presne to robí obmena.
Pravidlo platí: „Ak je číslo deliteľné 6, tak je párne." Vyber, čo o čísle vieš — a uvidíš, čo smieš (a nesmieš) usúdiť.
Priamy dôkaz
Z predpokladu A reťazcom správnych implikácií dôjdeme k tvrdeniu B: A ⇒ … ⇒ B. Každý krok je modus ponens.
Prepni paritu čísel a, b — uvidíš paritu súčtu aj súčinu a algebraický dôvod. Toto je jadro priamych dôkazov o párnosti.
Príklad 1 — súčet dvoch párnych je párny
Príklad 2 — súčin dvoch nepárnych je nepárny
Nepriamy dôkaz (obmena)
Namiesto A ⇒ B dokážeme jeho obmenu ¬B ⇒ ¬A — tá má vždy rovnakú pravdivostnú hodnotu. Je to modus tollens.
Prepínaj A, B a sleduj: obmena drží krok s pôvodnou implikáciou v každom riadku, obrátená nie.
Príklad — ak je n² párne, tak n je párne
Z predpokladu sa vychádza ťažko, preto dokážeme obmenu: „ak je n nepárne, tak n² je nepárne."
Obmena ¬B ⇒ ¬A platí vždy spolu s A ⇒ B. Obrátená B ⇒ A nemusí platiť — nezamieňaj ich. Toto je najčastejšia chyba pri nepriamom dôkaze.
Dôkaz sporom
Predpokladáme platnosť negácie tvrdenia ¬V a logickými krokmi dôjdeme k zjavnému sporu. Negácia je teda nemožná — a preto platí V.
Klasika — √2 je iracionálne
Euklid — prvočísel je nekonečne veľa
Sporom sa hodí pri tvrdeniach „neexistuje…" alebo „je iracionálne". Vždy začni presnou negáciou tvrdenia (pozri Výroky).
Protipríklad
Na vyvrátenie tvrdenia „pre všetky …" stačí nájsť jeden prípad, kde neplatí. Súvis s Výrokmi: negácia ∀ je ∃.
Vyber „tvrdenie", dosadzuj čísla a hľadaj jediný prípad, ktorý ho zhodí. Stačí jeden — a tvrdenie padá.
Jeden potvrdzujúci prípad nie je dôkaz. „Funguje to pre 3, 5, 7…" ešte neznamená, že platí pre všetky — iba protipríklad dokáže tvrdenie vyvrátiť.
Matematická indukcia
V aktuálnom katalógu ŠPÚ (2019) sa indukcia nenachádza ani v logike, ani pri postupnostiach. Je to teda nepovinný bonus — klasická a názorná metóda navyše.
Metóda na dôkaz tvrdení platných pre všetky n ∈ ℕ. Funguje ako padajúce domino: prvé padne a každé zhodí ďalšie.
Over tvrdenie pre n = 1 — prvé domino padne.
Z platnosti pre n dokáž platnosť pre n + 1 — každé domino zhodí ďalšie.
Najprv „základný krok" (zhodí prvé), potom „indukčný krok" (spustí reťaz). Bez základného kroku sa nič nestane.
Ťahaj n — porovnaj priamy súčet s hodnotou vzorca n(n+1)/2. Vždy sedia.
Dôkaz — 1 + 2 + … + n = n(n+1)/2
Ten istý súčet sa dá odvodiť aj priamo zo vzorca pre súčet aritmetickej postupnosti — a to už v ŠPÚ je (kap. 2.2). Indukcia nie je jediná cesta.
Dôkaz — n < 2ⁿ pre všetky n ∈ ℕ
Kedy ktorú metódu
Päť postupov, jedna logická kostra každého. Voľba metódy je polovica úspechu.
| Metóda | Dokazuje | Postup | Povinné? |
|---|---|---|---|
| Priamy | A ⇒ B | reťazec implikácií z A k B | áno |
| Nepriamy | A ⇒ B | dokáž obmenu ¬B ⇒ ¬A | áno |
| Sporom | výrok V | z ¬V doveď k sporu | áno |
| Protipríklad | vyvrátenie | nájdi jeden prípad, kde neplatí | áno |
| Indukcia | ∀ n ∈ ℕ | základný + indukčný krok | bonus |
Mostíky k iným témam
Výroky (01)
Implikácia, obmena, negácia kvantifikátorov a úsudky (modus ponens/tollens) — celý základ dôkazov.
Výrazy (04)
Úpravy výrazov sú nástroj priamych dôkazov — napr. 2(k+m), 2(…)+1.
Teória čísel (03)
Párnosť, deliteľnosť, prvočísla a nesúdeliteľnosť — typické tvrdenia na dôkaz.
Pre dané tvrdenie vyber najprirodzenejšiu metódu.
Záverečný kvíz
Desať otázok naprieč celou témou. Po každej dostaneš vysvetlenie. Koľko zvládneš?
Hotovo? Vráť sa hore na ľubovoľnú sekciu cez navigáciu a zopakuj si, čo ti ešte nesedí. 💪