Složené výroky nemusí obsahovat jen jedinou spojku, ale mohou být mnohem složitější. I u takových výroků často potřebujeme odhalit, zda jsou pravdivé či nepravdivé. V této kapitole si ukážeme, jak na to. Na závěr si předvedeme, že některé logické spojky lze nahradit kombinací negace a jiných spojek.
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ý:
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:
(¬A∧ B) ⇒ 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:
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:
Tyto výroky již dále dělit nemůžeme, negace u výroku A nám nemusí nahánět strach, s tou si již snadno poradíme. Máme tedy tři jednoduché výroky: A, B a 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ů:
| A | B | 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 A:
| A | B | C | ¬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ů ¬A a B. V naší tabulce již máme dost údajů pro její vyhodnocení (máme zde ohodnocení obou spojovaných výroků):
| A | B | C | ¬A | ¬A ∧ 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ří:
| A | B | C | ¬A | ¬A ∧ B | (¬A ∧ B) ⇒ 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ů A, B a C. Vidíme, že náš výrok je nepravdivý jen v jediném případě, a to když výrok B bude pravdivý a současně výroky A a 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 A a B, připadají v úvahu čtyři různé možnosti ohodnocení a tabulka může vypadat například následovně:
| A | 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é):
| A | B | 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:
(A ⇒ B) ∧ (B ⇒ 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:
Oba tyto dílčí výroky jsou tvořeny jednoduchou implikací, u které již při ohodnocení základních jednoduchých výroků A a B budeme schopni určit výsledné ohodnocení. Do tabulky tedy nejdřív zapíšeme všechny kombinace ohodnocení výroků A a B:
| A | B |
| 1 | 1 |
| 1 | 0 |
| 0 | 1 |
| 0 | 0 |
Nyní přidáme implikaci A ⇒ B:
| A | B | A ⇒ B |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Dále zapíšeme i druhou implikaci B ⇒ 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ů A a B):
| A | B | A ⇒ B | B ⇒ 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é:
| A | B | A ⇒ B | B ⇒ A | (A ⇒ B) ∧ (B ⇒ 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 A ⇔ B a zapišme její ohodnocení:
| A | B | A ⇒ B | B ⇒ A | (A ⇒ B) ∧ (B ⇒ A) | A ⇔ 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 |
|---|---|
| A ∧ B | ¬(A ⇒ ¬ B) |
| A ∨ B | ¬A ⇒ B |
| A ⇒ B | A ⇒ B |
| A ⇔ B | ¬((A ⇒ B) ⇒ ¬(B ⇒ 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í.
Vraťme se ale ještě k řešení pravdivostního ohodnocení složitějších výroků a podívejme se na tři zajímavé příklady. Prvním z nich je výrok:
A ⇒ (B ⇒ A)
Po rozdělení podle „nejvyšší“ implikace získáme dva výroky:
A vytvoříme tabulku (tentokrát ji zde rovnou uvedeme kompletní):
| A | B | B ⇒ A | A ⇒ (B ⇒ A) |
| 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
Narazili jsme na zajímavý výrok, z tabulky totiž vyplývá, že ať je ohodnocení jednoduchých výroků A a B jakékoli, výsledný výrok bude vždy pravdivý.
Až doposud jsme si pod písmeny A, B, C, … představovali nějaký jednoduchý výrok. Když se nad tím zamyslíme, zjistíme, že se pod ními nemusí skrývat jen výrok jednoduchý, ale i výroky složené, a to jakkoli složité, protože i ty mají své jednoznačné pravdivostní ohodnocení.
Je také dobré si uvědomit, že např. zápis A ⇒ B není de facto výrokem (i když jsme jej zde tak nazývali a budeme i dále nazývat), ale je jen jakýmsi vzorem pro výrok. Pravý výrok se z něj stává, až ve chvíli, kdy víme, jaký konkrétní výrok se schovává pod písmeny A, B. Tato písmena nazýváme výrokovými proměnnými. Je to podobné jako u jednoduchých rovnic. V rovnici můžeme mít např. proměnnou x, rovnost se z rovnice stává až po dosazení správného čísla za x.
Proč tu teď rozebíráme výrokové proměnné? Abychom se mohli vrátit k výše uvedenému výroku, pro který platí, že je vždy pravdivý, a mohli si nadefinovat, co je to tautologie. Tautologie je výrok, který je pro libovolné ohodnocení svých výrokových proměnných vždy pravdivý. Tento typ výroků je v matematice a matematické logice velmi důležitý, protože umožňuje odvozovat nové poznatky z poznatků již ověřených.
Podívejme se ještě na složitější tautologii:
(¬A ∨ B) ⇔ (A ⇒ B)
Po rozkladu na dílčí výroky se dostaneme k následující tabulce:
| A | B | ¬A | ¬A ∨ B | A ⇒ B | (¬A ∨ B) ⇔ (A ⇒ B) |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 |
Narazili jsme tedy na ekvivalenci dvou složitějších výroků, která je zároveň tautologií, tedy je vždy pravdivá. Z toho plyne, že oba spojované výroky jsou ekvivalentní (pro jakékoli ohodnocení výrokových proměnných), a tedy že jsme našli vyjádření implikace pomocí negace a disjunkce.
Nyní se podívejme na výrok:
(A ⇒ B) ⇔ (¬B ⇒ ¬A)
Tabulka pravdivostních hodnot bude vypadat následovně:
| A | B | ¬A | ¬B | A ⇒ B | ¬B ⇒ ¬A | (A ⇒ B) ⇔ (¬B ⇒ ¬A) |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
Opět se jedná o tautologii. Co je na ní zajímavého? Všimněme si, že je to vlastně ekvivalence dvou výroků. Už jsme si řekli, že v takovém případě jsou spojované výroky ekvivalentní. Neboli, máme-li implikaci A ⇒ B, pak ekvivalentní tvrzení můžeme sdělit pomocí implikace ¬B ⇒ ¬A. Takové implikaci se říká obměněná implikace. Obměněná implikace je opět velmi důležitým prvkem matematické logiky a náchází mnohá využití. Je však nutné dávat pozor a nepoplést si ji s obrácenou implikací, což je implikace, u níž přehodíme levou a pravou stranu. V našem případě by to byla implikace B ⇒ A. Tato implikace však není s původní implikací ekvivalentní (to už bychom měli vědet z kapitoly o logických spojkách)! Často se u matematických pravidel ve tvaru implikace uvádí upozornění, že obrácená implikace neplatí.
Podívejme se na konkrétní příklad. Použijeme výrok, který jsme již viděli, když jsme si zaváděli pojem implikace.
„Jestliže v Berouně prší, pak hladina Berounky v Berouně stoupá.“
Obměněná implikace zní takto:
„Jestliže hladina Berounky v Berouně nestoupá, pak v Berouně neprší.“
Obrácenou implikací je ale následující věta:
„Jestliže hladina Berounky v Berouně stoupá, pak v Berouně prší.“
Zkusme porovnat předchozí tři „berounské“ výroky. První je za normálních okolností pravdivý – pokud do řeky prší, její hladina skutečně (alespoň nepatrně) stoupá (výjimky způsobené vodohospodářskou regulací apod. pro tuto chvíli zanedbáme). Druhý říká v podstatě totéž, jen z „opačné“ strany (pokud hladina nestoupá, nemůže do řeky pršet). To, že tyto výroky říkají v podstatě totéž ale není asi každému na první pohled zřejmé, je nutné se nad tímto faktem dostatečně zamyslet. Třetí věta však ale nabírá jiný směr – říká, že pokud stoupá hladina řeky v nějakém místě, pak v tomto místě musí pršet. To samozřejmě není pravda, často jsou zdrojem povodní v údolí srážky spadlé v horách.
Na závěr tohoto zamyšlení nad implikacemi si ještě v tabulce shrňme rozdíly v pravdivostním ohodnocení původní, obměněné, obrácené a „obměněné obrácené“ implikace:
| A | B | ¬A | ¬B | A ⇒ B původní implikace |
¬B ⇒ ¬A obměněná implikace |
B ⇒ A obrácená implikace |
¬A ⇒ ¬B obměněná obrácená implikace |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
Také u složitých výroků musíme být schopni vytvořit jejich negace. Zatím ale umíme negovat jen výroky jednoduché popř. výroky s jedinou spojkou. Princip negování složitějších výroků je trochu podobný jejich vyhodnocování v tabulce pravdivostních hodnot – opět budeme výrok rozkládat na jednodušší. Postup bude následující:
Ukažme si postup na následujícím příkladu:
(A ⇒ B) ∧ (B ⇒ A)
„Nejvyšší“ spojkou je konjunkce – výrok je tvořen konjunkcí dvou jednodušších výroků (zde dvou implikací). Připomeňme si, že negací konjunkce A ∧ B je výrok ¬A ∨ ¬B. Proveďme podle tohoto pravidla negaci konjunkce v našem výroku. Získáme následující:
¬(A ⇒ B) ∨ ¬(B ⇒ A)
Před oběma implikacemi se objevila negace. Protože však již negaci implikace umíme, nemělo by tedy být obtížné tuto negaci provést:
Nyní již máme negace jen u výrokových proměnných, což znamená, že negace našeho výroku je hotova. Pozorně si ale ještě prohlédněme výrok, který jsme negovali. Je to výrok ekvivalentní k výroku A ⇔ B. Takže jsme odvodili nejen negaci našeho výroku, ale zároveň také negaci ekvivalence. Tím jsme splnili předsevzetí, které jsme si dali v minulé kapitole. To, že jsme opravdu našli negaci, je možné si ověřit tabulkou.
Pro lepší porozumění si ještě ukažme negování složitějších výroků na dalším příkladu:
(A ∨ B) ⇔ (A ⇒ ¬B)
Nejdříve znegujeme ekvivalenci (teď už víme, jak její negace vypadá):
((A ∨ B) ∧ ¬(A ⇒ ¬B)) ∨ (¬(A ∨ B) ∧ (A ⇒ ¬B))
Opět můžeme postupovat s negací i u vnitřních výroků, využijeme zde také poznatku, že dvojitá negace dává původní výrok.
((A ∨ B) ∧ (A ∧ B)) ∨ ((¬A ∧ ¬B) ∧ (A ⇒ ¬B))
Negace je hotova, ale výrok vypadá poměrně složitě. Na otázku, zda by jej nebylo možné zjednodušit, lze jednoduše odpovědět, že ano. A jak to provést? Jsou v podstatě dvě možnosti – buď vytvořit tabulku pravdivostního ohodnocení a z ní se pokusit odhadnout jednodušší ekvivalentní výrok, nebo provést zjednodušení úvahou. My se vydáme právě touto druhou cestou.
Celý výrok je disjunkcí dvou složených výroků. Podívejme se nyní na první část (levou stranu) této disjunkce. Aby tato byla pravdivá, musí zároveň platit konjunkce i disjunkce výroků A a B. Když si vzpomeneme, kdy je pravdivá disjunkce a konjunkce dvou výroků, zjistíme, že konjunkce je pravdivá pouze v jediném případě, kdy oba spojované výroky jsou pravdivé. V témže případě je pravdivá i disjunkce. To, že disjunkce může být pravdivá i jindy, pro nás v tuto chvíli nemá žádný význam, protože my potřebujeme, aby byly pravdivé obě. Z toho plyne, že nahradíme-li zmiňovanou levou stranu pouze konjunkcí, získáme ekvivalentní výrok (opět si můžeme ověřit tabulkou):
(A ∧ B) ∨ ((¬A ∧ ¬B) ∧ (A ⇒ ¬B))
Druhá část výroku je tvořena opět konjunkcí (tedy opět musí platit obě její strany, aby byla pravdivá) dvou složených výroků. Uvědomme si, kdy platí výrok ¬A ∧ ¬B. Je to pouze v případě, kdy výrok A i výrok B jsou nepravdivé. V takovém případě bude ovšem implikace A ⇒ ¬B pravdivá. Protože v jiném případě nemůže být výrok ¬A ∧ ¬B pravdivý, pak ani celá konjunkce nemůže být jindy pravdivá. Opět ji tedy můžeme nahradit pouze její levou stranou:
(A ∧ B) ∨ (¬A ∧ ¬B)
Výsledný výrok by se dal ještě zjednodušit. Jak? Výrok platí, jestliže výroky A a B jsou buď oba pravdivé, nebo oba nepravdivé. To je však definice ekvivalence, tedy výrok můžeme zapsat jako:
A ⇔ B
Ukázali jsme si, že složité výroky umíme nejen negovat, ale i různě upravovat a zjednodušovat, což nám může mnohdy výrazně ulehčit práci.