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

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

Определение 8.2. Любое отображение Р: МN ® W называется n-местным предикатом на множестве М. N-местный предикат, содержащий переменные X1, …, XN обозначим через Р(X1, …, XN). Переменные X1, …, XN принимают значения из множества М. Если a — значение предиката Р(X1, …, XN) при X1 = A1, …, XN = AN, то будем писать P(A1, …, AN) = a.

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

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

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

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

Замечание 8.7. По N-местному предикату Р(X1, …, XN) естественным образом определяется N-арное отношение R на множестве М: " (A1, …, AN) Î МN положим (A1, …, AN) Î R Û Р(A1, …, AN) º и. Тем самым устанавливается взаимооднозначное соответствие между множествами N-арных отношений и всех N-местных предикатов на множестве М. В связи с этим множество М с системой определенных на нем предикатов s называется, как и множество М с системой отношений, Моделью сигнатуры S и обозначается М(s).

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

1. Пусть Р(X1, …, XN) произвольный предикат на М. Заменив в нем Х1 некоторым элементом А Î М, мы получим новый, (N – 1)-местный предикат на М, который будем обозначать в виде Р(А, X2, …, XN) или каким-либо иным образом, например, Q(X2, …, XN). Аналогично, новые предикаты можно получать из предиката Р(X1, …, XN), заменяя в нем какую-либо другую переменную или даже несколько переменных элементами из М. Ясно, что заменив к переменных, получим (N – K)-местный предикат.

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

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

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

2. Пусть Р(X1, …, XN) — произвольный предикат на множестве М и N ³ 2. Заменим Х1 на Х2 (или, как говорят, отождествим переменные Х1, Х2). В результате получим (N – 1)-местный предикат Р(X1, Х2, Х3, …, XN). Аналогично можно получить из предиката Р(X1, …, XN) новые предикаты, отождествляя какие-либо другие переменные.

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

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

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

4. Кроме операций &, Ú, ®,` для предикатов на множестве можно определить еще логические операции Навешивания кванторов всеобщности и существования. Рассмотрим N-местный предикат Р(X1, …, XN) на множестве М.

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

" X1 Р(X1, …, XN). (8.1)

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

" X1 Р(X1, А2, …, АN),

Которое истинно в том и только том случае, когда высказывание Р(А, А2, …, АN) истинно при любом А Î М. Таким образом, (8.1) является (N – 1)-местным предикатом. При этом говорят, что предикат (8.1) Получен из предиката Р навешиванием квантора всеобщности по переменной х1. Отметим, что квантор всеобщности " можно навешивать и по другим переменным.

· Добавляя перед предикатом Р(X1, …, XN) фразу «Существует Х1, такое что», получим новое предложение, которое обозначается в виде

$ X1 Р(X1, …, XN). (8.2)

Подставив в него элементы А2, …, АN вместо X2, …, XN, получим высказывание

$ X1 Р(X1, А2, …, АN),

Которое истинно в том и только том случае, когда высказывание Р(А, А2, …, АN) истинно хотя бы при одном А из М. Следовательно, предложение (8.2) есть (N – 1)-местный предикат на М. Символ $ называется квантором существования, а о предложении (8.2) говорят, что оно получено из предиката Р(X1, …, XN) навешиванием квантора существования по переменной Х1. Квантор существования $ можно навешивать и по другим переменным.

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

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

"У Р(Х, У)

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

"у

Предложение

"Х P(X, Y)

Зависит только от переменной У и принимает значение «л» при любом значении У, поскольку в N не существует чисел, делящихся на все натуральные числа, т. е. "Х P(X, Y) = л.

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

$Х P(X, Y) º и

Зависит от У и принимает значение «и» для всех значений У. Аналогично $У P(X, Y) º и, для всех значений Х.

< Предыдущая		Следующая >