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

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

2.

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

3.

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

4.

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

5.

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

6.

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

7.

Пример.
Пусть M – множество студентов вуза и P(x) –
одноместный предикат « x есть студент 1-ой
группы». Тогда результатом действия квантора
общности x по переменной x на предикат P x
является высказывание x P(x) – «любой x является
студентом 1-ой группы», которое очевидно ложно
на множестве M. Результатом действия квантора
существования x по переменной x на предикат
P x является высказывание x P (x) – «некоторый
x является студентом 1-ой группы», которое
очевидно истинно на множестве M.

8.

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

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

10.

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

11.

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

12.

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

13.

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

14. Интерпретации формул алгебры предикатов

15.

Область интерпретации – непустое множество
M, которое является областью возможных
значений всех предметных переменных.
P
n-местным
предикатным
символам
присваиваются конкретные значения PM nместных предикатов на множестве M.
P PM
Соответствие
:
называется
интерпретацией предикатных символов.
Область
интерпретации
M
вместе
с
интерпретацией
предикатных
символов
называется интерпретацией формул алгебры
предикатов и обозначается (M , ) или просто M.

16.

При наличии интерпретации M конкретные
значения предметным переменным формул
алгебры
предикатов
присваиваются
с
помощью отображения множества всех
предметных переменных X в область
интерпретации M.
Такие отображения называются оценками
предметных переменных.

17.

Выполнимость формулы в интерпретации M
M |
при оценке
обозначается
и
определяется следующим образом:
1) если P x1 ,..., xn для n-местного предикатного
символа P и предметных переменных x1 ,..., xn ,
то M | тогда и только тогда, когда
высказывание PM ( x1 ),..., ( xn ) истинно;
2) если для формулы , то M | тогда
и только тогда, когда неверно, что M | ;
3) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда M | 1 и M | 2 ;

18.

4) если 1 2 для формул 1 , 2 , то M | тогда
и только тогда, когда M | 1 или M | 2 ;
5) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда неверно, что M | 1 и
M | 2 ;
6) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда M | 1 , M | 2
одновременно верны или нет;
7) если x для некоторой формулы , то M |
тогда и только тогда, когда M | для всех оценок
, отличающихся от оценки возможно только на
элементе x;
8) если x для некоторой формулы , то M |
тогда и только тогда, когда M | для некоторой
оценки , отличающейся от оценки возможно
только на элементе x.

19.

Определение. В интерпретации M формула
называется:
общезначимой
(или
тождественно
истинной), если M | при любых оценках
;
выполнимой, если M | для некоторой
оценки ;
опровержимой, если для некоторой оценки
неверно, что M | ;
тождественно ложной, если для любой
оценки неверно, что M | .

20.

Формула общезначима в интерпретации M, если
при подстановке в нее вместо n-арных предикатных
символов P их интерпретаций PM она превращается
в тождественно истинный на множестве M
предикат. Символическая запись M | .
Формула в интерпретации M выполнима,
опровержима или тождественно ложна, если при
подстановке в нее вместо n-арных предикатных
символов P их интерпретаций она превращается
соответственно в выполнимый, опровержимый или
тождественно ложный на множестве M предикат
PM .

21. Проблема общезначимости формул алгебры предикатов

22.

Определение. Формула называется тождественно
истинной, если она тождественно истина в любой
интерпретации M. Такая формула называется также
общезначимой формулой, или тавтологией алгебры
предикатов и обозначается | . Множество всех
тавтологий алгебры предикатов обозначим TАП. .
Определение. Формула называется тождественно
ложной или противоречием, если она тождественно
ложна в любой интерпретации M.
По определению противоречивость формулы
равносильна условию | .
Определение. Формула называется выполнимой, если
она выполнима хотя бы в одной интерпретации M,
которая называется моделью этой формулы.

23.

Таким образом, формула :
общезначимая (или тождественно истинная,
M |
тавтология),
если
в
любой
интерпретации M при любых оценках ;
запись | ;
выполнимая, если M | в некоторой
интерпретации M для некоторой оценки ;
опровержимая, если в некоторой
интерпретации M для некоторой оценки
неверно, что M | ;
тождественно ложная, если в любой
интерпретации M для любой оценки
неверно, что M | .

24.

Замечание 1.
Если формула является предложением, то она
не содержит свободных вхождений переменных
и, следовательно, не зависит от оценок
предметных
переменных
в
области
интерпретации M.
Значит, предложение в интерпретации M
общезначимо в том и только том случае, если оно
выполнимо (т.е. выполняется хотя бы при одной
оценке предметных переменных в области
интерпретации M).

25.

Замечание 2.
Для
формулы
справедливы
следующие утверждения:
1) |=
равносильно
|=
;
2)
выполнима в том и только
том случае, если выполнима формула
;
3)
выполнима
в
любой
интерпретации в том и только том случае,
если |=
.

26. Тавтологии алгебры предикатов

27.

Любая тавтология алгебры высказываний
является тавтологией алгебры предикатов.
Более того, тавтологии алгебры высказываний
дают возможность легко получать тавтологии
алгебры предикатов с помощью следующего
очевидного результата.
Лемма 1. Если X 1 ,..., X n – тавтология
алгебры высказываний, то для любых формул
алгебры предикатов 1 ,..., n формула 1 ,..., n
является тавтологией алгебры предикатов.

28.

С другой стороны, в алгебре предикатов можно
получить много принципиально новых тавтологий с
помощью следующих свойств кванторов.
Лемма 2. Для любых формул , следующие
формулы являются тавтологиями:
1. x x , x x ,
x x , x x ;
2. x y y x , x y y x ;
3. x ( ) x x ,
x ( ) x x ;

29.

4. x ( ) x , где – символ одной
из операций , ;
5. x ( ) x , где – символ одной из
операций , ,
если в формулу предметная переменная x не
входит свободно; а также
6. x ( ) ( x ) ,
x ( ) ( x ) ,
7. x ( ) ( x ) ,
x ( ) ( x ) .

30.

8.
x ( x) ( y) ,
( y ) x ( x) ,
если формула (x) не содержит предметную
переменную y и формула ( y) получается из
(x) заменой всех свободных вхождений
переменной x на предметную переменную y.