Логика предикатов

1. Логика предикатов

2. Понятие предиката

3.

ПРЕДИКАТ (лат. praedicatum – высказанное)
– термин, обозначающий член предложения –
сказуемое.
Пример. Студент уныло слушает лекцию.
Субъект Атрибут Предикат Объект

4.

Другое
значение
выражение
термина
отношения
«предикат»
между
лицами,
предметами, событиями, явлениями.
Пример. Студент уныло слушает лекцию.
Слушает (кто, кого, как)
–

5.

Определение.
Предикатом
называется
утверждение, содержащее переменные x1 ,..., xn ,
которое превращается в высказывание при замене
этих переменных конкретными объектами из
некоторой области возможных значений.
Обозначаются предикаты P,Q,...
Переменные x1 ,..., xn , называются предметными
или индивидуальными переменными. Число
предметных переменных в предикате называется
его арностью или местностью.
Более точно, предикат P с n предметными
переменными называется n-арным или n-местным
предикатом и обозначается P x1 ,..., xn .

6.

Предикат P x1 ,..., xn является функцией,
которая
каждому
набору
значений
x1 a1 ,..., xn an его n предметных переменных
x1 ,..., xn ставит в соответствие некоторое
P a1 ,..., an ,
высказывание
имеющее
определенное
истинностное
значение
( P a1 ,..., an ) .
Если
отвлечься
от
содержания
высказываний и учитывать только их
истинностные значения, то предикат можно
рассматривать как функцию со значениями в
множестве 0,1 .

7.

Рассматривая такую функцию на некотором
фиксированном множестве M допустимых
значений предметных переменных предиката,
получим n-арное отношение на множестве M,
состоящее из всех таких упорядоченных
наборов a1 ,..., an n элементов a1 ,..., an M , для
P a1 ,..., an
которых
является
истинным
высказыванием.
Такое n-арное отношение обозначается
+
символом P и называется множеством
истинности предиката P на множестве M.

8.

Определение. Предикат P x1 ,..., xn на множестве
M называется:
тождественно истинным, если для любых
x1 a1 M ,..., xn an M
значений
высказывание P a1 ,..., an истинно, т.е. P+=Mn;
тождественно ложным, если для любых
значений x1 a1 M ,..., xn an M высказывание
P a1 ,..., an ложно, т.е. P+ = ;
выполнимым, если для некоторых значений
x1 a1 M ,..., xn an M
высказывание
P a1 ,..., an истинно, т.е. P+ ;
опровержимым, если для некоторых значений
x1 a1 M ,..., xn an M
высказывание
P a1 ,..., an ложно, т.е. P+ Mn.

9.

Определение. Пусть предикаты одинаковой
арности P x1 ,..., xn и Q x1 ,..., xn рассматриваются
на множестве M. Тогда:
предикаты P и Q называются эквивалентными,
если P+ = Q+, т.е. при любых значениях
x1 a1 M ,..., xn an M высказывание P a1 ,..., an
истинно в том и только том случае, если
истинно высказывание Q a1 ,..., an ;
предикат Q называется следствием предиката
P , если P+ Q+, т.е. при любых значениях
x1 a1 M ,..., xn an M
из
истинности
высказывания P a1 ,..., an следует истинность
высказывания Q a1 ,..., an .

10. Алгебра предикатов

11.

Определение.
Результатом действия квантора общности
x1 по переменной x1 на n-местный предикат
P x1 ,..., xn называется (n 1)-местный предикат
x1 P( x1 , x2 ,..., xn ) , который зависит от
переменных x2 ,..., xn и который при значениях
x2 a2 ,..., xn an в том и только том случае
истинен на множестве M допустимых
значений переменной x1, если при любых
x1 a1 M
значениях
высказывание
P a1 , a2 ,..., an истинно.

12.

Определение.
Результатом
действия
квантора
существования x1 по переменной x1 на nместный предикат P x1 ,..., xn называется
(n 1)-местный предикат x1 P( x1 , x2 ,..., xn ) ,
который зависит от переменных x2 ,..., xn и
который при значениях x2 a2 ,..., xn an в том и
только том случае истинен на множестве M
допустимых значений переменной x1, если
x1 a1 M
при
некотором
значении
высказывание P a1 , a2 ,..., an истинно.

13.

Квантор существования и единственности
! x определяется как сокращение записи
следующей формулы
x ( P( x) y ( P( y) x y) ) .
Результат действия такого квантора на
предикат P(x) обозначается ! x P( x) и
читается «существует и единственен x, для
которого выполняется P(x) »).

14.

Ограниченный квантор существования
Q(x) определяется как сокращение записи
следующей формулы
x (Q( x) P( x)) .
Результат действия такого квантора на
предикат P(x) обозначается Q( x) P( x) и и
читается «существует x, удовлетворяющий
Q(x) , для которого выполняется P(x) ».

15.

Ограниченный квантор общности Q(x)
определяется как сокращение записи
следующей формулы
x (Q( x) P( x)) .
Результат действия такого квантора на
предикат P(x) обозначается Q( x) P( x) и
читается «для всех x, удовлетворяющих Q(x) ,
выполняется P(x) ».