8.2. Предикаты и операции над ними

Пусть М — произвольное непустое множество, и n  N  {0}. Мⁿ — n-я декартова степень множества М.

Определение 8.2. Любое отображение Р: Мⁿ   называется n-местным предикатом на множестве М. n-местный предикат, содержащий переменные x₁, …, x_n обозначим через Р(x₁, …, x_n). Переменные x₁, …, x_n принимают значения из множества М. Если  — значение предиката Р(x₁, …, x_n) при x₁ = a₁, …, x_n = a_n, то будем писать P(a₁, …, a_n) = .

Пример 8.3. M = N, n = 1. Тогда предложение «Х есть простое число» есть 1-местный предикат на множестве N. Обозначим это предложение через Р(х). Тогда Р: N  , где

Пример 8.4. M = N, n = 3. Тогда предложение «Число z является суммой чисел x, y» есть 3-местный предикат на множестве N. Обозначим это предложение через P(x, y, z). Тогда P: N³ -> :

Замечание 8.5. Любой n-местный предикат Р(x₁, …, x_n) на множестве М при фиксации переменных x₁, …, x_n превращается в высказывание.

Замечание 8.6. Под 0-местным предикатом понимается произвольное высказывание. При этом нуль-местных предикатов ровно два — истинный и ложный. Множество М⁰ — одноэлементно, (содержит единственную последовательность элементов множества М длины нуль). Поэтому М⁰  Ω отождествляются с элементами множества Ω (нуль-местных предикатов ровно два — истинный и ложный).

Замечание 8.7. По n-местному предикату Р(x₁, …, x_n) естественным образом определяется n-арное отношение R на множестве М:  (a₁, …, a_n)  Мⁿ положим (a₁, …, a_n)  R  Р(a₁, …, a_n)  и. Тем самым устанавливается взаимооднозначное соответствие между множествами n-арных отношений и всех n-местных предикатов на множестве М. В связи с этим множество М с системой определенных на нем предикатов  называется, как и множество М с системой отношений, моделью сигнатуры  и обозначается М().

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

1. Пусть Р(x₁, …, x_n) произвольный предикат на М. Заменив в нем х₁ некоторым элементом а  М, мы получим новый, (n – 1)-местный предикат на М, который будем обозначать в виде Р(а, x₂, …, x_n) или каким-либо иным образом, например, q(x₂, …, x_n). Аналогично, новые предикаты можно получать из предиката Р(x₁, …, x_n), заменяя в нем какую-либо другую переменную или даже несколько переменных элементами из М. Ясно, что заменив к переменных, получим (n – k)-местный предикат.

Пример 8.8. Рассмотрим 3-местный предикат

на множестве N. Заменив х на 2, получим новый 2-местный предикат P(2, y, z)

который можно записать, например, в виде «Число z на две единицы больше числа y».

2. Пусть Р(x₁, …, x_n) — произвольный предикат на множестве М и n  2. Заменим х₁ на х₂ (или, как говорят, отождествим переменные х₁, х₂). В результате получим (n – 1)-местный предикат Р(x₁, х₂, х₃, …, x_n). Аналогично можно получить из предиката Р(x₁, …, x_n) новые предикаты, отождествляя какие-либо другие переменные.

Пример 8.9. Отождествляя переменные х и у в предикате из примера 8.7, получим 2-местный предикат

на множестве N. Этот новый предикат можно записать, например, в виде предложения «Число z в два раза больше числа у».

3. Учитывая связь понятия предиката с понятием высказывания, можно определить логические операции для предикатов. Если Р — n-местный предикат, а q — m-местный предикат, и переменные, входящие в Р, не входят в q, то через P  q обозначим (m + n)-местный предикат, значение которого при конкретных значениях переменных равно дизъюнкции соответствующих значений предикатов P и q. Аналогично определяются конъюнкция и импликация предикатов, а также отрицания предиката.

4. Кроме операций , , , для предикатов на множестве можно определить еще логические операции навешивания кванторов всеобщности и существования. Рассмотрим n-местный предикат Р(x₁, …, x_n) на множестве М.

 Добавив к нему фразу «Для всех х₁» или «Для всякого х₁», получим новое предложение, которое обозначим в виде

 x₁ Р(x₁, …, x_n). (8.1)

Из построения этого предложения видно, что при замене в нем переменных х₂, …, х_n соответственно элементами а₂, …, а_n получится высказывание

 x₁ Р(x₁, а₂, …, а_n),

которое истинно в том и только том случае, когда высказывание Р(а, а₂, …, а_n) истинно при любом а  М. Таким образом, (8.1) является (n – 1)-местным предикатом. При этом говорят, что предикат (8.1) получен из предиката Р навешиванием квантора всеобщности по переменной х₁. Отметим, что квантор всеобщности  можно навешивать и по другим переменным.

 Добавляя перед предикатом Р(x₁, …, x_n) фразу «Существует х₁, такое что», получим новое предложение, которое обозначается в виде

 x₁ Р(x₁, …, x_n). (8.2)

Подставив в него элементы а₂, …, а_n вместо x₂, …, x_n, получим высказывание

 x₁ Р(x₁, а₂, …, а_n),

которое истинно в том и только том случае, когда высказывание Р(а, а₂, …, а_n) истинно хотя бы при одном а из М. Следовательно, предложение (8.2) есть (n – 1)-местный предикат на М. Символ  называется квантором существования, а о предложении (8.2) говорят, что оно получено из предиката Р(x₁, …, x_n) навешиванием квантора существования по переменной х₁. Квантор существования  можно навешивать и по другим переменным.

Пример 8.10. Пусть Р(х, у) есть предикат на N

тогда предложение

у Р(х, у)

зависит только от переменной х. При х = 1 оно принимает значение «и», так как 1 делит любое натуральное число. При любом другом значении х из N оно принимает значение «л», т.е.

у

Предложение

х P(x, y)

зависит только от переменной у и принимает значение «л» при любом значении у, поскольку в N не существует чисел, делящихся на все натуральные числа, т.е. х P(x, y) = л.

Пример 8.11. Р(х, у) — то же самое, что и в примере 8.10, тогда

х P(x, y)  и

зависит от у и принимает значение «и» для всех значений у. Аналогично у P(x, y)  и, для всех значений х.

Л е к ц и я 9