Výroková logika

Výroková logika pracuje s výroky: s tvrzeními, o kterých má smysl říct, jestli jsou pravdivá, nebo nepravdivá. Pravdivý výrok má pravdivostní hodnotu 1, nepravdivý 0. Z jednoduchých výroků se pomocí spojek skládají složené výroky a jejich hodnotu určuje pravdivostní tabulka. Spojky jsou čtyři a k nim negace:

`\begin{aligned}\neg A &\quad \text{negace (ne)} \\[6pt] A \wedge B &\quad \text{konjunkce (a)} \\[6pt] A \vee B &\quad \text{disjunkce (nebo)} \\[6pt] A \Rightarrow B &\quad \text{implikace (jestliže, pak)} \\[6pt] A \Leftrightarrow B &\quad \text{ekvivalence (právě když)}\end{aligned}`

Tabulku pro jakýkoli složený výrok vypíše i s mezivýsledky pravdivostní tabulka online. Hodnotu výroku, tautologie a negace s okamžitou kontrolou procvičíte v příkladech na výrokovou logiku. Výroková logika se probírá na začátku 1. ročníku střední školy spolu s množinami a její pravidla se pak používají v každém důkazu.

Co je výrok a co není

Výrok je oznamovací věta nebo matematický zápis, který je buď pravdivý, nebo nepravdivý, nic mezi tím. Nemusíme přitom vědět, která z možností platí: „Na Marsu kdysi žily bakterie“ je výrok, i když jeho pravdivost zatím nikdo nezná.

Zápis x + 2 = 5 se stane výrokem, až za x dosadíme číslo: pro x = 3 je pravdivý, pro x = 4 nepravdivý. Takovému zápisu s proměnnou se říká výroková forma. Výrokem se stane i tehdy, když řekneme, pro kolik čísel má platit, o tom je oddíl o kvantifikátorech.

Negace výroku

Negace výroku A se píše `\neg A` (v některých učebnicích A′) a tvrdí opak: je pravdivá právě tehdy, když A pravdivý není. Vždy se dá vytvořit úvodem „Není pravda, že …“, v běžné řeči se ale zápor obvykle přesune ke slovesu:

• A: „Číslo 12 je dělitelné třemi.“ `\neg A`: „Číslo 12 není dělitelné třemi.“
• A: „Venku je teplo.“ `\neg A`: „Venku není teplo.“ Negace není „Venku je zima“: může být také tak akorát, a pak by byly obě věty nepravdivé současně. Výrok a jeho negace mají vždy opačnou hodnotu.
• A: `5\gt3`. `\neg A`: `5\le3`. Negace „je větší“ je „je menší nebo rovno“, ne „je menší“.

Dvojí negace se ruší: `\neg (\neg A)` je totéž co A. „Není pravda, že číslo 12 není dělitelné třemi“ znamená, že dělitelné je.

Konjunkce, disjunkce, implikace a ekvivalence

Dva výroky A a B se dají spojit čtyřmi spojkami. Řádky tabulky jsou všechny čtyři možnosti, jakou hodnotu mají A a B, sloupce hodnota složeného výroku. Tuhle tabulku se vyplatí umět zpaměti, všechno ostatní se z ní odvodí.

• Konjunkce `A \wedge B` („A a B“, „A a zároveň B“) je pravdivá, jen když jsou pravdivé oba výroky. „Číslo 6 je sudé a dělitelné třemi“ platí. „Číslo 8 je sudé a dělitelné třemi“ neplatí, protože druhá část je nepravdivá.
• Disjunkce `A \vee B` („A nebo B“) je pravdivá, když platí aspoň jeden z výroků, tedy i když platí oba. V tom se matematické „nebo“ liší od běžné řeči: nevylučuje, že platí obojí. „Číslo 6 je sudé nebo dělitelné třemi“ je pravdivý výrok. Vylučovací „buď, anebo“, které obojí současně nepřipouští, je jiná spojka, vylučovací disjunkce.
• Implikace `A \Rightarrow B` („jestliže A, pak B“, „když A, tak B“) je nepravdivá v jediném případě: když A platí a B ne. Výroku A se říká předpoklad, výroku B závěr. Pomůže představit si slib „Když dostanu jedničku, koupím ti zmrzlinu.“ Porušený je jen tehdy, když jedničku dostanu a zmrzlinu nekoupím. Když jedničku nedostanu, slib porušený není, ať zmrzlinu koupím, nebo ne. Proto je implikace s nepravdivým předpokladem vždy pravdivá, i když zní nesmyslně: „Jestliže 2 + 2 = 5, pak je Měsíc z tvarohu“ je pravdivý výrok.
• Ekvivalence `A \Leftrightarrow B` („A právě tehdy, když B“) je pravdivá, když mají oba výroky stejnou hodnotu: oba platí, nebo oba neplatí. „Přirozené číslo je dělitelné deseti, právě když končí nulou“ platí pro každé přirozené číslo. Ekvivalence říká totéž co dvě implikace naráz, `A \Rightarrow B` a `B \Rightarrow A`.

Příklad 1

Výrok A zní „Číslo 15 je dělitelné pěti“, výrok B „Číslo 15 je sudé“. Jakou hodnotu mají `A \wedge B`, `A \vee B`, `A \Rightarrow B`, `B \Rightarrow A` a `A \Leftrightarrow B`?

Nejdřív hodnoty jednoduchých výroků: 15 = 3 · 5, takže A = 1, a 15 je liché, takže B = 0. Teď stačí najít v tabulce řádek A = 1, B = 0:

• `A \wedge B`: 0, B neplatí, konjunkce tedy také ne.
• `A \vee B`: 1, stačí, že platí A.
• `A \Rightarrow B`: 0, předpoklad platí a závěr ne, to je jediný nepravdivý případ.
• `B \Rightarrow A`: 1, předpoklad B je nepravdivý, implikace proto platí.
• `A \Leftrightarrow B`: 0, výroky mají různou hodnotu.

Jak sestavit pravdivostní tabulku

Pravdivostní tabulka složeného výroku se sestavuje vždy stejně:

1. Spočítejte proměnné. Pro n proměnných má tabulka 2ⁿ řádků: se dvěma proměnnými 4, se třemi 8.
2. Vypište všechny kombinace hodnot, ať na žádnou nezapomenete. Zvykem je v posledním sloupci proměnných střídat 1 a 0 po jedné, v předposledním po dvou, v dalším po čtyřech.
3. Přidejte sloupec pro každou část výroku, zevnitř ven: nejdřív negace jednotlivých proměnných, pak závorky, nakonec celý výrok.
4. Každý sloupec vyplňte podle tabulky spojek výše. Poslední sloupec je hodnota celého výroku.

Negace se týká jen toho, co stojí hned za ní: `\neg A \wedge B` znamená `(\neg A) \wedge B`, kdežto `\neg (A \wedge B)` neguje celou konjunkci. Ostatní spojky oddělujte závorkami, ať je jasné, co se počítá dřív.

Příklad 2

Sestavte pravdivostní tabulku výroku `\neg A \vee B`.

Proměnné jsou dvě, řádky tedy čtyři. Pomocný sloupec je `\neg A`, výsledný `\neg A \vee B` je 1 všude, kde je jednička aspoň v jednom ze sloupců `\neg A` a B:

Výsledný sloupec 1, 0, 1, 1 je stejný jako u implikace `A \Rightarrow B`. Dva výroky se stejným sloupcem jsou ekvivalentní, tedy `A \Rightarrow B` říká totéž co `\neg A \vee B`: „buď A neplatí, nebo platí B“. Porovnat dva výroky tabulkou umí kalkulačka ekvivalence dvou výroků.

Příklad 3

Kdy je pravdivý výrok `(A \wedge B) \Rightarrow C`?

Tři proměnné znamenají 2³ = 8 řádků. Pomocný sloupec je závorka `A \wedge B`:

Výrok je pravdivý v sedmi řádcích z osmi a nepravdivý jen pro A = 1, B = 1, C = 0. Kontrola bez tabulky: implikace neplatí, jen když předpoklad platí a závěr ne. Předpoklad `A \wedge B` platí jen v prvních dvou řádcích a z nich má C = 0 jen druhý. Stejnou tabulku i s mezivýsledky vypíše pravdivostní tabulka s tímto výrokem.

Tautologie a kontradikce

Výrok, který je pravdivý v každém řádku tabulky, je tautologie: platí, ať za proměnné dosadíme cokoli. Tautologiím se říká zákony výrokové logiky. Výrok nepravdivý v každém řádku je kontradikce (spor). Výrok pravdivý aspoň v jednom řádku se nazývá splnitelný, takže splnitelná je i každá tautologie. Nejjednodušší příklady:

`\begin{aligned}A \vee \neg A &\quad \text{tautologie} \\[6pt] A \wedge \neg A &\quad \text{kontradikce}\end{aligned}`

„Číslo je sudé, nebo není sudé“ platí vždy, „číslo je sudé a není sudé“ nikdy.

Příklad 4

Ověřte, že výrok `(A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)` je tautologie.

Spočítáme obě strany ekvivalence zvlášť. Levá je `A \Rightarrow B`, pro pravou potřebujeme `\neg B` a `\neg A`:

Sloupce `A \Rightarrow B` a `\neg B \Rightarrow \neg A` jsou stejné, 1, 0, 1, 1, takže ekvivalence platí ve všech čtyřech řádcích a výrok je tautologie. Kalkulačka pravdivostní tabulka má právě tento výrok nastavený jako příklad a pozná tautologii sama.

Nejdůležitější zákony, každý z nich se dá ověřit stejně:

Negace složeného výroku

Negaci složeného výroku jde vždy napsat jako „Není pravda, že …“. Ve škole se ale chce negace bez tohoto úvodu, se zápory uvnitř. K tomu slouží pravidla z tabulky zákonů:

První dva řádky jsou De Morganovy zákony. Pozor na implikaci: její negace už implikace není. Negaci ekvivalence jde zapsat i kratčeji jako `A \Leftrightarrow \neg B`. Ve větách:

• „Petr umí anglicky a hraje na kytaru.“ Negace: „Petr neumí anglicky nebo nehraje na kytaru.“
• „Ve středu půjdu do kina nebo do divadla.“ Negace: „Ve středu nepůjdu do kina ani do divadla.“ Slovo „ani“ tu znamená „a zároveň ne“.
• „Když bude pršet, vezmu si deštník.“ Negace: „Bude pršet a deštník si nevezmu.“
• „Půjdu ven, právě když bude svítit slunce.“ Negace: „Půjdu ven a slunce svítit nebude, nebo nepůjdu ven, i když slunce svítit bude.“

Příklad 5

Utvořte negaci výroku `A \Rightarrow (B \vee \neg C)` bez úvodního „není pravda, že“.

Negace se protlačí dovnitř spojku po spojce. Nejdřív negace implikace, pak De Morganův zákon pro disjunkci, nakonec dvojí negace:

`\begin{aligned}\neg (A \Rightarrow (B \vee \neg C)) &\Leftrightarrow A \wedge \neg (B \vee \neg C) \\[6pt] &\Leftrightarrow A \wedge (\neg B \wedge \neg (\neg C)) \\[6pt] &\Leftrightarrow A \wedge \neg B \wedge C\end{aligned}`

Kontrola: původní implikace je nepravdivá jen tehdy, když platí A a neplatí `B \vee \neg C`, tedy když B = 0 a C = 1. Přesně tento jediný případ popisuje výsledek `A \wedge \neg B \wedge C`. Postup krok po kroku i s ověřením tabulkou ukáže negace výroku, která má tento výrok nastavený jako příklad.

Obrácená implikace a obměna

K implikaci `A \Rightarrow B` patří dvě další: obrácená implikace `B \Rightarrow A` a obměna `\neg B \Rightarrow \neg A`. Obměna říká totéž co původní implikace, to ověřil Příklad 4. Obrácená implikace ne:

• Implikace: „Je-li číslo dělitelné šesti, je dělitelné třemi.“ Pravdivá.
• Obrácená: „Je-li číslo dělitelné třemi, je dělitelné šesti.“ Nepravdivá, stačí číslo 9.
• Obměna: „Není-li číslo dělitelné třemi, není dělitelné ani šesti.“ Pravdivá, stejně jako původní implikace.

V implikaci `A \Rightarrow B` je A postačující podmínka pro B a B nutná podmínka pro A: dělitelnost šesti stačí k dělitelnosti třemi, dělitelnost třemi je pro dělitelnost šesti nutná. Na obměně stojí nepřímý důkaz: místo „když A, pak B“ se dokazuje „když neplatí B, neplatí ani A“. Že obrácená implikace s původní ekvivalentní není, ukáže ekvivalence dvou výroků: má `A \Rightarrow B` a `B \Rightarrow A` nastavené jako příklad a vypíše řádky, ve kterých se liší.

Výroky s kvantifikátory a jejich negace

Výroková forma jako „x je liché“ se stane výrokem i bez dosazení, když řekneme, pro kolik prvků má platit. Obecný kvantifikátor `\forall` se čte „pro každé“, existenční `\exists` „existuje“. Výrok „Každé prvočíslo je liché“ je nepravdivý, protože 2 je sudé prvočíslo. Jeho negace „Existuje prvočíslo, které není liché“ je pravdivá.

• „Všichni žáci přišli včas.“ Negace: „Aspoň jeden žák přišel pozdě.“ Ne „Žádný žák nepřišel včas“, to je mnohem silnější tvrzení.
• „Aspoň tři žáci mají jedničku.“ Negace: „Nejvýše dva žáci mají jedničku.“
• „Každý žák má aspoň jednu pětku.“ Negace: „Aspoň jeden žák nemá žádnou pětku.“ Mění se oba kvantifikátory.

Výroky a množiny

Spojky odpovídají množinovým operacím. Když A je množina žáků, kteří umí anglicky, a B množina těch, kteří umí německy, pak žáci, pro které platí „umí anglicky a umí německy“, tvoří průnik A ∩ B. Ti, kdo umí aspoň jeden z jazyků, tvoří sjednocení A ∪ B, a ti, kdo anglicky neumí, doplněk A′. Vybarvená je vždy oblast, kde výrok platí:

De Morganovy zákony platí pro množiny ve stejném tvaru: doplněk průniku je sjednocení doplňků, (A ∩ B)′ = A′ ∪ B′. Vyzkoušet to jde na vlastních množinách v kalkulačce doplněk množiny, průnik a sjednocení spočítá sjednocení, průnik a rozdíl množin. Slovní úlohy, ve kterých se počítá s průnikem, řeší článek Slovní úlohy s množinami a Vennův diagram a kalkulačka Vennův diagram.

Časté chyby

• Negace jako opak. Negace „je teplo“ je „není teplo“, ne „je zima“. Výrok a jeho negace nesmí být nikdy nepravdivé současně.
• Negace implikace jako implikace. `\neg (A \Rightarrow B)` není `\neg A \Rightarrow \neg B` ani `A \Rightarrow \neg B`, ale `A \wedge \neg B`. Negace „když prší, beru si deštník“ je „prší a deštník si neberu“.
• De Morgan bez změny spojky. `\neg (A \wedge B)` není `\neg A \wedge \neg B`. Při negaci se „a“ mění na „nebo“ a naopak.
• „Nebo“ jako „buď, anebo“. Disjunkce platí i tehdy, když platí oba výroky.
• Implikace s nepravdivým předpokladem. Je vždy pravdivá. Nepravdivá je implikace jen v řádku 1, 0.
• Záměna obrácené implikace a obměny. Z `A \Rightarrow B` plyne `\neg B \Rightarrow \neg A`, ale ne `B \Rightarrow A`.
• Negace „všichni“ jako „žádný“. Na vyvrácení „všichni“ stačí jeden, který ne.
• Málo řádků. Tři proměnné dávají 8 řádků, ne 6. Počet řádků se s každou proměnnou zdvojnásobí.

Příklady k procvičení

Kam dál

Hodnotu složeného výroku, počet pravdivých řádků, tautologie i negace procvičíte v příkladech na výrokovou logiku. Po chybě uvidíte správnou odpověď hned.

Vlastní výroky spočítají kalkulačky množin a výrokové logiky: pravdivostní tabulka s mezivýsledky, negace výroku krok po kroku a ekvivalence dvou výroků. Z množinové části se k tématu hodí množinové operace, doplněk množiny a Vennův diagram se třemi množinami.

Navazující článek: Slovní úloha řešená pomocí množin.