Кванторы

Пусть P(x) – одноместный предикат, заданный на некотором множестве M. Если переменная x обозначает любой элемент из множества M, то P(x) является неопределенным высказыванием.

Операция " ставит в соответствие неопределенному высказыванию P(x) высказывание "xP(x), которое читается так: «для любого x имеет место P(x)» и по определению является истинным тогда и только тогда, когда P(x) истинно для любого элемента xÎM. Переход от неопределенного высказывания P(x) к высказыванию "xP(x) называется операцией навешивания квантора общности по предметному переменному x.

Операция $ ставит в соответствие неопределенному высказыванию P(x) высказывание $xP(x), которое читается так: «существует такое x, что имеет место P(x)» и по определению является истинным тогда и только тогда, когда P(x) истинно хотя бы для одного элемента xÎM. Переход от неопределенного высказывания P(x) к высказыванию $xP(x) называется операцией навешивания квантора существования по предметному переменному x.

В первом случае мы говорим, что предметная переменная x связана в предикате P(x) квантором всеобщности, во втором случае – квантором существования.

Определим операции навешивания квантора для общего случая n-местного предиката P(x₁,…,x_n). Операции навешивания кванторов " и $ по переменному x₁ (в общем случае по переменному x_i, где I= ) ставит в соответствие предикату P(x₁,…,x_n) (n-1) – местные предикаты

"x₁P(x_1,…, x_n) и $x₁P(x_1,…, x_n)

соответственно.

Истинностные значения этих предикатов определяются для фиксированных наборов значений предметных переменных x₂,…,x_n следующим образом:

"x₁P(x_1,a_2…,a_n)=

$x₁P(x_1,a_2…,a_n)=

В общем случае, если k<n, то операцию навешивания квантора можно повторить k раз. Тогда переменные x₁,…,x_k в таком предикате будут связанными, а переменные x_k+1,…,x_n – свободными. При k=n предикат становится высказыванием.

Примеры.

Рассмотрим предикат Д(x₁,x₂) – «число x₁ делится на число x₂», определенный на множестве натуральных чисел. Тогда операция навешивания кванторов приводит к следующим утверждениям:

1. "x₁Д(x_1, x₂) – «для любого x₁ имеет место Д(x₁,x₂)», т.е. всякое x₁ делится на x₂. Этот предикат принимает значение истины только для х₂=1.

2. $x₁ Д(x_1, x₂) – «существует x_1, которое делится на x₂». Этот предикат принимает значение истины для любого значения x₂.

3. "x₁"x₂Д(x_1, x₂) – «для всякого x₁ и для всякого x₂ имеет место делимость x₁ на x_2. Это высказывание является ложным.

4. $x₁"x₂Д(x_1, x₂) – «существует x₁, которое делится на всякое x₂» – ложное высказывание.

5. "x₂$x₁Д(x_1, x₂) – «для всякого x₂ существует x₁ такое, что x₁ делится на x₂» – истинное высказывание.