Кванторы

В алгебре высказываний применяют логические знаки для записи различных утверждений. Однако нам не достаточно этих знаков для выражения мысли типа «Всякий элемент $x$ из множества $D$ обладает свойством $P(x)$».

Понятие кванторов

Введем новые логические знаки, обозначаемые $\forall$, $\exists$ и $\exists!$. Знак $\forall$ называется квантором всеобщности, знак $\exists$ — квантором существования, а $\exists!$ — квантором существования и единственности.

Пусть $P(x)$ — одноместный предикат, определенный на множестве $D$.

Квантор всеобщности

Используя квантор всеобщности, можно составить следующее высказывание

$$\forall x~P(x),$$ которое является истинным тогда и только тогда, когда предикат $P(x)$ является истинным при любом значении пременной $x$ из множества $D$.

Читается как: «для любого $x$ выполняется $P(x)$»; «для всякого $x~P(x)$»; «для всякого $x$ верно $P(x)$» и т.п.

Пусть $P(x)$ предикат $x^2 \geq 0$, определенный на множестве действительных чисел $D = \mathbb R$. Тогда высказывание $\forall x~P(x)$ имеет вид $\forall x~x^2 \geq 0$. Это истинное высказывание, так как для любого значения пременной $x = a \in \mathbb R$ получаем истинное высказывание $a^2 \geq 0$. Однако, высказывание $\forall x~ x^2 > 0$ ложно, например, как при $x = 0$ получаем ложное высказывание $0 > 0$.

Квантор существования

Используя квантор существования, можно составить следующее высказывание

$$\exists x~P(x),$$ которое является истинным тогда и только тогда, когда предикат $P(x)$ является истинным хотя бы при одном значении пременной $x$ из множества $D$.

Читается как: «существует $x$ такой, что $P(x)$»; «существует $x$ с условием $P(x)$» и т.п.

Квантор существования и единственности

Используя квантор существования и единственности, можно составить следующее высказывание

$$\exists! x~P(x),$$ которое является истинным тогда и только тогда, когда предикат $P(x)$ является истинным только при одном значении пременной $x$ из множества $D$.

Читается как: «существует единственный $x$ такой, что $P(x)$»; «существует единственный $x$ с условием $P(x)$» и т.п.

Отрицание «кванторов»

Пусть $P(x)$ — одноместный предикат, тогда выполняются следующие тождества: $$\begin{array}{c} \overline{\forall x~P(x)} \equiv \exists x~ \overline{P(x)},\\ \overline{\exists x~P(x)} \equiv \forall x~\overline{P(x)} \end{array}$$

Докажем первое из них. Пусть высказываине $\overline{\forall x~P(x)}$ истинно. Тогда высказывание $\forall x~P(x)$ ложно. Поэтому для некоторого $x = a$ имеем $P(a)$ ложно. Тогда $\overline{P(a)}$ истинно. Итак, для некоторого значения $x = a~\overline{P(a)}$ истинно. Поэтому высказывание $\exists x~\overline{P(x)}$ истинно.

Аналогично доказывается второе утверждение.

Применение одного из кванторов «понижает» степень предиката на единицу. Из двуместного предиката получается одноместный предикат, а из одноместного — предикат $0$ степени или высказывание.

Правила перестановки кванторов

Справедливы следующие тождества $$\begin{array}{c} \exists x~\exists y~P(x,y) \equiv \exists y~\exists x~P(x,y), \\ \forall x~\forall y~P(x,y) \equiv \forall y~\forall x~P(x,y). \end{array}$$

Однако, разноименные кванторы переставлять местами нельзя. Рассмотрим двуместный предикат $P(x, y): x + y = 0$, определенный на множестве $\mathbb R$. Тогда высказывание $\exists x~\forall y~~~ x + y = 0$ можно прочитать так: «существует $x$, которое в сумме с любым $y$ равно 0». Это ложно высказывание.

Переставим разноименные кванторы местами и получим высказывание $\forall y~ \exists x~~~ x+ y = 0$, которое можно прочитать так: «для любого $y$ существует $x$ такой, что их сумма равна 0». Это истинное высказывание. В итоге получили различные истинностные значения высказываний.

Для записи одноименных кванторов существуют следующие сокращения:

$$\begin{array}{l} \forall x~\forall y \equiv \forall x, y~~~ \text{и}\\ \exists x~\exists y \equiv \exists x, y. \end{array}$$