Pravdivost formulí

Pokud máme nějaké atomické výroky, které složíme do formule, můžeme se pokusit rozhodnout, zda je celá formule pravdivá nebo nepravdivá.

Pravdivost výroku

Jako první si upřesníme, co je to pravdivostní hodnota výroku. Máme-li výrok p, měli bychom být schopni rozhodnout, zda je pravdivý, nebo nepravdivý. Pravdivý výrok bude mít pravdivostní hodnotu 1 a nepravdivý 0.

Pravdivostní ohodnocení je pak předpis e, který danému výroku přiřazuje buď 0 nebo 1. Pokud napíšeme e(p), chceme zjistit pravdivost výroku p. Pokud je p rovno výroku „dva krát dva jsou čtyři“, pak e(p) = 1, protože se jedná o pravdivý výrok. Pokud je q rovno výroku „Václav Klaus je žena“, pak e(q) = 0, protože Vašek není žena. e je tak funkce, která nám vrací, zda je výrok pravdivý.

Zde je nutné si uvědomit, že e není nějaká magická funkce, která ví všechno na světě. Chová se tak, jak jí řekneme. Ona neví, zda je Václav Klaus muž nebo žena. My bychom na začátku výpočtu měli deklarovat, jak se má ohodnocovací funkce chovat. Pokud jí řekneme, že Václav Klaus je žena, tak nám vrátí e(q) = 1.

Pravdivost výrokových spojek

Abychom mohli stanovit pravdivost formule, potřebujeme vědět, jak vyhodnotit pravdivost výrokových spojek. Tedy pokud známe ohodnocení e(p) a e(q), jaká bude pravdivostní hodnota formulí p ∧ q, $p \Rightarrow q$ apod.

Každá výroková spojka se chová jinak a používá se na něco jiného, takže si každou spojku probereme zvlášť.

Pravdivost konjunkce

Konjunkce se označuje p ∧ q a čte se “p a zároveň q“. Pro příklad si vezměme formuli „Česká republika leží ve střední Evropě a zároveň její hlavní město je Praha“. Kdy bude celá tato věta pravdivá?

K určení pravdivosti nám pomůže už samotná spojka „a zároveň“. Ta nám výslovně říká, že chce, aby oba výroky nalevo a napravo byly pravdivé. Pokud tak jsou oba výroky p a q pravdivé, tedy e(p) = 1 a e(q) = 1, pak je pravdivá i celá konjunkce. V opačném případě, kdy je buď jeden z výroků nepravdivý nebo jsou nepravdivé oba, je celá formule nepravdivá.

Příkladem konjunkce, která není pravdivá může být: „Vltava je řeka a zároveň Vltava teče přes Rusko“. Je pravda, že Vltava je řeka, ale není pravda, že teče v Rusku, takže celá konjunkce není pravdivá.

Přehledně to zapisuje následující tabulka:

$$\begin{array}{ccc} p&q&p \wedge q\\ 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&0 \end{array}$$

V prvních dvou sloupcích jsou pravdivostní hodnoty výroků p a q a ve třetím je pravdivostní hodnota formule p ∧ q.

Pravdivost disjunkce

Disjunkce se označuje p ∨ q a čte se “p nebo q“. Příklad: „Rusko leží v Evropě nebo v Asii.“ Kdy bude celá věta pravdivá?

U disjunkce nám stačí, když bude alespoň jedna z možností pravdivá. Spojka „nebo“ nám dává na výběr, stačí, když bude pravdivá její levá nebo pravá část. Jediný drobný rozdíl oproti běžné mluvě je, že logické nebo je pravdivé, i když jsou splněny oba výroky zároveň. To nebývá úplně zvykem, často v běžné mluvě používáme „nebo“ vylučovacím způsobem, tj. „buď …, nebo …“

Na to existuje klasický vtip: rodina v bazaru vybírá nové auto. Tatínek říká prodejci, „rozhodli jsme se, že si vezmeme modré nebo červené auto“. Prodejce jim prodal obě auta. Toto je ilustrace rozdílu mezi logickým a mluveným nebo: tatínek měl asi na mysli, že si z těchto aut vyberou právě jedno, kdežto prodejce považoval za platnou možnost prodat jim obě auta.

Předchozí věta s Ruskem je pravdivá, protože jsou pravdivé oba výroky. Věta „číslo 7 je dělitelné 3 nebo je číslo 7 prvočíslo“ je pravdivá, protože sedmička je prvočíslo. Sice není dělitelná třemi, ale to už nám nevadí. Tabulka pravdivostních hodnot:

$$\begin{array}{ccc} p&q&p \vee q\\ 1&1&1\\ 1&0&1\\ 0&1&1\\ 0&0&0 \end{array}$$

Pravdivost implikace

Implikace se označuje $p \Rightarrow q$ a čte se „jestliže p, pak q“. Příkladem implikace může být věta „jestliže vypijeme hodně vodky, pak budeme zvracet“. Kdy bude věta pravdivá?

Logická implikace je nejzrádnější ze všech spojek a i v běžné mluvě často není pochopena a je zaměňována s ekvivalencí. Zkusme si zodpovědět otázku, jestli platí zároveň i obrácená implikace: $q \Rightarrow p$.

Víme, že když vypijeme hodně vodky, pak budeme zvracet. Platí zároveň, že když budeme zvracet, tak jsme vypili hodně vodky? To určitě neplatí, mohli jsme pít úplně jiný alkohol a stejně nám mohlo být špatně a nebo nám může být špatně z něčeho úplně jiného. Obrácená implikace tak automaticky nemusí platit. Pokud platí $p \Rightarrow q$ a zároveň platí $q \Rightarrow p$, jedná se o ekvivalenci, viz dále.

Jiný příklad: „jestliže bude zítra pršet, pak si s sebou Honza vezme deštník“. A teď vám řeknu, že Honza si s sebou deštník vzal. Otázka zní — pršelo toho dne? Spousta lidí má tendenci říct, že samozřejmě ano, vždyť Honza si s sebou bral deštník, když mělo pršet. Jenže takto ta původní věta postavena není!

Honza si ve skutečnosti mohl vzít deštník kvůli něčemu jinému, o čem nemáme tušení. Třeba si Honza bere s sebou deštník vždy, když jde navštívit tchyni, aby jí mohl vypíchnout oko. Nebo se rozhodl, že si koupí nový deštník a ten starý chce vyhodit. To jsou všechno legální důvody, proč si Honza mohl s sebou vzít deštník, přestože nemuselo pršet.

Teď už si můžeme zodpovědět otázku, kdy bude implikace pravdivá. Když budou oba výroky pravdivé, tak bude implikace určitě pravdivá: „jestliže je 42 přirozené číslo, pak je kladné“. Oba výroky jsou pravdivé, takže celá implikace je pravdivá. Dalším příkladem může být implikace „jestliže je 42 přirozené číslo, pak je záporné“. Tato implikace není pravdivá, protože z pravdy se snažíme vyvodit něco, co není pravda.

Nakonec zbývají případy, kdy je první výrok nepravdivý. V takovém případě nás už pravdivost druhého výroku nezajímá. Pokud vycházíme z nepravdy, můžeme dál blábolit co chceme. Jsou to věty typu „jestliže je 1 záporné číslo, pak jsme čínský bůh srandy“ nebo „jestliže jsou Beatles známá stavební firma, pak je slunce modré.“ V takových případech je implikace automaticky pravdivá, protože zkrátka vychází z nepravdy. Tabulka:

$$\begin{array}{ccc} p&q&p \Rightarrow q\\ 1&1&1\\ 1&0&0\\ 0&1&1\\ 0&0&1 \end{array}$$

Pravdivost ekvivalence

Ekvivalence se zapisuje p ⇔ q a čte se “p právě tehdy, když q“. Příkladem ekvivalence může být „číslo x je dělitelné dvěma právě tehdy, když je sudé“. Kdy bude celá věta pravdivá?

U ekvivalence očekáváme, že jsou oba výroky v takové symbióze, že buď platí oba, nebo neplatí žádný. Takže buď je číslo x sudé a zároveň i dělitelné dvěma, nebo není ani jedno z toho. Nemůže nastat případ, kdy by x bylo sudé, ale nebylo by dělitelné dvěma.

Příklad: „Jiří si čte knížku právě tehdy, když sedí na záchodě.“ Aby byla ekvivalence splněná, tak vždy, když Jiří sedí na záchodě, tak si musí číst knížku. A zároveň vždy, když si čte knížku, musí sedět na záchodě. Nemůže se stát, že si čte knížku třeba v posteli.

Ekvivalenci můžeme vyjádřit pomocí dvou implikací. Takže p ⇔ q bychom mohli přepsat jako $p \Rightarrow q$ a zároveň $q \Rightarrow p$. Tabulka:

$$\begin{array}{ccc} p&q&p \Leftrightarrow q\\ 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&1 \end{array}$$

Negace

Negace je unární operace, zapisujeme ji buď čárkou p' nebo tímto symbolem: $\neg p$. Negace nám zneguje původní tvrzení. Máme-li výrok „Lucie Bílá je zpěvačka“, tak negací bychom dostali výrok „Není pravda, že Lucie Bílá je zpěvačka“ nebo zkráceně „Lucie Bílá není zpěvačka“. Prakticky vždy můžeme negaci vytvořit tak, že před výrok dáme „Není pravda, že…“

Negace nám obrátí pravdivostní hodnotu, tj. z 0 udělá 1 a z 1 udělá 0. Můžeme tak napsat $\neg0=1$ a $\neg1=0$.

Pozor na některé zrádné věci. Mějme tvrzení „vápno je bílé“. Jaká je negace? Někoho by mohlo napadnout, že „vápno je černé“, ale to není pravda! Když použijeme předchozí poučku, tak negací bude výrok „není pravda, že vápno je bílé“. Znamená to nutně, že musí být černé? Neznamená, může být třeba růžovoučké.

Tabulka všech spojek

$$\begin{array}{cccccc} p&q&p \wedge q&p \vee q&p \Rightarrow q&p \Leftrightarrow q\\ 1&1&1&1&1&1\\ 1&0&0&1&0&0\\ 0&1&0&1&1&0\\ 0&0&0&0&1&1 \end{array}$$

Pravdivost celé formule

Nyní už umíme vyhodnotit pravdivost dvou výroků, které jsou spojeny výrokovou spojkou. Celou formuli vyhodnotíme zcela analogicky. Pokud máme formuli $(p \Rightarrow q) \wedge r$, tak ve chvíli, kdy vyhodnotíme formuli $(p \Rightarrow q)$ například na 1, tak dostáváme klasickou konjunkci 1 ∧ r, kterou už umíme řešit.

Postupnou aplikací nejjednodušších výrokových spojek dojdeme k výsledné pravdivostní hodnotě celé formule. Často se k tomu používá tzv. tabulková metoda, které je popsáno dále.

Tabulková metoda

Tabulková metoda se používá při vyhodnocování složitějších formulí. Do prvních n sloupců si zapíšeme n výrokových symbolů, se kterými formule pracuje a do dalších sloupců postupně umístíme dílčí podformule, které formule obsahuje. Na příkladu to bude jasnější:

Mějme formuli $(p \vee q) \wedge (q \Rightarrow p)$. Na začátku si do tabulky napíšeme všechny výrokové symboly, tj. p a q a všechny kombinace jejich ohodnocení:

$$\begin{array}{cc} p&q\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Dále si tam připíšeme sloupce pro jednotlivé podformule p ∨ q a $q \Rightarrow p$.

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Nyní tyto formule vyhodnotíme a doplníme do sloupců nuly nebo jedničky. V tabulce máme všechny potřebné informace. Postupujeme tak, že když vyhodnocujeme p ∨ q v prvním řádku, tak za p dosadíme 1 a za q také 1. Tím dostáváme výraz 1 ∨ 1. Vyhodnocením tohoto výrazu je opět 1, takže do tabulky napíšeme jedničku:

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Takto postupně doplníme celou tabulku:

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1&1&1\\ 1&0&1&1\\ 0&1&1&0\\ 0&0&0&1 \end{array}$$

Nyní zbývá vyhodnotit celou formuli. Označme si ji třeba $\varphi=(p \vee q) \wedge (q \Rightarrow p)$. Přidáme do tabulky sloupeček s $\varphi$ a vyhodnotíme ho, přičemž k vyhodnocení už použijeme předchozí dva sloupce.

$$\begin{array}{ccccc} p&q&p \vee q&q \Rightarrow p&\varphi\\ 1&1&1&1&1\\ 1&0&1&1&1\\ 0&1&1&0&0\\ 0&0&0&1&0 \end{array}$$

Tabulka už je kompletní a určuje nám pravdivostní hodnotu formule ve všech možných ohodnocení. Například pokud e(p) = 1 a zároveň e(q) = 1, tak je formule pravdivá. V případě, že e(p) = 0 a e(q) = 1, tak formule pravdivá není.

Všimněte si, že nemůžeme říci, že „formule je pravdivá“. Tato věta nedává smysl, protože abychom mohli říci, že je formule pravdivá, museli bychom říci, v jakém ohodnocení je formule pravdivá. Můžeme tak říci, že „formule $\varphi$ je pravdivá v ohodnocení e₁ a není pravdivá v ohodnocení e₂“.

Jediným případem, kdy bychom mohli říci, že formule je pravdivá je, pokud je pravdivá ve všech možných ohodnoceních. Například formule $p \vee \neg p$ je pravdivá ve všech ohodnoceních, takže můžeme říci, že formule je pravdivá. Podobně pro případ, kdy formule bude ve všech ohodnoceních nepravdivá.

Takové formule pak mají své speciální označení. Formule, která je pravdivá ve všech ohodnoceních se nazývá tautologie. Formule, která není splněná v žádném ohodnocení, se nazývá kontradikce.