766.64K
Категория: МатематикаМатематика

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

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.
Такие отображения называются оценками
предметных переменных.
English     Русский Правила