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

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

2.

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

3.

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

4.

Функция
определяется двумя
множествами:
–
множество истинности,
–
множество ложности.

5.

Определение. Предикат 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.

6.

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

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

8.

Определение.
Результатом действия квантора общности
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 истинно.

9.

Определение.
Результатом
действия
квантора
существования 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 истинно.

10.

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

11.

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

12.

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

13.

Определение.
Алгеброй предикатов называется множество
всех предикатов P с логическими операциями
, , , ,
и операциями квантификации
x , x для всех предметных переменных x.

14. Формулы алгебры предикатов

15.

Свойства алгебры предикатов P описываются
с помощью специальных формул, которые
строятся из символов предикатов и предметных
переменных
с
помощью
специальных
вспомогательных символов – скобок и знаков
логических операций над предикатами.

16.

Алфавит алгебры предикатов состоит из
следующих символов:
x1 , x2 ,...,
1) предметные
переменные
которые используются для обозначения
элементов множества допустимых значений,
2) n-местные предикатные символы P,Q,...,
которые используются для обозначения nместных
предикатов
на
множестве
допустимых значений,
3) символы логических операций
, , , , , , ,
4) вспомогательные символы (,) и другие.

17.

Формулы алгебры предикатов определяются по
индукции следующим образом:
1) для любого n-местного предикатного символа P и
любых n предметных переменных x1 ,..., xn
выражение P x1 ,..., xn есть формула, которая
называется элементарной (или атомарной)
формулой;
2) если , – формулы, то формулами являются
также выражения
( ) , , , , ;
3) если – формула и x – предметная переменная,
то формулами являются также выражения x ,
x ; при этом переменная x и формула
называется областью действия соответствующего
квантора.

18.

Если в формулу входят переменные x1 ,..., xn ,
то записывают ( x1 ,..., xn ) .
Вхождение предметной переменной x в
формулу называется связным, если она
находится в области действия одного из этих
кванторов; в противном случае вхождение
предметной переменной x в формулу
называется свободным.
Формула
без
свободных
вхождений
переменных называется замкнутой формулой
или предложением.