\begin{align} \end{align}

Negace ekvivalence a složitějších výroků

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í:

  1. Nalezneme „nejvyšší“ spojku výroku.
  2. Znegujeme výrok podle pravidla pro negaci této spojky.
  3. Pokračujeme s dílčími výroky, je-li nutné je negovat.

Ukažme si postup na následujícím příkladu:

\((\)\(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\)\()\) \(\wedge\) \((\)\(\mathbf{B}\) \(\Rightarrow\) \(\mathbf{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 \(\mathbf{A}\) \(\wedge\) \(\mathbf{B}\) je výrok \(\neg\)\(\mathbf{A}\) \(\vee\) \(\neg\)\(\mathbf{B}\). Proveďme podle tohoto pravidla negaci konjunkce v našem výroku. Získáme následující:

\(\neg\)\((\)\(\mathbf{A}\) \(\Rightarrow\) \(\mathbf{B}\)\()\) \(\vee\) \(\neg\)\((\)\(\mathbf{B}\) \(\Rightarrow\) \(\mathbf{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:

\((\)\(\mathbf{A}\) \(\wedge\) \(\neg\)\(\mathbf{B}\)\()\) \(\vee\) \((\)\(\mathbf{B}\) \(\wedge\) \(\neg\)\(\mathbf{A}\)\()\)

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 \(\mathbf{A}\) \(\Leftrightarrow\) \(\mathbf{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:

\((\)\(\mathbf{A}\) \(\vee\) \(\mathbf{B}\)\()\) \(\Leftrightarrow\) \((\)\(\mathbf{A}\) \(\Rightarrow\) \(\neg\)\(\mathbf{B}\)\()\)

Nejdříve znegujeme ekvivalenci (teď už víme, jak její negace vypadá):

\(((\)\(\mathbf{A}\) \(\vee\) \(\mathbf{B}\)\()\) \(\wedge\) \(\neg\)\((\)\(\mathbf{A}\) \(\Rightarrow\) \(\neg\)\(\mathbf{B}\)\())\) \(\vee\) \((\)\(\neg\)\((\)\(\mathbf{A}\) \(\vee\) \(\mathbf{B}\)\()\) \(\wedge\) \((\)\(\mathbf{A}\) \(\Rightarrow\) \(\neg\)\(\mathbf{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.

\(((\)\(\mathbf{A}\) \(\vee\) \(\mathbf{B}\)\()\) \(\wedge\) \((\)\(\mathbf{A}\) \(\wedge\) \(\mathbf{B}\)\())\) \(\vee\) \(((\)\(\neg\)\(\mathbf{A}\) \(\wedge\) \(\neg\)\(\mathbf{B}\)\()\) \(\wedge\) \((\)\(\mathbf{A}\) \(\Rightarrow\) \(\neg\)\(\mathbf{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ů \(\mathbf{A}\) a \(\mathbf{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):

\((\)\(\mathbf{A}\) \(\wedge\) \(\mathbf{B}\)\()\) \(\vee\) \(((\)\(\neg\)\(\mathbf{A}\) \(\wedge\) \(\neg\)\(\mathbf{B}\)\()\) \(\wedge\) \((\)\(\mathbf{A}\) \(\Rightarrow\) \(\neg\)\(\mathbf{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 \(\neg\)\(\mathbf{A}\) \(\wedge\) \(\neg\)\(\mathbf{B}\). Je to pouze v případě, kdy výrok \(\mathbf{A}\) i výrok \(\mathbf{B}\) jsou nepravdivé. V takovém případě bude ovšem implikace \(\mathbf{A}\) \(\Rightarrow\) \(\neg\)\(\mathbf{B}\) pravdivá. Protože v jiném případě nemůže být výrok \(\neg\)\(\mathbf{A}\) \(\wedge\) \(\neg\)\(\mathbf{B}\) pravdivý, pak ani celá konjunkce nemůže být jindy pravdivá. Opět ji tedy můžeme nahradit pouze její levou stranou:

\((\)\(\mathbf{A}\) \(\wedge\) \(\mathbf{B}\)\()\) \(\vee\) \((\)\(\neg\)\(\mathbf{A}\) \(\wedge\) \(\neg\)\(\mathbf{B}\)\()\)

Výsledný výrok by se dal ještě zjednodušit. Jak? Výrok platí, jestliže výroky \(\mathbf{A}\) a \(\mathbf{B}\) jsou buď oba pravdivé, nebo oba nepravdivé. To je však definice ekvivalence, tedy výrok můžeme zapsat jako:

\(\mathbf{A}\) \(\Leftrightarrow\) \(\mathbf{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.