Кванторные операции над предикатами

Специфика природы предикатов позволяет ввести такие операции над ними, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами (или операции квантификации) — квантор общности ∀ и квантор существования ∃.

Кванторы в явном виде впервые были введены немецким математиком Готлобом Фреге в работе "Begriffsschrift" ("Исчисление понятий", 1879). В 1885 г. английский логик Чарльз Пирс ввел термины "квантор", "квантификация", происшедшие соответственно от лат. quantun — "сколько" и лат. quantun + facio — "делать". Это означает, что квантор показывает, о скольких (всех или некоторых) объектах говорится в том или ином предложении. Символику для кванторов в виде перевернутых латинских букв ввел итальянский математик Дж. Пеано в 90-е гг. XIX в. После использования кванторов математиками Пеано, Шредером, Расселом они стали широко использоваться.

Кванторами называются символы ∀ и ∃, являющиеся сокращением:

∀ – «для любого», «для каждого», «для всех»;

∃ – «существует», «найдётся».

 

Помимо кванторов и вместе с ними часто используются символы «!»,

«:», «|», являющиеся сокращением:

! – «единственный»;

: – «такой, что»;

| – «такой, что».

При этом «:» используется, как правило, в формулировках определений и теорем, записываемых при помощи кванторов, например, в определении предела последовательности. В то же время, знак «|» применятся в определениях множеств.

 

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

Известно, что для превращения одноместного предиката в высказывание нужно подставить вместо его переменной какой-нибудь конкретный предмет из области задания предиката. Имеется еще один способ для такого превращения — это применение к предикату операций

связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного предиката.

 

Определение: Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату P(x), определенному на множестве M, сопоставляется высказывание, обозначаемое (∀x)(P(x)) (читается: "для всякого [значения] x - P(x) [истинное высказывание]"), которое истинно в том и только в том случае, когда предикат P(x), тождественно истинен, и ложно в противном случае.

 

Пример 15.

Рассмотрим два одноместных предиката на множестве N: «0≤ х» (х больше или равен нуля) и «х | 30» (х – делитель 30). Первый предикат тождественно истинный, поэтому применение к нему операции связывания квантором общности дает истинное высказывание: (∀ x)(0≤х) — "для всякого х число 0 не превосходит х ". Второй предикат опровержим, поэтому операция связывания квантором общности, примененная к нему, дает ложное высказывание: (∀ x)(х | 30) — "для любого х число х является делителем числа 30".

 

Если одноместный предикат P(x), задан на конечном множестве M={a₁,a₂,…a_n}, то высказывание (∀x)(P(x)) эквивалентно (имеет то же логическое значение) конъюнкции P(a₁)˄P(a₂)˄…˄P(a_n). В самом деле, по определению истинность высказывания (∀x)(P(x)) означает, что предикат тождественно истинен, т.е. каждое из высказываний P(a₁), P(a₂), …, P(a_n), в которые этот предикат превращается, истинно. Последнее равносильно истинности конъюнкции P(a₁)˄P(a₂)˄…˄P(a_n).

Следовательно, для предикатов, заданных на конечном множестве, операция связывания квантором общности может быть выражена через конъюнкцию. Для предикатов, заданных на бесконечном множестве, такого сделать нельзя, и в этом случае операция связывания квантором общности является существенно новой.

Можно подметить еще одну особенность операции связывания квантором общности по сравнению с ранее описанными операциями: они ставили в соответствие одному или двум предикатам новый предикат, а операция связывания квантором общности сопоставляет предикату высказывание. На это можно сказать следующее. Во-первых, каждое высказывание для достижения большей общности сейчас и в дальнейшем можно рассматривать как предикат, содержащий 0 предметных переменных, т. е. как нульместный предикат. Во-вторых, мы пока применяли квантор общности лишь к одноместным предикатам. Переходим к рассмотрению вопроса о применении операции связывания квантором общности к предикатам с любым числом предметных переменных; такая операция

предстанет операцией в полном смысле слова: предикатам она будет сопоставлять предикаты.

 

Определение: Операцией связывания квантором общности по переменной х₁ называется правило, по которому каждому n-местному (n≥2) предикату P(x, x₂, …, x_n), определенному на множествах M₁, M₂, …, M_n, ставится в соответствие новый (n-1)-местный предикат, обозначаемый (∀x)(P(x, x₂, …, x_n)), (читается: "для всех х₁ P(x, x₂, …, x_n), который для любых предметов a₂∈M₂, …, a_n∈M_n превращается в высказывание (∀x₁)(P(x, a₂, …, a_n)), истинное в том и только в том случае, когда одноместный предикат P(x, a₂, …, a_n), определенный на множестве M₁ тождественно истинный, и ложное в противном случае.

 

Пример 16.

Например, рассмотрим двухместный предикат "y≤x", определенный на множестве N ². Применим к нему квантор общности по переменной x. Получим одноместный предикат (∀ x)(y≤x), зависящий от переменной y. Этот предикат может превратиться как в истинное высказывание (при y =1), так и в ложное (при подстановке вместо y любых натуральных чисел, кроме 1).

 

Пример 17.

Двухместный предикат "(x+y)²=x²+2xy+y² ", определенный на R ², тождественно истинен. Поэтому применение к нему квантора общности по любой переменной, например по у, дает одноместный предикат (по x), который будет тождественно истинным (∀ x)((x+y)²=x²+2xy+y²)

 

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

 

Определение: Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату P(x), определенному на множестве M, ставится в соответствие высказывание, обозначаемое (∃x)(P(x)) (читается: "существует [значение] x, такое, что P(x), [истинное высказывание]"), которое ложно в том и только в том случае, когда P(x), тождественно ложен, и истинно в противном случае.

 

Пример 18.

рассмотрим два одноместных предиката, определенных на множестве N:

«x=x+1» и «х | 30». Первый предикат тождественно ложный, поэтому применение к нему операции связывания квантором существования дает ложное высказывание: (∃ x)(x=x+1) - "существует натуральное число, равное себе плюс 1". Второй предикат выполним, поэтому операция связывания квантором существования, примененная к нему, дает истинное высказывание: (∃ x)(х | 30) - "существует натуральное число, делящее число 30".

Если одноместный предикат P(x), задан на конечном множестве M={a₁,a₂,…a_m},, то высказывание (∃x)(P(x)) эквивалентно (имеет то же логическое значение) дизъюнкции P(a₁)˅P(a₂)˅…˅P(a_m). В самом деле, по определению ложность высказывания (∃x)(P(x)) означает, что предикат P(x), тождественно ложен, т.е. каждое из высказываний P(a₁), P(a₂), …,P(a_m), в которые данный предикат может превратиться, ложно. Последнее равносильно ложности дизъюнкции P(a₁)˅P(a₂)˅…˅P(a_m).

Значит, для предикатов, заданных на конечном множестве, операция связывания квантором существования может быть выражена через дизъюнкцию. Для предикатов, заданных на бесконечном множестве, такого сделать нельзя, и в этом случае операция связывания квантором существования является существенно новой.

 

Определение: Операцией связывания квантором существования по переменной х₁ называется правило, по которому каждому n-местному (n≥2) предикату P(x₁, x₂, …, x_n), определенному на множествах M₁, M₂, …, M_n, ставится в соответствие новый (n-1)-местный предикат, обозначаемый (∃x)(P(x₁, x₂, …, x_n), (читается: "существует такой х₁ что P(x₁, x₂, …, x_n), который для любых предметов a₂∈M₂, …, a_n∈M_n превращается в высказывание (∃x₁)(P(x₁, а₂, …, а_n)), ложное в том и только в том случае, когда одноместный предикат (P(x₁, а₂, …, а_n)), определенный на множестве M₁,тождественно ложен, и истинное в противном случае.

 

Пример 19.

Например, рассмотрим двухместный предикат " y≤x ", определенный на R². Применим к нему квантор существования по переменной x. Получим одноместный предикат (∃ x)(y≤x), зависящий от переменной y. Этот предикат всегда превращается в истинное высказывание, если вместо у подставлять конкретные числа, т.е. он является тождественно истинным предикатом.

 

 

Пример 20.

В другом примере двухместный предикат " x²+y² <0", определенный на R ², тождественно ложен. Поэтому применение к нему квантора существования по любой переменной, например по x, дает одноместный (по y) предикат, который будет тождественно ложным: (∃ x)(x²+y² <0).

 

Кванторы $ и " могут использоваться и для любого числа переменных.

 

Рассмотрим их различное использование на примере двухместного предиката любит (Х, У), который описывает отношение: «X любит Y»):

 

("X) ("Y) любит (Х, Y) – «все люди любят всех людей»

($Х) ("Y) любит (Х, Y) – «существует человек, который любит всех

("Х) ($Y) любит (Х, Y) – «для каждого человека существует тот, который его любит»

($X) ($Y) любит (Х, Y) – «существует человек, который кого-нибудь любит».

 

Применение кванторов к естественному языку:

"х A(x)	Для любого х (имеет место) А(х) А(х) при произвольном х Для всех х (верно) А(х) А(х), каково бы ни было х Для каждого х (верно) А(х) Всегда имеет место А(х) Каждый обладает свойством А Свойство А присуще всем Всё удовлетворяет А Любой объект является А Всякая вещь обладает свойством А	"х A(x)	Для всякого х неверно А(х) А(х) всегда ложно ничто не обладает свойством А всё суть не А
$х A(x)	Для некоторых х (имеет место) А(х) Для подходящего х (верно) А(х) Существует х, для которого (такой, что) А(х) Имеется х, для которого (такой, что) А(х) Найдется х, для которого (такой, что) А(х) У некоторых вещей есть признак А Хотя бы для одного х (верно) А(х) Кто-нибудь относится к (есть) А По крайней мере, один объект есть А	$х A(x)	Не существует х такого, что А(х) Нет никакого х, такого, что А(х) Нет х, такого, что А(х) А(х) не выполняется ни для какого х Ничто не обладает свойством А Никто не есть А Неверно, что для некоторых х А(х) Ни для какого х не верно А(х)
"х A(x)	Не для каждого х (имеет место) А(х) Не при всяком х (верно) А(х) А(х) оказывается истинным не для всех х Не всё обладает свойством А Не все суть А А не всегда верно	$х A(x)	Для некоторого х неверно А(х) Что-то не обладает свойством А Кто-то есть не А