Предикат. Примеры предикатов: разрешимых, тождественно истинных, тождественно ложных. Операции над предикатами. Множество истинности предиката.

Предикаты – это отображения произвольных множеств во множество высказываний. Логика предикатов представляет собой развитие логики высказываний.

Определение предиката 

Пусть Х₁, Х₂, ..., Х_п произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных выбираются из множества X, которые будем называть предметной областью. Предикатом местности n (n - местным предикатом), определенным на предметной области X, называют отображение множества X во множество высказываний. Обозначение: P( )- n - местный предикат, определенный на X:=( ).

Пример:   «х простое число».

Это выражение не является высказыванием, но если в нем переменную х заменить на определенное число, то получим высказывание. Причем при замене х на число 3 получим истинное высказывание, тогда как при замене х на 8 получим ложное высказывание.

Таким образом, выражение: «х простое число» можно рассматривать как функцию Р(х), зависящую от переменной х. Область определения Р(х) — множество чисел, а область значения — высказывание.

Предикаты - отображения произвольных множеств во множество высказываний. Пусть х₁, х₂, . . . , х_n - произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных х₁, х₂, . . . , х_n выбираются из множества X, которые будем называть предметной областью.

Предикатом местности n (n-местным предикатом), определенным на предметной области X, называют отображение множества X во множество высказываний.

Обозначение: P(х₁, х₂, . . . , х_n) - n-местный предикат, определенный на X:={х₁, х₂, . . . , х_n}.

Дадим другое определение предиката.

N-местный предикат - это связное повествовательное предложение, содержащее n переменных и обладающее следующим свойством: при фиксации всех переменных о нем (предложении) можно сказать, истинно оно или ложно.

Примеры.

1) Р(х₁, х₂) "Натуральное число х₁делится (без остатка) на натуральное число х₂" - двуместный предикат, определенный на множестве пар натуральных чисел (х₁, х₂ N ).  Очевидно Р(4, 2) =1;  Р(5, 3) = 0

2) Р(х) = “x² < -1, xR” - одноместный предикат, определенный на R.

Ясно, что Р(-1) = 0 и вообще предикат P(x) - тождественно ложен, т.е. Р(x) = 0

3) Р(х, y, z) = “x² + y² ≤ z,   x,y,xR” - трехместный предикат, определенный на R³.   Р(1, 1, -2) = 0,    Р(1, 1, 2) = 1

Предикат — это функция, значениями которой являются высказывания о п объектах, представляющих значения аргументов.

С помощью формальных теорий можно описать обширный класс высказываний, называемых предикатами. Дадим опреде­ление исчисления предикатов как формальной теории, а затем подробно остановимся на интерпретации.

Определение 1 (предиката). Функция Р(х₁, ... ,х_п), опре­деленная на некотором множестве М и принимающая одно из двух значений: И (истина) или Л (ложь):

Р: М → {И, Л},

называется п-местным предикатом.

Произвольная функция Р: Мⁿ→В, заданная на произвольном множестве М, называется n-местным предикатом Р(х₁, х₂, . . .,x_n), т.е. Р задает семантическую характеристику.

Формальная теория S = <A, F, Р, R> называется исчислением предикатов первого порядка, если заданы алфавит, формулы, ак­сиомы и правила вывода.

​

Тождественно-истинным называется предикат, истинный всю­ду на области определения: Т(Р) = D(P).

Тождественно-ложным называется предикат, множество истинности которого пусто: Т(Р) = 0.

РАЗРЕШИМЫЙ ПРЕДИКАТ

такой n-местный предикат Р, заданный на нек-ром множестве конструктивных объектов (напр., натуральных чисел) М, для к-рого существует алгоритм, позволяющий для любого набора а _1; . . ., а _п элементов множества Мнайти значение (И или Л) предиката Рна этом наборе. Иными словами, предикат является разрешимым, если он, рассматриваемый как n-местная функция на Мсо значениями во множестве {И, Л}, является вычислимой функцией.