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

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

2.

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

3.

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

4.

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

5.

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.

6. Классификация формул алгебры предикатов

7.

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

8.

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

9.

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

10.

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

11.

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

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

13.

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

14.

С другой стороны, в алгебре предикатов можно
получить много принципиально новых тавтологий с
помощью следующих свойств кванторов.
Лемма 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 ;

15.

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

16. Логическая равносильность формул алгебры предикатов

17.

Определение. Формулы алгебры предикатов
, называется логически равносильными, если
результат применения к ним логической
операции эквивалентность является
тавтологией.
В этом случае записывают , или просто
.
Таким образом, означает, что | .

18.

Теорема 1 (Взаимосвязь между кванторами).
Для любой формулы справедливо равенство:
x y y x , x y y x .
С другой стороны, если в формулу
предметные переменные x,y входят свободно,
то равенство
y x x y
не выполняется, так как в этом случае формула
y x x y
не является тавтологией.

19.

Теорема 2. Пусть формула (x) не содержит
предметную переменную y и формула ( y )
получается из (x) заменой всех свободных
вхождений переменной x на предметную
переменную y.
Тогда формулы x (x) и x (x) будут
логически
равносильны
соответственно
формулам y ( y) и y ( y) , т.е. выполняются
равенства:
x ( x) y ( y) и x ( x) y ( y) .

20.

Теорема 3 (Законы де Моргана для кванторов). Для
любой
формулы
справедливы
следующие
утверждения:
x x , x x ,
x x , x x .
Теорема 4 (Взаимосвязь кванторов с конъюнкцией и
дизъюнкцией). Для любых формул , справедливы
следующие утверждения:
x ( ) x x ,
x ( ) x x .
Если в формулу предметная переменная x не входит
свободно, то справедливы также утверждения:
x x , x x , где
– символ одной из операций , .

21.

Теорема
6
(Взаимосвязь
кванторов
с
импликацией). Если в формулу предметная
переменная x не входит свободно, то для любой
формулы справедливы следующие утверждения:
x ( ) x , x ( ) x .
Если же предметная переменная x не входит
свободно в формулу , то для любой формулы
справедливы утверждения:
x ( ) x , x ( ) x .

22.

Следствие
7.
Любая
формула
представляется в следующем виде:
K1 x1 ... K n xn ,
где K1 ,..., K n – некоторые кванторы и –
формула без кванторов.
Таким образом, каждая формула логически
равносильна формуле K1 x1 ... K n xn , в которой
все кванторы стоят в самом начале формулы и
которая называется предваренной нормальной
формой (сокращенно ПНФ) формулы .

23.

Алгоритм приведения формулы к ПНФ:
1) преобразуем формулу в эквивалентную ей
формулу , которая не содержит импликации и
эквивалентности и в которой отрицание
действует только на элементарные формулы;
2) в все кванторы последовательно выносим
вперед по теореме 5, при этом кванторы
общности x выносятся из конъюнкции и
кванторы существования x выносятся из
дизъюнкции, а для выноса кванторов общности
x из дизъюнкции и кванторов существования
x из конъюнкции переименовываем связанные
переменные x в новые переменные y, которые не
входят в рассматриваемую формулу.