§6. Равносильные формулы логики предикатов.
Определение 1.
Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.
Определение 2.
Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области.
Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.
Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности:
1.
2.
3.
4.
5.
.
Равносильность 1
означает тот простой факт, что, если не
для всех х истинно А(х), то существует
х, при котором будет истиной
.
Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х), то для всех х будет истиной .
Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.
ЗАКОНЫ ЛОГИЧЕСКИХ ОПЕРАЦИЙ.
(общезначимые формулы логики предикатов)
|
|
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
§7. Нормальные формы формул логики предикатов.
В логике предикатов, как и в логике высказываний, формулы могут иметь нормальную форму, т.е. существуют эквивалентные нормальные формы представления любых предикатных формул. При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме. В логике предикатов различают два вида нормальных форм: приведенную и предваренную.
Определение.
Говорят, что формула логики предикатов имеет приведенную нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.
Пример 1.
.
Получили приведенную нормальную форму исходной формулы.
Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, пренексную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, т.е. ПНФ формулы логике предикатов имеет вид
,
где под символом
понимается один из кванторов
или
,
а формула А кванторов не содержит.
Процедура получения (приведения) ПНФ. Состоит в следующем:
Используя формулы 18, 19 (отнесенные к предикатам), заменить операции
и
~ на
.Используя формулы логики предикатов 31, 32, а также формулы логики высказываний 1, 16, 17, представить предикатную формулу таким образом, чтобы символы отрицания относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме).
Для формул, содержащих подформулы вида
,
вести новые переменные, позволяющие
использовать соотношения 46, 47, 49, 50 или
53, 54.С помощью формул 35 – 38, 46, 47, 49, 50, 53, 54 получить формулу в виде ПНФ.
Пример 2.
обозначим в
предикате Q переменную y через z
Пример 3.
обозначим в
предикате Q переменную x через z
–
ПНФ.
Пример 4.
последний
предикат не зависит от переменной z
два первых предиката
не зависят от переменной u
- ПНФ.
Пример 5.
