🧠 Výroková logika

Ze života

O čem to je

Každý den říkáš věty se slovy „a“, „nebo“, „když…, tak…“. Většinou to stačí. Ale smlouva, pravidla soutěže nebo počítačový program musí být naprosto jednoznačné – jinak vznikne spor.

Výroková logika přesně říká, kdy je složená věta pravdivá. Používá ji matematika v důkazech, programátor v podmínkách programu i právník ve smlouvě.

Nové pojmy

VýrokVěta, o které jde jednoznačně rozhodnout, jestli je pravdivá, nebo nepravdivá. Otázka, rozkaz ani přání výrok nejsou.„Praha je hlavní město ČR.“ je výrok (pravdivý). „7 je sudé číslo.“ je také výrok (nepravdivý).
Pravdivostní hodnotaOdpověď na otázku „platí to?“. Pravda se značí 1, nepravda 0.„2 + 2 = 4“ má hodnotu 1.

Pozor na „x > 3“: dokud nevíš, co je x, nejde rozhodnout. Taková věta výrokem není. Vyzkoušej si třídění:

Negace (¬A)Opak výroku. Platí přesně tehdy, když původní výrok neplatí. Bezpečně ji vytvoříš slovy „Není pravda, že…“.A: „Venku prší.“ ¬A: „Venku neprší.“

Spojky v běžných situacích

Konjunkce (A ∧ B), „a zároveň“Pravdivá jen tehdy, když platí oba výroky.„Je mi 16 a mám řidičák na auto.“ Stačí, aby jedna část neplatila, a celé je to nepravda.
Disjunkce (A ∨ B), „nebo“Pravdivá, když platí aspoň jeden výrok – klidně i oba. Matematické „nebo“ není „buď, anebo“.„K obědu bude polévka nebo dezert.“ Když dostaneš obojí, slib platí.
Implikace (A ⇒ B), „jestliže A, pak B“Funguje jako slib. Je nepravdivá jen v jediném případě: A nastalo a B ne.Slib: „Když prší, vezmu deštník.“
Prší?Deštník?Slib porušen?
anoanone – slib dodržen
anoneano – jediné porušení
neanone – o suchu jsem nic neslíbil
nenene
Ekvivalence (A ⇔ B), „právě tehdy, když“Pravdivá, když mají oba výroky stejnou hodnotu – buď oba platí, nebo oba neplatí.„Číslo je sudé právě tehdy, když je dělitelné dvěma.“

Jak vyvrátit „všichni“ a „někdo“

Učitel řekne: „Všichni napsali úkol.“ Abys ho vyvrátil, stačí jeden žák bez úkolu. Negace tedy zní „Aspoň jeden úkol nenapsal.“ A naopak: „Někdo umí plavat“ vyvrátíš jen tak, že nikdo neumí plavat.

Je pravdivý výrok „Jestliže 2 + 2 = 5, pak je Měsíc z tvarohu.“?
Je to slib s podmínkou 2 + 2 = 5. Ta nikdy nenastane, takže slib nemůže být porušen. Implikace je pravdivá.
Napiš negaci výroku „Někdo z nás umí plavat.“
Výrok vyvrátíš, jen když neumí plavat vůbec nikdo: „Nikdo z nás neumí plavat.“
✗Negace „Všechna prvočísla jsou lichá.“ je „Žádné prvočíslo není liché.“
✓Negace je „Aspoň jedno prvočíslo není liché.“

K vyvrácení „všechna“ stačí jeden protipříklad (číslo 2). „Žádné“ tvrdí mnohem víc, než je potřeba.

∧ platí, jen když platí obojí. ∨ platí, když platí aspoň jedno. ⇒ je nepravdivá jen při „A ano, B ne“. Negace „všichni“ = „aspoň jeden ne“, negace „někdo“ = „nikdo“.

Tabulkou

O čem to je

Představ si výrok jako vypínač: buď svítí (1 = pravda), nebo nesvítí (0 = nepravda). Ze dvou vypínačů můžeš poskládat různé obvody – a výsledná žárovka svítí podle pravidla.

Místo dohadování si prostě vypíšeš všechny kombinace do tabulky. Tak to dělá i počítač: každý jeho výpočet stojí na těchto pravidlech.

Nové pojmy

VýrokTvrzení, o kterém lze rozhodnout, zda platí (1), nebo neplatí (0).„5 > 3“ je výrok s hodnotou 1.
Logická spojkaZnačka, která z jednoduchých výroků vyrobí složený: ¬ (negace, „ne“), ∧ (konjunkce, „a“), ∨ (disjunkce, „nebo“), ⇒ (implikace, „jestliže…, pak“), ⇔ (ekvivalence, „právě tehdy, když“).
Pravdivostní tabulkaTabulka, kde v každém řádku je jedna kombinace hodnot výroků a vedle výsledek. Každý výrok má 2 možnosti, takže 2 výroky dávají 2 · 2 = 4 řádky, 3 výroky 2³ = 8 řádků.

Tabulka všech spojek

ABA ∧ BA ∨ BA ⇒ BA ⇔ B
111111
100100
010110
000011
∧: jednička jen v řádku 1 a 1.
∨: nula jen v řádku 0 a 0.
⇒: nula jen v řádku A = 1, B = 0.
⇔: jednička tam, kde jsou A a B stejné.
¬A: prostě otoč hodnotu A (1 ↔ 0).
A je pravdivý, B nepravdivý. Urči A ∧ B, A ∨ B a A ⇒ B.
Najdi řádek A = 1, B = 0. Tam je A ∧ B = 0, A ∨ B = 1, A ⇒ B = 0.

Jak se neguje složený výrok

De Morganova pravidlaPři negaci složeného výroku se ∧ mění na ∨ a naopak, a každá část se zneguje.¬(A ∧ B) = ¬A ∨ ¬B

Otáčej kartičky. Zkus nejdřív sám říct, co je na zadní straně.

  • ¬(A ∧ B) – ¬A ∨ ¬B
  • ¬(A ∨ B) – ¬A ∧ ¬B
  • ¬(A ⇒ B) – A ∧ ¬B
  • ¬(všichni jsou…) – aspoň jeden není…
  • ¬(aspoň jeden je…) – žádný není…
Ověř tabulkou pro A = 1, B = 0, že ¬(A ∧ B) má stejnou hodnotu jako ¬A ∨ ¬B.
A ∧ B = 0, takže ¬(A ∧ B) = 1. Dále ¬A = 0, ¬B = 1, a 0 ∨ 1 = 1. Obě strany dávají 1. (Stejně to vyjde i v ostatních třech řádcích.)

Obměna implikace

ObměnaK implikaci A ⇒ B je to implikace ¬B ⇒ ¬A. Má vždy stejnou pravdivostní hodnotu jako původní.„Když prší, je mokro.“ → obměna „Když není mokro, neprší.“
✗Z „Když prší, je mokro.“ plyne „Když je mokro, prší.“
✓Plyne jen obměna: „Když není mokro, neprší.“

B ⇒ A (obrácená implikace) může být nepravdivá – mokro může být i od kropení. Stejnou hodnotu má jen ¬B ⇒ ¬A.

Každý výrok má hodnotu 1 nebo 0; n výroků dává 2ⁿ řádků tabulky. Negace prohazuje ∧ ↔ ∨ a „všichni“ ↔ „aspoň jeden“. Implikace má stejnou hodnotu jako její obměna ¬B ⇒ ¬A.
🧺Množiny a intervaly🔢Číselné obory