Лекция 11_2гр

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

2.

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

3.

На области возможных значений M истинностная
функция предиката
определяется множеством:
–
множество истинности.

4.

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

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

6.

Отрицание
n-местного
предиката
P x1 ,..., xn
определяется как n-местный предикат P , который при
подстановке значений x1 a1 ,..., xn an превращается в
высказывание P a ,..., a , являющееся отрицанием
высказывания P a1 ,...,an .
1
n
Конъюнкция n-местных предикатов P x1 ,..., xn и Q x1 ,..., xn
определяется как n-местный предикат P Q , который
при подстановке значений x1 a1 ,..., xn an превращается в
высказывание P Q a ,..., a , являющееся конъюнкцией
высказываний P a1 ,...,an и Q a1 ,..., an .
1
n

7.

Для любого множества M допустимых
значений предметных переменных предикатов
множества
истинности
предикатов
взаимосвязаны с логическими операциями по
следующим формулам:
P M n \ P , P Q P Q , P Q P Q ,
P Q ( P) Q , P Q ( P Q) (Q P) .

8.

Примеры.
1. Пусть на множестве вещественных чисел
R предикат P x выражается неравенством
f x 0
Q x
и предикат
выражается
g x 0 .
неравенством
Тогда
система
неравенств fg((xx)) 00, определяется как
конъюнкция предикатов P Q и, значит,
имеет множество решений P Q P Q ,
равное пересечению множеств решений
неравенств системы.

9.

2. Пусть на множестве вещественных чисел R
предикат P x выражается неравенством f x 0 и
предикат Q x выражается неравенством g x 0 .
f ( x) 0,
Тогда
совокупность
неравенств
g ( x) 0
определяется как дизъюнкция предикатов P Q
и, значит, имеет множество решений
P Q P Q , равное объединению множеств
решений неравенств системы.

10.

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

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.

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

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

14.

15.

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

16.

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

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

18.

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

19.

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

20.

Выполнимость формулы в интерпретации M
при оценке обозначается 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 ;

21.

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.