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

1.

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

2.

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

3.

Выразительные
средства
алгебры
высказываний недостаточны для описания
утверждений
со
структурой
сложной
логической
субъектно-предикатных
рассуждений, в которых используются не
только понятие субъекта (как объекта, о
которых говорится в рассуждении), но и
понятие
предиката
(как
выраженного
сказуемыми свойства объектов рассуждения).

4.

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

5.

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

6.

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

7.

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

8.

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

9.

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

10.

Примеры.
1. Пусть M – множество студентов вуза.
Предикаты:
P(x)
– « x есть студент 1-ой группы»,
Q(x)
– « студент x есть отличник».
+
Множеством истинности P на множестве M
является множество студентов 1-ой группы
вуза и множеством истинности Q+ на
множестве M является множество всех
отличников вуза.

11.

2. Пусть M – множество вещественных чисел
R.
Предикаты:
P(x) – утверждение «
»,
Q(x) – утверждение «
».
Множеством истинности предиката P на множестве
является
множество
всех
положительных
вещественных чисел и множеством истинности предиката
на
Q
множестве
.
.
является
множество

12.

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

13.

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

14.

Отрицание
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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

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

24.

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

25.

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

26.

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

27.

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

28.

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

29.

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

30.

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

31.

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