Материал предоставлен http://it.rfet.ru

Кванторы

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

Предикаты. Операции над предикатамиПроверка знаний. Предикаты