Квантифікатори

Приклади висловів з квантифікаторами

Властивість: число x парне можна виразити, як існує ціле число k таке, що x = 2\cdot k. Це можна записати як \exists k \in \mathbb{Z}: x = 2\cdot k.

Твердження Підводні човни (P) не можуть літати (L). можна записати, як \forall x: P(x) \Rightarrow \neg L(x).

У складніших висловах з кількома квантифікаторами ми маємо дбати про порядок квантифікаторів:

• \exists x\in M\ \forall y \in M: y \leq x – існує елемент у множині M, який є більшим або рівним усім іншим елементам у M, тобто вислів каже, що множина має найбільший елемент.
• \forall x\in M\ \exists y \in M: y \leq x – для кожного елемента у множині M існує елемент x, який менший або рівний X. Оскільки можна вибрати y=x, то це виконується для будь-якої множини (для просунутих: лише якщо розглядаємо множини чисел і \leq як звичайне упорядкування на числах).

\exists x\in M\ \forall y \in M: y \leq x – існує елемент у множині M, який є більшим або рівним усім іншим елементам у M, тобто вислів каже, що множина має найбільший елемент. \forall x\in M\ \exists y \in M: y \leq x – для кожного елемента у множині M існує елемент x, який менший або рівний x. Оскільки можна вибрати y=x, це виконується для будь-якої множини (для просунутих: лише якщо розглядаємо множини чисел і \leq як звичайне упорядкування на числах).

Заперечення тверджень з квантифікаторами

Під час заперечення тверджень з квантифікаторами змінюємо існуючий квантифікатор на загальний (і навпаки) і переміщуємо заперечення «всередину». Приклад:

• Не є правдою, що всі коти (К) чорні (Ч).
• \neg (\forall x: K(x) \Rightarrow C(x))
• Змінюємо загальний квантифікатор на існуючий і заперечуємо твердження.
• \exists x: \neg(K(x) \Rightarrow C(x))
• Тепер заперечуємо імплікацію за допомогою правила \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B).
• \exists x: K(x) \wedge \neg C(x)
• Існує кіт, який не є чорним.