Obsah oddílu

Výroková logika

Stručný přehled teorie

Výrok – Oznamovací věta, o které má smysl prohlásit, že je pravdivá (1) nebo že není pravdivá (0).

Hypotéza – Výrok, jehož pravdivostní hodnotu neznáme, zatím neznáme nebo ani znát nemůžeme.

Kvantifikovaný výrok – Výrok, který obsahuje některý z kvantifikátorů.

Kvantifikátor

• Existenční – $\exists$ (existuje aspoň jeden), $\exists!$ (existuje právě jeden)
• Obecný – $\forall$ (pro každý, pro žádný)
• Obsahující konkrétní číselný údaj n (právě n, alespoň n, nejvýš n,…)

Negace – Negace výroku $V$ je výrok $\neg V$ (, nebo V‘), který popírá pravdivostní hodnotu výroku V (např. triviální formou „Není pravda, že …“)

Pravidla pro negování výroků:

Výrok … $A$	Negace výroku … $\neg A$
… je …	… není …
… nevyřešil …	… vyřešil …
$\forall x:V(x)$ … čteme: „pro každé x platí V(x)“	$\exists x:\neg V(x)$ …“existuje aspoň jedno x, pro něž V(x) neplatí
$\exists x: V(x)$ … čteme: „existuje x, pro něž platí V(x)“	$\forall x: \neg V(x)$ …“pro žádné x neplatí V(x)“
Aspoň $n$ … je …	Nejvýš $(n-1)$ … je …
Nejvýš $n$ … je …	Alespoň $(n+1)$ … je …

Složené výroky: – souvětí vytvořená spojením jednodušších výroků pomocí logických spojek:

Poznámky:

1. Disjunkce (neboli alternativa) $A \vee B$ ... $A$ nebo $B$
   V běžném jazyce se spojka „nebo“ používá většinou ve vylučovacím významu (tedy buď platí tvrzení A, nebo platí tvrzení B).
   Ve výrokové logice probírané na gymnáziu však spojka „nebo“ vylučovací význam nemá. Jinými slovy se připouští i situace, kdy platí obě tvrzení A i B současně.
   Disjunkce dvou výroků je pravdivá právě tehdy, když je pravdivý aspoň jeden ze spojovaných výroků (jinými slovy disjunkce dvou výroků je nepravdivá pouze tehdy, když oba spojované výroky jsou nepravdivé).
   Př.:
2. Implikace $A \Rightarrow B$ ... jestliže $A$, pak $B$
   
   1. Pochopení prvního, třetího a čtvrtého řádku tabulky pravdivostních hodnot zpravidla nedělá studentům potíže. Problematický je ovšem druhý řádek. Učitel může použít při vysvětlení
      1. konkrétní jednoduché výroky, např. A:Prší., B:Silnice je mokrá.

         První řádek:	Jestliže prší (1), pak je silnice mokrá (1).	Platí … 1.
         Třetí řádek:	Jestliže neprší (0), pak je silnice mokrá (1).	Platí … 1 (déšť mohl skončit před minutou).
         Čtvrtý řádek:	Jestliže neprší (0), pak je silnice suchá (0).	Platí … 1.
         Druhý řádek (pro řadu studentů problematický):	Jestliže prší (1), pak je silnice suchá (0).	NEPLATÍ … 0.

      2. práci s pojmy pravda (1) a lež (0):

         První řádek:	Z první pravdy (1) plyne druhá pravda (1).	Platí … 1.
         Třetí řádek:	Ze lži (0) plyne pravda (1).	Platí … 1 (pravda vždy „vyhraje“).
         Čtvrtý řádek:	Z první lži (0) plyne druhá lež (0).	Platí … 1.
         Druhý řádek (pro řadu studentů problematický):	Z pravdy (1) plyne lež (0).	NEPLATÍ … 0.

   2. Obrácená implikace … $B \Rightarrow A$
      Obměněná implikace ...$\neg B \Rightarrow \neg A$ (je ekvivalentní s výrokem $A \Rightarrow B$)
      
3. Kromě uvedených existují i další spojky, které jsou předmětem důkladnějšího a podrobnějšího studia výrokové logiky. Pomocí konečného počtu spojek lze zapsat libovolný složený výrok.

Tautologie – Složený výrok, jenž je pravdivý bez ohledu na pravdivostní hodnoty výroků, z nichž je složen.

Kontradikce – žený výrok, jenž je nepravdivý bez ohledu na pravdivostní hodnoty výroků, z nichž je složen.

Negace složených výroků

Kontrola správnosti úsudků – využívá výrokovou logiku.

Met.: Předpokladem úspěšného zvládnutí výrokové logiky je výborná znalost základních operací s jednoduchými (i kvantifikovanými) a složenými výroky. Učitel musí velmi důkladně promýšlet jak obsah učiva, tak zápisy na tabuli. Důležitá je srozumitelnost, přesnost, správnost, ale i stručnost.

Před zápisem do tabulky na tabuli by měl učitel věty vyslovit a pak se studenty na základě definice rozhodovat, do kterého sloupce věta patří, proč je výrokem, jakou má pravdivostní hodnotu, proč výrokem není …

Následovat by měla krátká diskuse o větách (např.):

• X: Před dvěma miliardami let vletělo do Slunce těleso velikostí srovnatelné s Měsícem.
• Y: Ve vesmíru existuje kromě Země ještě aspoň jedna planeta, na níž je inteligentní život.

Jsou to výroky? ANO!!!! Každé z vět jednoznačně odpovídá právě jedna ze dvou možných pravdivostních hodnot. To, že je z nějakého důvodu určení této pravdivostní hodnoty nad lidské síly, nemůže věty vyřadit z rodiny výroků. Jedná se však o speciální výroky – tzv. hypotézy.

Pozn.: Dříve, než se přistoupí k negování výroků, je třeba probrat kvantifikované výroky.

Teprve nyní by se mělo přistoupit k negování výroků.

Negace jednoduchých výroků je následně třeba důkladně procvičit. Negování kvantifikovaných výroků s prvočíselnými údaji je třeba aspoň na několika prvních příkladech vizualizovat!!!

Úloha 1.3.1

Negujte:

1. Nikdo nechybí.
2. Některou tvoji radu využiji.
3. Od události uplynulo nejvýš 10 let.
4. Petr v utkání vstřelil právě 3 branky.

Met.: Následující jednoduché úlohy je třeba rovněž důkladně procvičit dřív, než se přejde k řešení složitějších složených výroků a dalších komplikovanějších úloh. Učitel by měl upozornit, že výroky, které jsou výsledkem předepsaných logických operací se zadanými výroky, nemusí vždy dávat z hlediska češtiny “správný” smysl.

Úloha 1.3.2

Vyslovte větu obrácenou, obměněnou a negaci:

1. Budeš-li schopný a ochotný, uděláš to.
2. Když se nepostaráš, Adam odjede nebo se Beata nevrátí.

Úloha 1.3.3

Negujte výroky. Určete pravdivostní hodnotu zadání.

1. Je-li číslo dělitelné čtyřmi, pak je dělitelné i dvěma.
2. Je-li trojúhelník tupoúhlý, pak není pravoúhlý.
3. Trojúhelník je pravoúhlý, právě když pro délky jeho stran platí vzorec $a^2+b^2=c^2$ .

Úloha 1.3.5

Rozhodněte, zda je výrok $K$ tautologií: $K = (\neg A \Rightarrow B) \Leftrightarrow (A \vee B)$

Závěr: Ano, jde o tautologii.

Kontrola správnosti úsudků

Úsudek je myšlenkový proces, který na základě předpokladů, jejichž pravdivostní hodnoty známe, formuluje závěry. Úsudek může být buď správný nebo nesprávný.

Met.: Princip řešení:

Sestavíme tabulku pravdivostních hodnot pro výroky a operace, které se v úloze vyskytují. Najdeme všechny řádky, které odpovídají splněným předpokladům.

• Jestliže je na všech řádcích, kde jsou splněny všechny předpoklady, splněn i závěr, pak je úsudek správný.
• Jestliže v tabulce existuje byť jen jediný řádek, na kterém jsou splněny všechny předpoklady, ale není splněn závěr, pak je úsudek nesprávný.

Pozn.: Právě poslední fáze řešení, tedy rozhodnutí o správnosti úsudku, dělá některým studentům problémy. Pokud některý student „projde úspěšně“ řešením, ale jeho odpověď zní např. „Výrok je (ne)pravdivý“ namísto „Úsudek je (ne)správný“, svědčí to o nepochopení podstaty řešeného problému.

Úloha 1.3.6

Bude-li mít Jana vyznamenání, pojede k moři.
Jana je u moře.
Je správné usoudit, že měla vyznamenání?

Úloha 1.3.7

Víme, že platí dvě následující tvrzení:

Když nesvítí A nebo nesvítí C, pak B svítí.
Když svítí A i B, pak nesvítí C.

Rozhodněte, zda je pak správný úsudek: Nesvíti-li A, pak svítí B.

Oba předpoklady jsou splněny na čtyřech řádcích: druhém, třetím, čtvrtém a šestém. A na všech těchto řádcích je splněn i závěr. Je tedy možné konstatovat, že daný úsudek je správný.

Pozn.: Jakmile zjistíme, že na některém řádku není splněný některý z předpokladů, řádek nás nezajímá a nemusíme se na něm zdržovat zjišťováním dalších pravdivostních hodnot.

Met.: Tato úloha je určitě vhodná pro to, aby student viděli více různých způsobů řešení. Obsahuje totiž pouze dva základní výroky (označme např. B … “Mám bratra” a S … “Mám sestru”), s nimiž se dá jednoduše a názorně pracovat:

• 1. způsob – úvahou “o počtu pravd” (jde o první pohled a vyřazení odpovědí “bijících do očí”). Konjunkce je pravdivá v jednom případě ze čtyř, nemůže tedy být ekvivalentní se zadanou implikací, která je pravdivá ve třech případech ze čtyř. Vyřadíme tedy výrok c).
• 2. způsob – užitím tabulky pravdivostních hodnot. Při jejím správném vyplnění bude dobře vidět, že sloupce výsledných pravdivostních hodnot pro původní větu a pro větu b) jsou stejné.
• 3. způsob – lze si všimnout, že daná věta a věta b) představují implikaci a k ní obměněnou implikaci. A ty jsou samozřejmě ekvivalentní.
• 4. způsob – užitím vhodných diagramů (např. Eulerových nebo Vennových).

Ze zadání evidentně plyne, že pole č.3 odpovídající situaci, kdy mám sestru a nemám bratra, musí být prázdné. Porovnáním diagramu se situacemi a), b), c) jednoznačně vyplyne, že ekvivalentní může být pouze věta b).

Další úlohy k procvičování

Základní poznatky

Úloha 1.3.9

Negujte:

1. Aspoň jednou nelhal.
2. Nic ti nevytýkám.
3. Potřeboval právě 5 pokusů.
4. Je mu nejvýš 10 let.

Úloha 1.3.10

Vyslovte větu obměněnou a negaci:

1. Budu-li se učit nebo číst, nepůjdu do kina.
2. Když nebude pršet, půjdu ven a nezmoknu.

Úloha 1.3.11

Negujte výroky. Určete pravdivostní hodnotu zadání. :

1. Je-li číslo dělitelné devíti, pak je dělitelné i třemi.
2. Je-li trojúhelník pravoúhlý, pak není ostroúhlý.
3. Trojúhelník je pravoúhlý, právě když pro délky jeho stran platí vzorec $a^2+b^2=c^2$ .
4. $log1000 \leq 6log\sqrt{10}$

1.4.7 - Realisticky.cz

Úloha 1.3.12

Rozhodněte, zda je výrok $K$ tautologií: $K=\neg (A \vee B)\wedge (\neg A \Rightarrow B)$

Ne, kontradikce.

Typové příklady standardní náročnosti

Úloha 1.3.13

Petr a Pavel čekají na Adama, Pepu a Cyrila.
Pavel říká: „Když přijde Adam a Pepa, přijde i Cyril.“
Petr odpoví: „Když přijde Adam a nepřijde Cyril, nepřijde ani Pepa.“
Pavel odpoví: „Vždyť říkáš totéž, co já.“

Je to pravda?

Ano.

Úloha 1.3.14

Výrok říká: Je-li objem krychle větší než 1 cm³, je její hrana delší než 1 cm.
Měřením bylo zjištěno, že hrana měří 1,2 cm.

Usoudili jsme, že objem této krychle je větší než 1 cm³. Je náš úsudek správný?

Ne.

Úloha 1.3.15

Negujte:

• $\neg A \vee (B \wedge C)$
• $[(\neg A \vee B) \Rightarrow C]\wedge (\neg B \Leftrightarrow C)$

• $ A \wedge (\neg B \vee \neg C)$
• $[((\neg A \vee B) \wedge \neg C) \vee ((\neg B \wedge \neg C)\vee(B\wedge C))$

Rozšiřující cvičení

Úloha 1.3.16

d)

Met.: Úloha je relativně jednoduchá, takže časově nejméně náročné je určitě řešení s náčrtem dvou schránek a „vyzkoušením“ umístění dopisu do první, respektive do druhé, schránky a posouzením pravdivosti jednotlivých tvrzení v prvním, respektive v druhém, případě.

Úloha 1.3.17

Neplyne a)

Úloha 1.3.18

b)

Úloha 1.3.19

Negujte: $\forall a \in Q, \forall b \in Q: (a \lt b \Rightarrow \exists c \in R - Q; a \lt c \lt b)$