Kontrapríklad a dôkazy

Celé stáročia si Európania boli istí: všetky labute sú biele. Veď kto kedy videl inú? Milióny bielych labutí to „potvrdzovali“ každý deň.

Potom v roku 1697 priplávala holandská výprava k západnému pobrežiu Austrálie. A na rieke tam plávali čierne labute. Jediný pohľad stačil a „istá pravda“ bola preč.

Presne takto funguje matematika. Tvrdenie „každé … je …“ nedokážeš tým, že ho vyskúšaš na desiatich, sto či tisíc prípadoch. Na jeho vyvrátenie však stačí jediný prípad, ktorý nesedí. V tomto článku sa naučíš tvrdenie vyvrátiť aj dokázať.

Jedna čierna labuť stačí

Aj na internete koluje veľa „právd“, ktoré padnú na jedinom prípade.

Tvrdenie	Prípad, ktorý ho vyvráti
Všetky labute sú biele.	čierna labuť z Austrálie
Blesk nikdy neudrie dvakrát do toho istého miesta.	mrakodrap Empire State Building zasiahne blesk zhruba 20-krát za rok
Každé prvočíslo je nepárne.	číslo 2

Všimni si: nikto nemusel prezrieť všetky labute sveta. Stačila jedna čierna.

💡 Tvrdenie so slovom „každý“, „všetky“ alebo „nikdy“ je veľmi odvážne. Stačí jedna výnimka a je nepravdivé.

Kontrapríklad

Kontrapríklad je prípad, ktorý spĺňa predpoklad tvrdenia a nespĺňa jeho záver.

Obe podmienky sú dôležité. Pozri sa na tvrdenie:

Každé prirodzené číslo, ktoré je deliteľné číslom 4, je deliteľné číslom 8.

Číslo	Deliteľné 4?	Deliteľné 8?	Čo to znamená
16	áno	áno	tvrdenie len potvrdzuje
6	nie	nie	o tvrdení nič nehovorí
10	nie	nie	o tvrdení nič nehovorí
12	áno	nie	kontrapríklad

Číslo 12 tvrdenie vyvráti. Je deliteľné štyrmi, ale nie ôsmimi.

Číslo 6 tvrdenie nevyvráti. Tvrdenie hovorí len o číslach deliteľných štyrmi. Šestka do tejto skupiny vôbec nepatrí. Je to ako vyvracať vetu „všetky labute sú biele“ čiernou vranou.

⚠️ Číslo 16 tvrdenie nedokazuje. Je to len potvrdzujúci príklad. Tvrdeniu pomôže presne tak málo ako ďalšia biela labuť.

💡 Kontrapríklad je vlastne dôkaz negácie: „Existuje číslo deliteľné štyrmi, ktoré nie je deliteľné ôsmimi.“ Viac o tom v článku Negácia výrokov a kvantifikátory.

Riešený príklad 1: nájdi kontrapríklad

Pre každé reálne číslo x platí x² ≥ x.

Predpoklad: x je reálne číslo. To spĺňa každé číslo, ktoré vyberieš.
Záver: x² ≥ x. Hľadáme číslo, pre ktoré je štvorec menší ako samotné číslo.
Celé čísla nepomôžu: 2² = 4, 0² = 0, (−3)² = 9. Vždy to vyjde.
Skús číslo medzi 0 a 1, napríklad x = 0,5. Potom x² = 0,25.
Platí 0,25 < 0,5. Záver neplatí.

Číslo 0,5 je kontrapríklad. Tvrdenie je nepravdivé. ∎

💡 Keď hľadáš kontrapríklad, skús „čudné“ čísla: 0, 1, záporné čísla, zlomky, číslo 2 medzi prvočíslami.

Príklady nestačia

Možno si povieš: „Keď to vyskúšam na veľa číslach, tak to predsa platí.“ Pozri sa na toto tvrdenie:

Pre každé prirodzené číslo n je číslo n² + n + 41 prvočíslo.

Tento vzorec si všimol už matematik Leonhard Euler. Vyskúšaj ho:

n	n² + n + 41	Prvočíslo?
1	43	áno
2	47	áno
3	53	áno
10	151	áno
39	1 601	áno
40	1 681	nie

Samé prvočísla až po n = 39. To je 39 potvrdení za sebou! A potom n = 40:

40² + 40 + 41 = 40 · 41 + 41 = 41 · 41 = 1 681.

Číslo 1 681 je deliteľné číslom 41, takže nie je prvočíslo. Tridsaťdeväť potvrdení tvrdenie nedokázalo. Jeden kontrapríklad ho vyvrátil.

⚠️ Ani milión vyskúšaných čísel nie je dôkaz. Prirodzených čísel je nekonečne veľa a ty ich vyskúšaš vždy len konečne veľa.

Dokázať alebo vyvrátiť

Predstav si súd. Obžaloba musí vinu dokázať tak, aby nezostala žiadna rozumná pochybnosť. Obhajobe stačí ukázať jednu vec, ktorá obžalobu rozbije.

S tvrdením „každý“ je to rovnako. Kto ho chce dokázať, má ťažkú prácu. Kto ho chce vyvrátiť, potrebuje jediný kontrapríklad.

Tvrdenie	Ako ho dokázať	Ako ho vyvrátiť
„Každé … je …“	všeobecný dôkaz pre všetky prípady	jeden kontrapríklad
„Existuje … také, že …“	jeden vhodný príklad	všeobecný dôkaz, že taký prípad nie je

Pri tvrdení „existuje“ je to naopak. Tvrdenie „existuje párne prvočíslo“ dokážeš jedným číslom: 2.

Na všeobecný dôkaz máš tri hlavné nástroje:

priamy dôkaz — ideš od predpokladu rovno k záveru,
nepriamy dôkaz — dokážeš obmenu,
dôkaz sporom — ukážeš, že opak vedie k nezmyslu.

Priamy dôkaz

Pri priamom dôkaze implikácie A ⇒ B vyjdeš z predpokladu A. Potom krok za krokom dôjdeš k záveru B. Každý krok musí logicky vyplývať z predchádzajúcich.

Najprv si treba pojmy zapísať matematicky:

Slovami	Zápis
n je párne	n = 2k, kde k je celé číslo
n je nepárne	n = 2k + 1, kde k je celé číslo
n je deliteľné tromi	n = 3k, kde k je celé číslo

Riešený príklad 2: priamy dôkaz

Tvrdenie: Súčet dvoch nepárnych čísel je párny.

Vezmi dve ľubovoľné nepárne čísla. Nevolíš konkrétne čísla, aby dôkaz platil pre všetky.
Zapíš ich ako 2k + 1 a 2m + 1, kde k, m sú celé čísla.
Sčítaj ich: (2k + 1) + (2m + 1) = 2k + 2m + 2 = 2 · (k + m + 1).
Číslo k + m + 1 je celé. Súčet je teda dvojnásobok celého čísla.

Súčet je párny. ∎

⚠️ Použi dve rôzne písmená k a m. Keby si napísal 2k + 1 dvakrát, dokazoval by si len súčet čísla so sebou samým.

Nepriamy dôkaz — cez obmenu

Obmena B′ ⇒ A′ má rovnakú pravdivosť ako A ⇒ B (pozri Implikácia, obrátená implikácia a obmena). Ak dokážeš obmenu, dokázal si aj pôvodné tvrdenie.

Prečo by si to robil? Niekedy je cesta „odzadu“ oveľa ľahšia. Je to ako bludisko v časopise: často ho rýchlejšie vyriešiš od cieľa.

Pôvodné tvrdenie A ⇒ B	Obmena B′ ⇒ A′
Ak prší, tak je cesta mokrá.	Ak cesta nie je mokrá, tak neprší.
Ak je n² párne, tak n je párne.	Ak n nie je párne, tak n² nie je párne.

Riešený príklad 3: dôkaz obmenou

Tvrdenie: Ak je n² párne, tak n je párne (n je celé číslo).

Skús to priamo: n² = 2k. Ako sa odtiaľ dostaneš k n? Odmocnina z 2k ti nepomôže. Priama cesta je ťažká.
Zapíš obmenu. Predpoklad A: „n² je párne“, záver B: „n je párne“. Obmena B′ ⇒ A′ znie: ak n je nepárne, tak n² je nepárne.
Dokáž obmenu priamo. Nech n je nepárne, teda n = 2k + 1, kde k je celé číslo.
Umocni: n² = (2k + 1)² = 4k² + 4k + 1 = 2 · (2k² + 2k) + 1.
Číslo 2k² + 2k je celé. Takže n² má tvar „dvojnásobok celého čísla plus 1“, teda je nepárne.

Obmena platí, preto platí aj pôvodné tvrdenie. ∎

💡 Tento výsledok sa ti zíde hneď v ďalšej časti pri dôkaze, že odmocnina z 2 nie je zlomok.

Dôkaz sporom

Predstav si detektíva. Podozrivý je záhradník. Detektív uvažuje:

Predpokladajme, že vrahom je záhradník.
Potom musel byť o 21:00 v knižnici.
Lenže o 21:00 ho kamera natočila na stanici na druhom konci mesta.
Nikto nemôže byť na dvoch miestach naraz. To je spor.
Záhradník teda vrahom nie je.

Presne tak funguje dôkaz sporom. Predpokladáš, že tvrdenie neplatí. Potom ukážeš, že z toho vyplýva nezmysel — spor. Tvrdenie teda musí platiť.

Riešený príklad 4: prvočísel je nekonečne veľa

Tento dôkaz napísal už Euklides pred viac ako 2 000 rokmi.

Predpokladajme opak: prvočísel je konečne veľa. Vypíšeme ich všetky: p₁, p₂, …, pₖ.
Vytvoríme číslo N = p₁ · p₂ · … · pₖ + 1.
N je väčšie ako 1. Preto má aspoň jedného prvočíselného deliteľa. Nazvime ho p.
Podľa predpokladu je p v našom zozname. Teda p delí súčin p₁ · p₂ · … · pₖ.
Ak p delí N aj súčin, delí aj ich rozdiel. Ten je N − p₁ · p₂ · … · pₖ = 1.
Žiadne prvočíslo však nedelí číslo 1. To je spor.

Predpoklad bol nesprávny. Prvočísel je nekonečne veľa. ∎

⚠️ Dôkaz netvrdí, že samotné N je prvočíslo. Napríklad 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30 031 = 59 · 509. Spor vznikne aj tak: prvočísla 59 a 509 v zozname nie sú.

Riešený príklad 5: odmocnina z 2 nie je zlomok

Tvrdenie: √2 je iracionálne číslo.

Predpokladajme opak: √2 je racionálne. Dá sa teda zapísať ako zlomok √2 = p/q, kde p, q sú prirodzené čísla.
Zlomok môžeme vykrátiť do základného tvaru. Predpokladajme teda, že p a q sú nesúdeliteľné — nemajú spoločného deliteľa väčšieho ako 1.
Umocni rovnosť na druhú: 2 = p²/q², teda p² = 2q².
Číslo p² je párne. Podľa riešeného príkladu 3 je aj p párne: p = 2r.
Dosaď: (2r)² = 2q², teda 4r² = 2q², teda q² = 2r².
Číslo q² je párne, takže aj q je párne.
Obe čísla p a q sú párne, teda ich delí číslo 2. To je spor s tým, že sú nesúdeliteľné.

Predpoklad bol nesprávny. √2 je iracionálne. ∎

Ako začať dôkaz sporom

Dôkaz sporom stojí a padá na prvej vete. Tá musí byť presná negácia tvrdenia. Ak negáciu urobíš zle, dôkaz nič nedokáže.

Tvrdenie	Správny začiatok: predpokladajme, že …
Prvočísel je nekonečne veľa.	… prvočísel je konečne veľa.
√2 je iracionálne.	… √2 je racionálne.
Neexistuje najväčšie prirodzené číslo.	… existuje najväčšie prirodzené číslo.
Každý trojuholník má aspoň dva ostré uhly.	… existuje trojuholník, ktorý má najviac jeden ostrý uhol.
Ak je n² párne, tak n je párne.	… n² je párne a n je nepárne.

⚠️ Negácia implikácie A ⇒ B je A a B′, nie A′ ⇒ B′. Pri poslednom riadku teda predpokladáš, že predpoklad platí a záver nie.

⚠️ Negácia slova „každý“ nie je „žiadny“. Je to „existuje aspoň jeden, ktorý nie“. Pravidlá nájdeš v článku Negácia výrokov a kvantifikátory.

Najčastejšie chyby

Príklady namiesto dôkazu. „Skúsil som 5 čísel a platí to“ nie je dôkaz. Spomeň si na n² + n + 41.
Kontrapríklad, ktorý nespĺňa predpoklad. Číslo 6 nevyvráti tvrdenie o číslach deliteľných štyrmi.
Rovnaké písmeno pre rôzne čísla. Dve nepárne čísla nezapíšeš obe ako 2k + 1.
Dokazovanie obrátenej implikácie. Obrátená implikácia B ⇒ A nemá rovnakú pravdivosť ako A ⇒ B. Rovnakú pravdivosť má len obmena B′ ⇒ A′.
Zlá negácia na začiatku sporu. „Prvočísel je málo“ nie je negácia vety „prvočísel je nekonečne veľa“.
Chýbajúci záver. Po spore napíš, čo z neho vyplýva: „Predpoklad bol nesprávny, tvrdenie platí.“

V skratke

Kontrapríklad spĺňa predpoklad a nespĺňa záver. Jeden stačí na vyvrátenie tvrdenia „každý“.
Akokoľvek veľa potvrdzujúcich príkladov nie je dôkaz.
Priamy dôkaz: od predpokladu A krok za krokom k záveru B.
Nepriamy dôkaz: dokážeš obmenu B′ ⇒ A′, ktorá má rovnakú pravdivosť ako A ⇒ B.
Dôkaz sporom: predpokladáš negáciu tvrdenia a dôjdeš k nezmyslu. Negácia musí byť presná.

Skús si sám

Nájdi kontrapríklad: „Každé prvočíslo je nepárne.“
Nájdi kontrapríklad: „Ak je súčin a · b dvoch prirodzených čísel párny, tak a aj b sú párne.“
Nájdi kontrapríklad: „Pre každé reálne číslo x platí (x + 1)² = x² + 1.“
Rozhodni, či číslo 9 je kontrapríklad k tvrdeniu „Každé prirodzené číslo deliteľné šiestimi je deliteľné deviatimi.“
Dokáž priamo: súčin dvoch nepárnych čísel je nepárny.
Dokáž sporom: neexistuje najväčšie párne prirodzené číslo.

Riešenia

Číslo 2. Je to prvočíslo a je párne.
Napríklad a = 2, b = 3. Súčin 6 je párny, ale číslo 3 nie je párne.
Napríklad x = 1. Vľavo (1 + 1)² = 4, vpravo 1² + 1 = 2. Platí 4 ≠ 2. Funguje každé x okrem nuly.
Nie. Číslo 9 nie je deliteľné šiestimi, takže nespĺňa predpoklad. Kontrapríklad je napríklad 6 alebo 12: sú deliteľné šiestimi, ale nie deviatimi.
Nepárne čísla zapíš ako 2k + 1 a 2m + 1, kde k, m sú celé. Súčin je (2k + 1) · (2m + 1) = 4km + 2k + 2m + 1 = 2 · (2km + k + m) + 1. Číslo 2km + k + m je celé, takže súčin je nepárny. ∎
Predpokladajme opak: existuje najväčšie párne prirodzené číslo P. Číslo P + 2 je tiež párne prirodzené číslo a je väčšie ako P. To je spor s tým, že P je najväčšie. Najväčšie párne prirodzené číslo teda neexistuje. ∎

Precvič si

👉 Späť na začiatok: Výrok a výroková logika — úvod