Предикаты. Основные понятия

п-местный предикат - это функция Р(х₁ х₂, х_п) от п переменных, принимающих значения из некоторых заданных предметных областей, так что,a функция P принимает два логических значения – «истинно» или «ложно».

Таким образом, предикат Р(х_1, х_2, ..., х_п) является функцией типа , где множества, называются предметными областями предиката; х_1, х_2, ..., х_п -предметными переменными предиката; В = {1,0}.

Соответствия между предикатами, отношениями и функциями:

1. Для любых М и п существует взаимно однозначное соответствие между n-местными отношениями u n-местными предикатами Р(х_1, х_2, ..., х_п), :

• каждому n-местному отношению R соответствует предикат Р(х_1, х_2, ..., х_п), такой, что Р(a_1, a_2, ...,a_п) = 1, если и только если (a_1, a_2, ..., a_п) Î R;

• всякий предикат Р(х_1, х_2, ..., х_п) определяет отношение R такое, что (a_1, a_2, ..., a_п) Î R, если и только если Р(a_1, a_2, ...,a_п) = 1.

При этом R задает область истинности предиката Р.

2. Всякой функции f(х_1, х_2, ..., х_п) , соответствует предикат Р(х_1, х_2, ..., х_п, х_п+1)=1такой, что Р(a_1,a_2, ..., a_п, a_п+1)=1, если и только если f(a_1, a_2, ..., a_п)=a_n+1.

Обратное соответствие (от (n+1)-местного предиката (рис. 2.17) к n-местной функции) возможно не всегда, а только для таких предикатов Р^’ для которых выполняется условие (связанное с требованием однозначности функции): Р(a_1, a_2, ...,a_п, a_п+1) = 1, то для любого

a^’_п+1 ≠a_п+1 Р(a_1, a_2, ...,a_п, a^’_п+1) = 0 {1}

Аналогичное соответствие (взаимно однозначное) имеется между подмножеством отношений {R'}{R} и множеством функций {f}.

Для этого класса отношений выполняется аналогичное условие: если (a_1,a_2, ..., a_п, a_п+1) Î R^’ то для любого a^’_п+1 ≠a_п+1, (a_1,a_2, ..., a_п, a_п+1)R^’

Выражение Р(a_1, a_2, ...,a_п) будем понимать как высказывание «Р(a_1, a_2, ...,a_п)=1», а выражение Р(х_1, х_2, ..., х_п) - как переменное высказывание, истинность которого определяется подстановкой элементов множества М вместо переменных (х_1, х_2, ..., х_п).

Для обозначения двухместных предикатов помимо префиксной записи Р(х_1, х₂) используется нередко инфиксная запись х₁Рх₂

Пример 2.

Каким отношениям и функциям соответствуют следующие предикаты, определенные на множестве натуральных чисел:

1. Предикат тождества E:N²→В: Е(а_], а₂) = 1 тогда и только тогда, когда а_]=а₂

Двухместному предикату тождества Е – «x_]=x₂» взаимно однозначно соответствуют:

а) двухместное отношение R₁ , - «быть равным», , тогда и только тогда, когда Е (a₁, а₂) = 1;

б) одноместная функция (операция) тождества f₁(x₁)=х₂, а именно:.

2. Предикат делимости D: N²→В: D (а_], а₂) = 1 тогда и только тогда, когда а_]делится на а₂:

Двухместному предикату делимости D – «х₁ делится на х₂» взаимно однозначно соответствует двухместное отношение R₂ – «делиться», тогда и только тогда, когда D (a₁, а₂) = 1. Однако функции f₁(x₁)=х2 для предиката делимости D (x₁, x₂) не существует, так как не выполнено условие (1), например D(6, 2) = 1 и D(6, 3) = 1, однако 2≠3.

3. Предикат суммы S:N³→В: S(а_1, а_2, а₃) = 1 тогда и только тогда, когда а₁+a₂ = a₃.

Трехместному предикату суммы S – «x₁+x₂ =x₃» взаимно однозначно соответствуют:

а) трехместное отношение: тогда и только тогда, когда S(а_1, а_2, а₃) = 1;

б) двухместная функция (операция арифметики) - сложение f(х₁, х₂) = х₃, а именно: х₁ + х₂ = х₃.