Предикаты. Кванторы

В текстах естественного языка часто встречаются повествовательные предложения, не являющиеся высказываниями, например эти предложения могут иметь неопределенные параметры. Например, такие предложения, как «У девочки красивая коса», «Число х — простое», «х + у = z ».

Если в такие предложения вместо параметров (переменных) поставить конкретную девочку и конкретные числа х , у , z , то получим высказывания, которые станут истинными или ложными, например «У Веры красивая коса», «Число 17 простое» или «7 + 8 = 9» и т. п.

Повествовательные предложения с параметрами называются предикатами.

Определение 9.1(предиката ). Функция Р (х 1, ... , хп), определенная на некотором множестве М и принимающая одно из двух значений: И (истина) или Л (ложь):

P : M → {И, Л},

называется п-местным предикатом .

Множество М часто задано по умолчанию обычным математическим контекстом.

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

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

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

Пример 9.1. Пусть Р (1)(х ) — предикат «х делится на два»; Q (1)( x ) — предикат «х делится на три».

Тогда выражение

Р (1)(х ) & Q (1)( x )

означает: «х делится на два и х делится на три», т. е, это выражение определяет предикат «х делится на шесть».

Аналогичным образом можно использовать все логические связки логики высказываний:

&, ∨ , ⌉ , ⇒ , ~.

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

Определение 9.2(квантора общности ). Пусть Р (х ) — некоторый предикат, принимающий значения И или Л для каждого х множества М . Под выражением ( ∀ x ) P ( x ) будем подразумевать высказывание истинное, когда Р (х ) истинно для каждого элемента х из множества М , и ложное — в противном случае. Читается оно: «для всех х Р (х )». Этот новый предикат уже не зависит от х , т. е. является высказыванием. Символ ∀ называется квантором общности, а переменная х называется связанной(квантором). Несвязанные квантором переменные обычно называются свободными.

Определение 9.3(квантора существования ). Пусть Р (х ) — некоторый предикат. Под выражением ( ∃ х )Р (х ) будем понимать высказывание истинное, когда существует элемент множества М , для которого Р (х ) истинно, и ложное — в противном случае. Читается это выражение так: «существует х такое, что Р (х )», или «существует х , для которого Р (х )». Полученный новый предикат тоже не зависит от х и является высказыванием. Символ ∃ называется квантором существования, а переменная х — связанной (квантором). Несвязанные квантором переменные обычно называют свободными.

Пример 9.2. Вернемся к примеру 9.1 о делимости на 3 и на 2. Тогда на множестве натуральных чисел предикат

(∃ х ) Р (1)(х ) & Q (1)( x )) —

истинное высказывание, а предикат

(∀ х ) Р (1)(х ) & Q (1)( x )) —

ложное высказывание.

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