Лекция 5_2025.ppsx

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

2.

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

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

4.

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

5.

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

6.

7.

,
|
4) если
для формул
тогда
1
2, то M
1
2
|
|
и только тогда, когда M
;
1или M
2
,
|
5) если
для формул
1
2
1
2, то M
|
тогда и только тогда, когда неверно, что M
1и
M
|
;
2
,
|
6) если
для формул
1
2
1
2, то M
|
|
тогда и только тогда, когда M
, M
1
2
одновременно верны или нет;
|
7) если x
для некоторой формулы , то M
|
тогда и только тогда, когда M
для всех оценок
, отличающихся от оценки возможно только на
элементе x;
|
8) если x
для некоторой формулы , то M
|
тогда и только тогда, когда M
для некоторой
оценки , отличающейся от оценки возможно
только на элементе x.

8.

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

10.

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

11.

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

12.

13.

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

14.

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

15.

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

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

17.

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

18.

С другой стороны, в алгебре предикатов можно
получить много принципиально новых тавтологий с
помощью следующих свойств кванторов.
, следующие
Лемма 2. Для любых формул
формулы являются тавтологиями:
x
x
x
x
1.
,
,
x
x
x
x
,
;
x
y
y
x
x
y
y
x
2.
,
;
(
x
)
x
x
3.
,
(
x
)
x
x
;

19.

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