§ 4. КВАНТОРЫ

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

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

Пусть — предикат от одной свободной переменной Под выражением будем подразумевать высказывание, истинное, если принимает значение И для всех допустимых значений переменной т. е. если предикат тождественно истинен, и ложное в противном случае. Высказывание уже не зависит от Символ приписываемый слева к предикату называется квантором общности по переменной Если же А есть высказывание, то есть высказывание, истинное тогда и только тогда, когда А истинно.

Рассмотрим теперь предикат от нескольких свободных переменных, например предикат от трех переменных. Этот предикат при произвольной замене всех свободных переменных, кроме их значениями бис представляет собой предикат, зависящий только от свободной переменной а выражение

есть высказывание. Предикат становится высказыванием в результате задания значений всех входящих в него свободных переменных, кроме значит, от не зависит. Таким образом, зависит от всех свободных переменных, входящих в кроме т. е. это двухместный предикат от у и z. Этот предикат на данном наборе значений свободных переменных b, с принимает значение И тогда и только тогда, когда предикат , зависящий только от одной свободной переменной является тождественно истинным. Символ можно читать так: «для всякого или «для всех х», а запись читается так: «для всякого имеет место или, короче, «для каждого

Переменная от которой предикат не зависит, называется связанной переменной (в отличие от переменных у, z, которые являются свободными).

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

Для квантора существования употребляется символ , приписываемый слева к предикату или высказыванию. Пусть — предикат от одной свободной переменной

Под выражением будем подразумевать высказывание, истинное, если принимает значение И хотя бы для одного из допустимых значений переменной т. е. предикат является выполнимым, и ложное в противном случае. Если же А — высказывание, то есть высказывание, истинное тогда и только тогда, когда А истинно.

Пусть теперь А(х, у, z) есть трехместный предикат. Если в этом предикате заменить все свободные переменные, кроме их значениями, например значениями b, с, то получится предикат А (х, b, с), зависящий только от одной свободной переменной а выражение

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

Предикат принимает значение И на данном наборе b, с допустимых значений тогда и только тогда, когда одноместный предикат выполним.

Символ называется квантором существования по переменной и читается так: «существует такое, что». Выражение читается так: «хотя бы при одном имеет место или «существует такое что

Совершенно аналогично применяются кванторы к любому предикату с большим числом переменных. В результате применения квантора к -местному предикату (при ) получается -местный предикат.

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

Скобки обычно опускают, получая при этом выражения

Отметим, что одинаковые кванторы можно переставлять, получая при этом эквивалентные высказывания, т. е. истинные эквиваленции:

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

Применение к предикату одного или нескольких кванторов (общности, существования) называется квантификацией.

Рассмотрим применение кванторов на примере. Пусть — двухместный предикат, где х и у — целочисленные переменные. Этот предикат выражает положительность суммы двух целых чисел и представляет собой некоторое высказывание всякий раз, когда переменным х и у придаются конкретные значения. Если к этому предикату применить квантор существования по переменной у, то получится одноместный предикат

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

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

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

Это последнее высказывание ложно.