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

Пусть М — произвольное непустое множество, и 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) º и, для всех значений х.

Л е к ц и я 9