Similar presentations:
Формулы алгебры предикатов (лекция 5)
1.
Формулы алгебрыпредикатов
2.
Определение.Алгеброй предикатов называется множество
всех предикатов P с логическими операциями
, , , ,
и операциями квантификации
x , x для всех предметных переменных x.
3.
4.
Алфавит алгебры предикатов состоит изследующих символов:
x1 , x2 ,...,
1) предметные
переменные
которые используются для обозначения
элементов множества допустимых значений,
2) n-местные предикатные символы P,Q,...,
которые используются для обозначения nместных
предикатов
на
множестве
допустимых значений,
3) символы логических операций
, , , , , , ,
4) вспомогательные символы (,) и другие.
5.
Формулы алгебры предикатов определяются поиндукции следующим образом:
1) для любого n-местного предикатного символа P и
любых n предметных переменных x1 ,..., xn
выражение P x1 ,..., xn есть формула, которая
называется элементарной (или атомарной)
формулой;
2) если , – формулы, то формулами являются
также выражения
( ) , , , , ;
3) если – формула и x – предметная переменная,
то формулами являются также выражения x ,
x ; при этом переменная x и формула
называется областью действия соответствующего
квантора.
6.
Если в формулу F входят переменные x1 ,..., xn ,то записывают F = F ( x1 ,..., xn ) .
Вхождение предметной переменной x в
формулу F называется связным, если она
находится в области действия одного из
кванторов по этой переменной; в противном
случае вхождение предметной переменной x в
формулу F называется свободным.
Формула
без
свободных
вхождений
переменных называется замкнутой формулой
или предлож ением.
Фактически формула определяет предикат с
переменными, которые входят в формулу
свободно.
7.
Интерпретации формулалгебры предикатов
8.
Область интерпретации – непустое множествоM, которое является областью возможных
значений всех предметных переменных.
P
n-местным
предикатным
символам
присваиваются конкретные значения PM nместных предикатов на множестве M.
P PM
Соответствие
:
называется
интерпретацией предикатных символов.
Область
интерпретации
M
вместе
с
интерпретацией
предикатных
символов
называется интерпретацией формул алгебры
предикатов и обозначается (M , ) или просто M.
9.
При наличии интерпретации M конкретныезначения предметным переменным формул
алгебры
предикатов
присваиваются
с
помощью отображения множества всех
предметных переменных X в область
интерпретации M.
Такие отображения называются оценками
предметных переменных.
10.
Выполнимость формулы F в интерпретации Mпри оценке a обозначается M |=a F - читается
«формула F истинна в интерпретации M при
оценке a » и определяется следующим образом:
1) если F = P (x1 ,..., xn ) для n-местного предикатного
символа P и предметных переменных x1 ,..., xn ,
то M |=a F тогда и только тогда, когда
высказывание PM (a ( x1 ),...,a ( xn ) ) истинно;
2) если F = ¬Y для формулы Y, то M |=a F тогда
и только тогда, когда неверно, что M |=a Y ;
3) если F = F1 Ù F 2 для формул F1 , F 2 , то M |=a F
тогда и только тогда, когда M |=a F1 и M |=a F 2 ;
11.
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.
12.
13.
Классификация формулалгебры предикатов
14.
Определение. В интерпретации M формуланазывается:
общезначимой
(или
тождественно
истинной), если M | при любых оценках
;
выполнимой, если M | для некоторой
оценки ;
опровержимой, если для некоторой оценки
неверно, что M | ;
тождественно ложной, если для любой
оценки неверно, что M | .
15.
Формула общезначима в интерпретации M (синтерпретаций PM n-арных предикатных символов
P ), если она превращается в тождественно
истинный
на
множестве
M
предикат.
Символическая запись M | .
Формула в интерпретации M выполнима,
опровержима или тождественно ложна, если она
превращается соответственно в выполнимый,
опровержимый или
тождественно ложный на
множестве M предикат PM .
16.
17.
Определение. Формула называется тождественноистинной, если она тождественно истина в любой
интерпретации M. Такая формула называется также
общезначимой формулой, или тавтологией алгебры
предикатов и обозначается | . Множество всех
тавтологий алгебры предикатов обозначим TАП. .
Определение. Формула называется тождественно
ложной или противоречием, если она тождественно
ложна в любой интерпретации M.
По определению противоречивость формулы
равносильна условию | .
Определение. Формула называется выполнимой, если
она выполнима хотя бы в одной интерпретации M,
которая называется моделью этой формулы.
18.
Таким образом, формула :общезначимая (или тождественно истинная,
M |
тавтология),
если
в
любой
интерпретации M при любых оценках ;
запись | ;
выполнимая, если M | в некоторой
интерпретации M для некоторой оценки ;
опровержимая, если в некоторой
интерпретации M для некоторой оценки
неверно, что M | ;
тождественно ложная, если в любой
интерпретации M для любой оценки
неверно, что M | .
19.
Замечание 1.Если формула является предложением, то она
не содержит свободных вхождений переменных
и, следовательно, не зависит от оценок
предметных
переменных
в
области
интерпретации M.
Значит, предложение в интерпретации M
общезначимо в том и только том случае, если оно
выполнимо (т.е. выполняется хотя бы при одной
оценке предметных переменных в области
интерпретации M).
20.
Тавтологии алгебрыпредикатов
21.
Любая тавтология алгебры высказыванийявляется тавтологией алгебры предикатов.
Более того, тавтологии алгебры высказываний
дают возможность легко получать тавтологии
алгебры предикатов с помощью следующего
очевидного результата.
Лемма 1. Если X 1 ,..., X n – тавтология
алгебры высказываний, то для любых формул
алгебры предикатов 1 ,..., n формула 1 ,..., n
является тавтологией алгебры предикатов.
22.
С другой стороны, в алгебре предикатов можнополучить много принципиально новых тавтологий с
помощью следующих свойств кванторов.
Лемма 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 ;
23.
4. x ( ) x , где – символ однойиз операций , ;
5. x ( ) x , где – символ одной из
операций , ,
если в формулу предметная переменная x не
входит свободно; а также
6. x ( ) ( x ) ,
x ( ) ( x ) ,
7. x ( ) ( x ) ,
x ( ) ( x ) .