В алгебре высказываний применяют логические знаки для записи различных утверждений. Однако нам не достаточно этих знаков для выражения мысли типа «Всякий элемент %%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} $$
| Предикаты. Операции над предикатами | Проверка знаний. Предикаты |