Кванторы

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

а) Выражение ( x)P(x) означает высказывание, истинное только в том случае, когда предикат Р( х) истинен для всех предметов из поля М. Выра­жение ( x)P(x) читается «для всякого х, Р(х)», здесь символ ' ' - квантор общности.

б) Выражение ( х)Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен хотя бы для одного предмета из по­ля М. Выражение ( х)Р(х) читается «существует х, что Р(х»); символ ­ - квантор существования .

Рассмотрим примеры применения операций квантирования к преди­катам. Пусть даны предикаты над полем натуральных чисел:

1) х² = х· х, тогда ( x)(x² = х· х) - истинное высказывание;

2) х + 2 = 7, тогда ( x)(x + 2 = 7) - ложное высказывание; а ( х)(х + 2 = 7) - истинное высказывание;

3) х + 2 = х, тогда (' x)(x + 2 = х) - ложное высказывание.

Квантор общности - это оператор, приводящий в соответствии лю­бому заданному предикату y = Р(х) такую двузначную логическую пере­менную z, которая принимает значение 1 тогда и только тогда, когда у = 1 при всех значениях х.

Квантор существования - это оператор, приводящий в соответствии любому одноместному предикату y = Р(х) такую двузначную логическую переменную z, которая принимает значение 0 тогда и только тогда, когда у = 0 при всех значениях х.

Рассмотрим некоторые общие свойства введенных операторов.

В соответствии с определениями кванторов логическая переменная z в выражениях

z = ( x)P(x) z = ( х)Р(х)

уже не является функцией предметной переменной х.

Для того чтобы отметить отсутствие функциональной зависимости z от х, предметную переменную х в таких случаях называют связанной. Несвязанные переменные называют свободными.

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

( x)A(x, у) ˅ ( z)B(z, v)

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

Если квантор общности или квантор существования применяется не к одно-местному предикату, а к какому-нибудь k-местному предикату, то в результате этого получается снова предикат, но за счет связывания одной предметной переменной получаемый предикат будет (k - l)-местным.