Protipříklad a důkazy

Celá staletí měli Evropané jasno: všechny labutě jsou bílé. Kdo by kdy viděl jinou? Miliony bílých labutí to každý den „potvrzovaly“.

Pak v roce 1697 doplula nizozemská výprava k západnímu pobřeží Austrálie. A na tamní řece plavaly černé labutě. Stačil jeden pohled a „jistá pravda“ byla pryč.

Přesně tak funguje matematika. Tvrzení „každé … je …“ nedokážeš tím, že ho vyzkoušíš na deseti, stu nebo tisíci případech. K jeho vyvrácení ale stačí jediný případ, který nesedí. V tomto článku se naučíš tvrzení vyvrátit i dokázat.

---

Obsah

• Jedna černá labuť stačí
• Protipříklad
• Příklady nestačí
• Dokázat, nebo vyvrátit
• Přímý důkaz
• Nepřímý důkaz — přes obměnu
• Důkaz sporem
• Jak začít důkaz sporem
• Nejčastější chyby
• Ve zkratce
• Zkus si sám
• Řešení
• Procvič si

---

Jedna černá labuť stačí

I na internetu koluje spousta „pravd“, které padnou na jediném případu.

Všimni si: nikdo nemusel prohlédnout všechny labutě světa. Stačila jedna černá.

💡 Tvrzení se slovem „každý“, „všechny“ nebo „nikdy“ je hodně odvážné. Stačí jedna výjimka a je nepravdivé.

---

Protipříklad

Protipříklad je případ, který splňuje předpoklad tvrzení a nesplňuje jeho závěr.

Obě podmínky jsou důležité. Podívej se na tvrzení:

Každé přirozené číslo, které je dělitelné číslem 4, je dělitelné číslem 8.

Číslo 12 tvrzení vyvrátí. Je dělitelné čtyřmi, ale ne osmi.

Číslo 6 tvrzení nevyvrátí. Tvrzení mluví jen o číslech dělitelných čtyřmi. Šestka do této skupiny vůbec nepatří. Je to jako vyvracet větu „všechny labutě jsou bílé“ černou vránou.

⚠️ Číslo 16 tvrzení nedokazuje. Je to jen potvrzující příklad. Tvrzení pomůže přesně tak málo jako další bílá labuť.

💡 Protipříklad je vlastně důkaz negace: „Existuje číslo dělitelné čtyřmi, které není dělitelné osmi.“ Více v článku Negace výroků a kvantifikátory.

Řešený příklad 1: najdi protipříklad

Pro každé reálné číslo x platí x² ≥ x.

1. Předpoklad: x je reálné číslo. To splňuje každé číslo, které vybereš.
2. Závěr: x² ≥ x. Hledáme číslo, jehož druhá mocnina je menší než samotné číslo.
3. Celá čísla nepomůžou: 2² = 4, 0² = 0, (−3)² = 9. Vždycky to vyjde.
4. Zkus číslo mezi 0 a 1, třeba x = 0,5. Pak x² = 0,25.
5. Platí 0,25 < 0,5. Závěr neplatí.

Číslo 0,5 je protipříklad. Tvrzení je nepravdivé. ∎

💡 Když hledáš protipříklad, zkoušej „podivná“ čísla: 0, 1, záporná čísla, zlomky, mezi prvočísly dvojku.

---

Příklady nestačí

Možná si řekneš: „Když to vyzkouším na hodně číslech, tak to přece platí.“ Podívej se na tohle tvrzení:

Pro každé přirozené číslo n je číslo n² + n + 41 prvočíslo.

Tohoto vzorce si všiml už matematik Leonhard Euler. Vyzkoušej ho:

Samá prvočísla až do n = 39. To je 39 potvrzení za sebou! A pak n = 40:

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

Číslo 1 681 je dělitelné číslem 41, takže to není prvočíslo. Třicet devět potvrzení tvrzení nedokázalo. Jeden protipříklad ho vyvrátil.

⚠️ Ani milion vyzkoušených čísel není důkaz. Přirozených čísel je nekonečně mnoho a ty jich vyzkoušíš vždycky jen konečně mnoho.

---

Dokázat, nebo vyvrátit

Představ si soud. Obžaloba musí vinu prokázat tak, aby nezbyla žádná rozumná pochybnost. Obhajobě stačí ukázat jednu věc, která obžalobu rozbije.

S tvrzením „každý“ je to stejné. Kdo ho chce dokázat, má těžkou práci. Kdo ho chce vyvrátit, potřebuje jediný protipříklad.

U tvrzení „existuje“ je to naopak. Tvrzení „existuje sudé prvočíslo“ dokážeš jedním číslem: 2.

Na obecný důkaz máš tři hlavní nástroje:

• přímý důkaz — jdeš od předpokladu rovnou k závěru,
• nepřímý důkaz — dokážeš obměnu,
• důkaz sporem — ukážeš, že opak vede k nesmyslu.

---

Přímý důkaz

Při přímém důkazu implikace A ⇒ B vyjdeš z předpokladu A. Pak krok za krokem dojdeš k závěru B. Každý krok musí logicky plynout z předchozích.

Nejdřív si pojmy zapiš matematicky:

Řešený příklad 2: přímý důkaz

Tvrzení: Součet dvou lichých čísel je sudý.

1. Vezmi dvě libovolná lichá čísla. Nevolíš konkrétní čísla, aby důkaz platil pro všechna.
2. Zapiš je jako 2k + 1 a 2m + 1, kde k, m jsou celá čísla.
3. Sečti je: (2k + 1) + (2m + 1) = 2k + 2m + 2 = 2 · (k + m + 1).
4. Číslo k + m + 1 je celé. Součet je tedy dvojnásobek celého čísla.

Součet je sudý. ∎

⚠️ Použij dvě různá písmena k a m. Kdybys napsal dvakrát 2k + 1, dokazoval bys jen součet čísla se sebou samým.

---

Nepřímý důkaz — přes obměnu

Obměna B′ ⇒ A′ má stejnou pravdivost jako A ⇒ B (viz Implikace, obrácená implikace a obměna). Když dokážeš obměnu, dokázal jsi i původní tvrzení.

Proč bys to dělal? Někdy je cesta „odzadu“ mnohem snazší. Je to jako bludiště v časopise: často ho vyřešíš rychleji od cíle.

Řešený příklad 3: důkaz obměnou

Tvrzení: Jestliže je n² sudé, pak n je sudé (n je celé číslo).

1. Zkus to přímo: n² = 2k. Jak se odtud dostaneš k n? Odmocnina z 2k ti nepomůže. Přímá cesta je těžká.
2. Zapiš obměnu. Předpoklad A: „n² je sudé“, závěr B: „n je sudé“. Obměna B′ ⇒ A′ zní: jestliže n je liché, pak n² je liché.
3. Dokaž obměnu přímo. Nechť n je liché, tedy n = 2k + 1, kde k je celé číslo.
4. Umocni: n² = (2k + 1)² = 4k² + 4k + 1 = 2 · (2k² + 2k) + 1.
5. Číslo 2k² + 2k je celé. Takže n² má tvar „dvojnásobek celého čísla plus 1“, je tedy liché.

Obměna platí, proto platí i původní tvrzení. ∎

💡 Tenhle výsledek se ti bude hodit hned v další části, v důkazu, že odmocnina ze 2 není zlomek.

---

Důkaz sporem

Představ si detektiva. Podezřelý je zahradník. Detektiv uvažuje:

1. Předpokládejme, že vrahem je zahradník.
2. Pak musel být ve 21:00 v knihovně.
3. Jenže ve 21:00 ho kamera natočila na nádraží na druhém konci města.
4. Nikdo nemůže být na dvou místech zároveň. To je spor.
5. Zahradník tedy vrahem není.

Přesně tak funguje důkaz sporem. Předpokládáš, že tvrzení neplatí. Pak ukážeš, že z toho plyne nesmysl — spor. Tvrzení tedy musí platit.

Řešený příklad 4: prvočísel je nekonečně mnoho

Tento důkaz sepsal už Eukleidés před více než 2 000 lety.

1. Předpokládejme opak: prvočísel je konečně mnoho. Vypíšeme je všechna: p₁, p₂, …, pₖ.
2. Vytvoříme číslo N = p₁ · p₂ · … · pₖ + 1.
3. N je větší než 1. Proto má aspoň jednoho prvočíselného dělitele. Říkejme mu p.
4. Podle předpokladu je p v našem seznamu. Tedy p dělí součin p₁ · p₂ · … · pₖ.
5. Když p dělí N i součin, dělí i jejich rozdíl. Ten je N − p₁ · p₂ · … · pₖ = 1.
6. Žádné prvočíslo ale nedělí číslo 1. To je spor.

Předpoklad byl chybný. Prvočísel je nekonečně mnoho. ∎

⚠️ Důkaz netvrdí, že samotné N je prvočíslo. Například 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30 031 = 59 · 509. Spor vznikne i tak: prvočísla 59 a 509 v seznamu nejsou.

Řešený příklad 5: odmocnina ze 2 není zlomek

Tvrzení: √2 je iracionální číslo.

1. Předpokládejme opak: √2 je racionální. Dá se tedy zapsat jako zlomek √2 = p/q, kde p, q jsou přirozená čísla.
2. Zlomek můžeme zkrátit na základní tvar. Předpokládejme tedy, že p a q jsou nesoudělná — nemají společného dělitele většího než 1.
3. Umocni rovnost na druhou: 2 = p²/q², tedy p² = 2q².
4. Číslo p² je sudé. Podle řešeného příkladu 3 je i p sudé: p = 2r.
5. Dosaď: (2r)² = 2q², tedy 4r² = 2q², tedy q² = 2r².
6. Číslo q² je sudé, takže i q je sudé.
7. Obě čísla p a q jsou sudá, dělí je tedy číslo 2. To je spor s tím, že jsou nesoudělná.

Předpoklad byl chybný. √2 je iracionální. ∎

---

Jak začít důkaz sporem

Důkaz sporem stojí a padá s první větou. Ta musí být přesná negace tvrzení. Když negaci uděláš špatně, důkaz nic nedokáže.

⚠️ Negace implikace A ⇒ B je A a B′, ne A′ ⇒ B′. V posledním řádku tedy předpokládáš, že předpoklad platí a závěr ne.

⚠️ Negace slova „každý“ není „žádný“. Je to „existuje aspoň jeden, který ne“. Pravidla najdeš v článku Negace výroků a kvantifikátory.

---

Nejčastější chyby

• Příklady místo důkazu. „Zkusil jsem 5 čísel a platí to“ není důkaz. Vzpomeň si na n² + n + 41.
• Protipříklad, který nesplňuje předpoklad. Číslo 6 nevyvrátí tvrzení o číslech dělitelných čtyřmi.
• Stejné písmeno pro různá čísla. Dvě lichá čísla nezapíšeš obě jako 2k + 1.
• Dokazování obrácené implikace. Obrácená implikace B ⇒ A nemá stejnou pravdivost jako A ⇒ B. Stejnou pravdivost má jen obměna B′ ⇒ A′.
• Špatná negace na začátku sporu. „Prvočísel je málo“ není negace věty „prvočísel je nekonečně mnoho“.
• Chybějící závěr. Po sporu napiš, co z něj plyne: „Předpoklad byl chybný, tvrzení platí.“

---

Ve zkratce

• Protipříklad splňuje předpoklad a nesplňuje závěr. Jeden stačí k vyvrácení tvrzení „každý“.
• Sebevíc potvrzujících příkladů není důkaz.
• Přímý důkaz: od předpokladu A krok za krokem k závěru B.
• Nepřímý důkaz: dokážeš obměnu B′ ⇒ A′, která má stejnou pravdivost jako A ⇒ B.
• Důkaz sporem: předpokládáš negaci tvrzení a dojdeš k nesmyslu. Negace musí být přesná.

---

Zkus si sám

1. Najdi protipříklad: „Každé prvočíslo je liché.“
2. Najdi protipříklad: „Jestliže je součin a · b dvou přirozených čísel sudý, pak a i b jsou sudá.“
3. Najdi protipříklad: „Pro každé reálné číslo x platí (x + 1)² = x² + 1.“
4. Rozhodni, jestli je číslo 9 protipříkladem k tvrzení „Každé přirozené číslo dělitelné šesti je dělitelné devíti.“
5. Dokaž přímo: součin dvou lichých čísel je lichý.
6. Dokaž sporem: neexistuje největší sudé přirozené číslo.

---

Řešení

1. Číslo 2. Je to prvočíslo a je sudé.
2. Například a = 2, b = 3. Součin 6 je sudý, ale číslo 3 sudé není.
3. Například x = 1. Vlevo (1 + 1)² = 4, vpravo 1² + 1 = 2. Platí 4 ≠ 2. Funguje každé x kromě nuly.
4. Ne. Číslo 9 není dělitelné šesti, takže nesplňuje předpoklad. Protipříkladem je například 6 nebo 12: jsou dělitelná šesti, ale ne devíti.
5. Lichá čísla zapiš jako 2k + 1 a 2m + 1, kde k, m jsou celá. Součin je (2k + 1) · (2m + 1) = 4km + 2k + 2m + 1 = 2 · (2km + k + m) + 1. Číslo 2km + k + m je celé, takže součin je lichý. ∎
6. Předpokládejme opak: existuje největší sudé přirozené číslo P. Číslo P + 2 je také sudé přirozené číslo a je větší než P. To je spor s tím, že P je největší. Největší sudé přirozené číslo tedy neexistuje. ∎

---

Procvič si

• 🔍 Najdi protipříklad
• 🧩 Jaký je to důkaz?
• 🪜 Doplň krok důkazu
• ✏️ Negace výroku
• 🧮 Obrácená implikace a obměna

👉 Zpět na začátek: Výrok a výroková logika — úvod