Pravdivost složitějších výroků
Už v předchozí kapitole jsme si ukázali použití tabulky pravdivostních hodnot. U složitějších výroků ji budeme používat jako účinný nástroj ke zjištění pravdivostního ohodnocení daného výroku. Postup je poměrně jednoduchý:
- Výrok rozdělíme na co nejjednodušší dílčí výroky spojené logickými spojkami.
- Jednoduché výroky ohodnotíme.
- Pro jednotlivá ohodnocení jednoduchých výroků budeme analyzovat pravdivostní hodnoty o něco složitějších výroků podle spojek, jimiž jsou jednoduché výroky spojeny.
- Ohodnocení podle spojek opakujeme pro stále složitější dílčí výroky, až nakonec získáme ohodnocení celého složitého výroku.
Uvedený postup nemusí na první pohled vypadat srozumitelně, proto si vše ukážeme na příkladu, konkrétně na následujícím výroku:
\(( \neg\)\(\mathbf{A} \wedge \mathbf{B})\) \(\Rightarrow\) \(\mathbf{C}\)
Provedeme bod 1 z postupu, tj. postupně rozdělíme výrok na nejjednodušší dílčí výroky. Náš výrok je vlastně implikace, jejíž „levá strana“ je tvořena opět složeným výrokem. Když tedy výrok podle této implikace rozdělíme, získáme dva jednodušší výroky:
- \(\neg\)\(\mathbf{A} \wedge \mathbf{B}\)
- \(\mathbf{C}\)
Zatímco druhý výrok je jednoduchý a dále jej dělit nemůžeme, první výrok ještě rozdělit můžeme – je to totiž konjunkce dvou jednoduchých výroků (přesněji jednoduchého výroku a negace jiného jednoduchého výroku). Rozdělením této konjunkce získáme další dva výroky:
- \(\neg\)\(\mathbf{A}\)
- \(\mathbf{B}\)
Tyto výroky již dále dělit nemůžeme, negace u výroku \(\mathbf{A}\) nám nemusí nahánět strach, s tou si již snadno poradíme. Máme tedy tři jednoduché výroky: \(\mathbf{A}\), \(\mathbf{B}\) a \(\mathbf{C}\). Tyto jednoduché výroky zaneseme do tabulky pravdivostních hodnot a do jejích řádků zapíšeme všechny kombinace pravdivostních hodnot jednotlivých výroků:
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{C}\) |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
Nyní do tabulky přidáme negaci výroku \(\mathbf{A}\):
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{C}\) | \(\neg\)\(\mathbf{A}\) |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
Přidáme konjunkci výroků \(\neg\)\(\mathbf{A}\) a \(\mathbf{B}\). V naší tabulce již máme dost údajů pro její vyhodnocení (máme zde ohodnocení obou spojovaných výroků):
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{C}\) | \(\neg\)\(\mathbf{A}\) | \(\neg\)\(\mathbf{A}\) \(\wedge\) \(\mathbf{B}\) |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 |
Nyní můžeme do tabulky přidat celý náš zkoumaný výrok. Jeho ohodnocení bychom již měli zvládnout, protože z tabulky můžeme vyčíst, jaká jsou ohodnocení obou stran implikace, která náš výrok tvoří:
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{C}\) | \(\neg\)\(\mathbf{A}\) | \(\neg\)\(\mathbf{A}\) \(\wedge\) \(\mathbf{B}\) | \((\neg\)\(\mathbf{A}\) \(\wedge\) \(\mathbf{B})\) \(\Rightarrow\) \(\mathbf{C}\) |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 |
A máme ohodnocení našeho výroku pro jednotlivé pravdivostní hodnoty výroků \(\mathbf{A}\), \(\mathbf{B}\) a \(\mathbf{C}\). Vidíme, že náš výrok je nepravdivý jen v jediném případě, a to když výrok \(\mathbf{B}\) bude pravdivý a současně výroky \(\mathbf{A}\) a \(\mathbf{C}\) budou nepravdivé.
Pozor!!! Pokud chceme využívat tabulku pravdivostního ohodnocení pro zjišťování pravdivostní hodnoty výroku v závislosti na ohodnocení obsažených jednoduchých výroků, je nutné uvést v tabulce všechny možné kombinace pravdivostního ohodnocení jednoduchých výroků. Bude-li výrok obsahovat pouze dva jednoduché výroky \(\mathbf{A}\) a \(\mathbf{B}\), připadají v úvahu čtyři různé možnosti ohodnocení a tabulka může vypadat například následovně:
| \(\mathbf{A}\) | \(\mathbf{B}\) |
| 1 | 1 |
| 1 | 0 |
| 0 | 1 |
| 0 | 0 |
V případě tří různých výroků je to již osm různých možností (opravdu žádné dva řádky nejsou stejné):
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{C}\) |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
Vidíme, že počet řádků se zdvojnásobil. To platí i pro další navyšování počtu jednoduchých výroků, pro čtyři bychom tedy potřebovali 16 řádků, pro pět 32 řádků, atd. Tato metoda se tedy hodí především pro vyhodnocování složitých výroků, které obsahují malé množství jednoduchých výroků, je-li jejich počet vyšší, je vyhodnocování velmi pracné.
Vraťme se k vyhodnocování pravdivosti složitějších výroků a předveďme si postup ještě na jiném výroku:
\(( \mathbf{A}\) \(\Rightarrow\) \(\mathbf{B})\) \(\wedge\) \((\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A})\)
Opět budeme výrok dělit, až se dostaneme k jednoduchým výrokům. „Nejvyšší“ spojkou je v tuto chvíli konjunkce, pomocí níž jsou spojeny dva dílčí výroky v závorkách. Rozdělíme-li tedy náš výrok, získáme následující dva výroky:
- \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\)
- \(\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A}\)
Oba tyto dílčí výroky jsou tvořeny jednoduchou implikací, u které již při ohodnocení základních jednoduchých výroků \(\mathbf{A}\) a \(\mathbf{B}\) budeme schopni určit výsledné ohodnocení. Do tabulky tedy nejdřív zapíšeme všechny kombinace ohodnocení výroků \(\mathbf{A}\) a \(\mathbf{B}\):
| \(\mathbf{A}\) | \(\mathbf{B}\) |
| 1 | 1 |
| 1 | 0 |
| 0 | 1 |
| 0 | 0 |
Nyní přidáme implikaci \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\):
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Dále zapíšeme i druhou implikaci \(\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A}\) (to jsme však také mohli udělat již v předchozím kroku, protože i její ohodnocení umíme určit na základě znalosti ohodnocení jednoduchých výroků \(\mathbf{A}\) a \(\mathbf{B}\)):
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\) | \(\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A}\) |
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 |
Teď už chybí jen výsledný výrok. Nezapomeňme, že je to konjunkce dvou výroků, u nichž již známe jejich ohodnocení. Zapsat ohodnocení výsledného výroku je tedy jednoduché:
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\) | \(\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A}\) | \(( \mathbf{A}\) \(\Rightarrow\) \(\mathbf{B})\) \(\wedge\) \((\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A})\) |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
Přidejme pro zajímavost do tabulky ještě ekvivalenci \(\mathbf{A}\) \(\Leftrightarrow\) \(\mathbf{B}\) a zapišme její ohodnocení:
| \(\mathbf{A}\) | \(\mathbf{B}\) | \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\) | \(\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A}\) | \(( \mathbf{A}\) \(\Rightarrow\) \(\mathbf{B})\) \(\wedge\) \((\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A})\) | \(\mathbf{A}\) \(\Leftrightarrow\) \(\mathbf{B}\) |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
Zjistili jsme, že ekvivalenci dvou výroků lze zapsat také pomocí dvojice implikací spojených konjunkcí. Ačkoli jsme použili jiné spojky, výsledné pravdivostní ohodnocení výroku je stejné (už víme, že o dvojici takových výroků říkáme, že jsou ekvivalentní). Lze také jiné logické spojky nahradit pomocí jiných? Ano, je to možné, dokonce nám pro výstavbu celé výrokové logiky stačí dvě vhodně zvolené spojky (mezi spojky počítáme i negaci, je to tzv. unární spojka), např. negace a implikace. Můžeme se podívat, jak pomocí této dvojice zapsat ostatní spojky:
| Původní výrok | Zápis pomocí negace a implikace |
|---|---|
| \(\mathbf{A}\) \(\wedge\) \(\mathbf{B}\) | \(\neg\)\((\mathbf{A}\) \(\Rightarrow\) \(\neg\) \(\mathbf{B})\) |
| \(\mathbf{A}\) \(\vee\) \(\mathbf{B}\) | \(\neg\)\(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\) |
| \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\) | \(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\) |
| \(\mathbf{A}\) \(\Leftrightarrow\) \(\mathbf{B}\) | \(\neg\)\(((\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B})\) \(\Rightarrow\) \(\neg\)\((\mathbf{B}\) \(\Rightarrow\) \(\mathbf{A}))\) |
Je zřejmé, že kdybychom měli k dispozici jen tyto dvě spojky, byl by zápis složených výroků velmi nepřehledný. Zkuste si jako cvičení ověřit tabulkou, že jsou uvedené dvojice výroků opravdu ekvivalentní.
