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

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

Определение 8.2. Любое отображение Р: Мⁿ ® W называется n-местным предикатом на множестве М. n -местный предикат, содержащий переменные x ₁, …, x_n обозначим через Р (x ₁, …, x_n). Переменные x ₁, …, x_n принимают значения из множества М. Если a — значение предиката Р (x ₁, …, x_n) при x ₁ = a ₁, …, x_n = a_n, то будем писать P (a ₁, …, a_n) = 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: N ³ -> W:

Замечание 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 -местных предикатов на множестве М. В связи с этим множество М с системой определенных на нем предикатов s называется, как и множество М с системой отношений, моделью сигнатуры s и обозначается М (s).

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

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) º и, для всех значений х.

Дата добавления: 2014-12-29