6.4. ПЕРЕМЕННЫЕ И КВАНТОРЫ

Рассмотрим п. п. формулу

и интерпретацию

— конечное множество целых чисел ,

а — число 30,

b — число 1,

Р — отношение «больше или равно».

При такой интерпретации п. п. формула утверждает, что «30 больше или равно 1». Это утверждение, очевидно, истинное, и наша п. п. формула при данной интерпретации имеет значение Т. Предположим, что при той же самой области мы приписываем значения константным буквам соответственно. С каждой из этих букв можно сконструировать формулу вида

При этом каждая из п. п. формул при данной интерпретации имеет значение Т.

Часто бывает нужно высказать определенное утверждение, относящееся к каждому элементу некоторой области. Такое утверждение можно было бы сделать в виде конъюнкции п. п. формул, утверждение каждой из которых касается одного из элементов. В рассмотренном выше примере п. п. формула

утверждает, что «каждое целое число от 1 до 100 больше или равно 1». Так как каждая п. п. формула имеет значение Т, то мы устанавливаем с помощью таблиц истинности, что эта конъюнкция также имеет значение Т.

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

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

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

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

в любой интерпретации имеет значение Т.)

Иногда требуется высказать утверждение, касающееся всех пар элементов из некоторой области или всех троек и т. Тогда используется несколько переменных и для каждой из них символ V. Так, правильно построенную формулу, соответствующую утверждению «для всех пар целых чисел, расположенных между 1 и 100, первое больше второго», можно запиеать в виде

Очевидно, что эта п. п. формула (двойная конъюнкция) при нашей интерпретации имеет значение

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

где — элементы области Согласно таблице истинности, эта правильно построенная формула имеет значение Т,

когда верно утверждение «по крайней мере один элемент из D обладает, свойством

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

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

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

При комбинировании кванторов всеобщности и существования действие квантора существования может оказаться «зависящим» от каких-нибудь предшествующих кванторов всеобщности. Так, утверждение «для любого целого числа существует большее целое число» можно записать в виде

Очевидно, что если эта п. п. формула должна иметь значение Т, то переменная у, которая «существует», должна зависеть от х.

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