Negace kvantifikovaných výroků
Na negace výroků s kvatifikátory jsme již trochu narazili ve chvíli, kdy jsme si kvantifikátory zaváděli a říkali si, za jakých podmínek kvantifikovaný výrok platí a kdy naopak neplatí. Přesto se na ně podívejme přesněji.
Nejprve si ukažme negaci výroku s obecným kvantifikátorem. Označíme-li výrokový vzorec \(\mathbf{A}\)(\(x\)) a proměnnou \(x\) budeme vybírat z množiny označené \(M\), můžeme psát:
\(\forall (x \in M)\): \(\mathbf{A}\)(\(x\))
Tento symbolický zápis označuje, že pro každé \(x\) z množiny \(M\) platí vztah uvedený ve výrokovém vzorci \(\mathbf{A}\)(\(x\)). V podstatě označuje zápis libovolného výroku s obecným kvantifikátorem. My jej využijeme k snadnému zápisu negace takového výroku.
Obecný kvantifikátor nám říká, že \(\mathbf{A}\)(\(x\)) platí pro všechny hodnoty proměnné \(x\). Jak z něj utvoříme negaci? K tomu, aby výrok nebyl pravdivý, stačí, abychom nalezli jednu hodnotu dané proměnné, která po dosazení do výrokového vzorce způsobí vznik nepravdivého výroku. Neboli, musí existovat hodnota proměnné, pro níž vznikne pravdivý výrok z negace výrokového vzorce. Předchozí věta zapsaná symbolicky je na následujícím řádku:
\(\exists (x \in M)\): \(\neg\)\(\mathbf{A}\)(\(x\))
Ukažme si tento poznatek opět na konkrétním příkladu – uvažujme výrok:
„Pro každé přirozené číslo x platí, že je dělitelné sedmi.“
Toto je samozřejmě nepravdivý výrok, jeho negaci lze formulovat následovně:
„Existuje přirozené číslo x takové, že není dělitelné sedmi.“
Přejděme k negaci výroků s existenčním kvantifikátorem. Použijeme opět symbolický zápis:
\(\exists (x \in M)\): \(\mathbf{A}\)(\(x\))
Pak existenční kvantifikátor říká, že existuje alespoň jedna hodnota proměnné \(x\) taková, že z \(\mathbf{A}\)(\(x\)) po jejím dosazením vznikne pravdivý výrok. Chceme-li výrok znegovat, musíme říci, že žádná taková hodnota neexistuje. To můžeme formulovat také tak, že pro všechny hodnoty proměnné \(x\) vznikne z \(\mathbf{A}\)(\(x\)) nepravdivý výrok, neboli že pro všechny hodnoty, kterých \(x\) může nabývat, bude vždy platit negace \(\mathbf{A}\)(\(x\)):
\(\forall (x \in M)\): \(\neg \mathbb{A}\)(\(x\))
Můžeme opět uvést příklad:
„Existuje přirozené číslo x takové, že je dělitelné dvěma.“
Negaci tohoto pravdivého výroku můžeme zapsat takto:
„Pro každé přirozené číslo x platí, že není dělitelné dvěma.“
Negace výroků s větším počtem kvantifikátorů
Pokud je před výrokovým vzorcem více kvantifikátorů, změníme při negování všechny tyto kvantifikátory na opačné a potom provedeme negaci výrokového vzorce. Pokud je výrok složen z více kvantifikovaných výroků, postupujeme při negaci opět stejně jako dříve – výrok rozdělíme podle spojky na dva jednodušší, znegujeme spojku a podle výsledku negace spojky upravujeme dílčí výroky.
Uvažujme následující výrok:
\(\forall (x \in M) \exists (y \in N): [(\mathbb{A}(x,y) \Rightarrow \mathbb{B}(x)) \wedge \forall (z \in K): (\mathbb{C}(x,y,z) \vee \mathbb{D}(x,z) ) ]\)
Na tomto výroku si ukážeme postup negace složitějších výroků s kvantifikátory. Nejprve znegujeme kvantifikátory u proměnných \(x\) a \(y\):
\(\exists (x \in M) \forall (y \in N): \neg[(\mathbb{A}(x,y) \Rightarrow \mathbb{B}(x)) \wedge \forall (z \in K): (\mathbb{C}(x,y,z) \vee \mathbb{D}(x,z) ) ]\)
Kvantifikátory jsou prozatím znegovány, nejvyšší spojkou je nyní konjunkce, znegujeme tedy ji:
\(\exists (x \in M) \forall (y \in N): [\neg(\mathbb{A}(x,y) \Rightarrow \mathbb{B}(x)) \vee \neg \forall (z \in K): (\mathbb{C}(x,y,z) \vee \mathbb{D}(x,z) ) ]\)
Dále znegujeme implikaci a kvantifikátor u proměnné \(z\):
\(\exists (x \in M) \forall (y \in N): [(\mathbb{A}(x,y) \wedge \neg\mathbb{B}(x)) \vee \exists (z \in K): \neg(\mathbb{C}(x,y,z) \vee \mathbb{D}(x,z) ) ]\)
A negaci dokončíme znegováním disjunkce:
\(\exists (x \in M) \forall (y \in N): [(\mathbb{A}(x,y) \wedge \neg\mathbb{B}(x)) \vee \exists (z \in K): (\neg\mathbb{C}(x,y,z) \wedge \neg\mathbb{D}(x,z) ) ]\)
Na závěr této kapitoly si ještě řekneme, že existuje také způsob, jakým se v matematice zapisuje, že existuje právě jeden prvek dané množiny, který splňuje určitou vlastnost. Používají se pro to slova „právě jeden“ a značí se vykřičníkem (společně s existenčním kvantifikátorem). Chceme-li např. zapsat, že existuje jen a pouze jedno přirozené číslo menší než dvě, můžeme tak učinit takto:
\(\exists ! (x \in \mathbb{N}): x < 2\)