Kvantifikátory

Příklady výroků s kvantifikátory

Vlastnost Číslo x je sudé. můžeme vyjádřit jako Existuje celé číslo k takové, že x = 2\cdot k. To můžeme zapsat jako \exists k \in \mathbb{Z}: x = 2\cdot k.

Výrok Ponorky (P) nemohou létat (L). můžeme zapsat jako \forall x: P(x) \Rightarrow \neg L(x).

U složitejších výroků s více kvantifikátory musíme dávat na pořadí kvantifikátorů:

• \exists x\in M\ \forall y \in M: y \leq x – existuje prvek v množině M, který je větší roven všem ostatním prvkům v M, tj. výrok říká, že množina má největší prvek.
• \forall x\in M\ \exists y \in M: y \leq x – pro každý prvek v množině M existuje prvek x, který je menší nebo roven X. Protože klidně můžeme vybrat y=x, je to splněno pro každou množinu (pro pokročilé: tedy pouze pokud uvažujeme množiny čísel a \leq jako běžné uspořádání na číslech).

Negace výroků s kvantifikátory

Při negování výroků s kvantifikátory měníme existenční kvantifikátor na obecný (a naopak) a posouváme negaci „dovnitř“. Příklad:

• Není pravda, že všechny kočky (K) jsou černé (C).
• \neg (\forall x: K(x) \Rightarrow C(x))
• Změníme obecný kvantifikátor na existenční a znegujeme výrok.
• \exists x: \neg(K(x) \Rightarrow C(x))
• Nyní znegujeme implikaci pomocí pravidla \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B).
• \exists x: K(x) \wedge \neg C(x)
• Existuje kočka, která není černá.