Кванторы

Предикатам могут быть приписаны кванторы. Знак называется квантором общности, а знак называется квантором существования.

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

Символ интерпретируется как фраза «для всех х», соответственно - «существует х».

Выражение " x P (x) интерпретируется следующим образом: для любого х предикат Р (х) истинный.

Выражение $ х Р (х) интерпретируют следующим образом: существует такое х, что предикат Р (х) истинный.

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

Высказывание называется универсальным высказыванием для предиката . Символ происходит от первой буквы англ. all — «все».

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

Высказывание называется экзистенциальным высказыванием для предиката . Символ происходит от первой буквы англ. exist — «существовать».

В качестве примера рассмотрим предикат P (x) = «x – нечетное число».

На множестве он является тождественно истинным, поэтому для него справедливо выражение: , . На множестве выражение истинным не будет, для него справедливо выражение , .

Если одноместный предикат задан на конечном множестве , то нетрудно понять, что высказывание эквивалентно (имеет то же логическое значение) конъюнкции . В самом деле, по определению истинность высказывания означает, что предикат тождественно истинен, т.е. каждое из высказываний , в которые этот предикат превращается, истинно. Последнее равносильно истинности конъюнкции .

Если одноместный предикат задан на конечном множестве , то высказывание эквивалентно (имеет то же логическое значение) дизъюнкции . В самом деле, по определению ложность высказывания означает, что предикат тождественно ложен, т.е. каждое из высказываний , в которые данный предикат может превратиться, ложно. Последнее равносильно ложности дизъюнкции .

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

Теперь рассмотрим вопрос о применении операции связывания квантором общности или существования к предикатам с любым числом предметных переменных.

Определение 3. Операцией связывания квантором общности по переменной называется правило, по которому каждому п -местному предикату , определенному на множестве М = , ставится в соответствие новый -местный предикат, обозначаемый , который для любых предметов , , …, превращается в высказывание , истинное в том и только в том случае, когда одноместный предикат , определенный на множестве , тождественно истинен, и ложное в противном случае.

Например, рассмотрим двухместный предикат «», определенный на множестве . Применим к нему квантор общности по переменной х. Получим одноместный предикат , зависящий от переменной у. Этот предикат может превратиться как в истинное высказывание (при ), так и в ложное (при подстановке вместо у любых натуральных чисел, кроме 1).

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

Например, применив к одноместному предикату , где , квантор общности по переменной у, получим нуль-местный предикат, т.е. высказывание . Ясно, что полученное высказывание ложно, потому что предикат опровержим.

Определение 4. Операцией связывания квантором существования по переменной называется правило, по которому каждому п -местному предикату , определенному на множестве М = , ставится в соответствие новый -местный предикат, обозначаемый , который для любых предметов , , …, превращается в высказывание , ложное в том и только в том случае, когда одноместный предикат , определенный на множестве , тождественно ложен, и истинное в противном случае.

Заметим, что к -местному предикату , зависящему от переменных , можно снова применить одну из операций квантификации ‑ квантор общности или квантор существования по одной из свободных переменных. В результате получится -местные предикаты и .

Определение 5. Переменная х, входящая в предикат , называется связанной, если она находится под действием квантора или . В противном случае, переменная х в предикате является свободной.

Например, в предикате

переменные х и z ‑связанные, а переменные у и v ‑свободные.

Пример 1. Пусть A(x, y) – некоторый двухместный предикат, определённый на множестве из пяти элементов: M = {a₁, a₂, a₃, a₄, a₅}, Предикатная функция задана матрицей:

y x	a1	a2	a3	a4	a5
a1
a2
a3
a4
a5

В результате применения квантификации можно получить четыре одноместных предиката.

x	" (y) A(x, y)		y	" (x) A(x, y)
a1			a1
a2			a2
a3			a3
a4			a4
a5			a5

x	$ (y) A(x, y)		y	$ (x) A(x, y)
a1			a1
a2			a2
a3			a3
a4			a4
a5			a5

Если к оставшейся свободной переменной применить квантор, то одноместные предикаты превратятся в высказывания:

$ (x) " (y) A(x, y)= 1 $ (y) " (x) A(x, y)= 0

" (x) $ (y) A(x, y)= 1 " (y) $ (x) A(x, y)= 1

Порядок применения разноимённых кванторов существенен и может привести к различным высказываниям.

Пример 2.

1. Пусть предикат определен на множестве натуральных чисел.

Предикат означает ‑ «для всякого х существует такое y, что x делит y». Это утверждение истинно. Если кванторы поменять местами, то получим предикат , значение которого ‑ «существует такое число y, что любое х его делит». Это утверждение ложно.

2. Пусть ‑ предикат, определенный на множестве людей. Тогда означает, что у каждого человека х есть мать у. Предикат с другим порядком кванторов означает ложное утверждение, что существует мать всех людей.