Главная | Обратная связь | Поможем написать вашу работу!

Общезначимые эквивалентности логики предикатов

Логика предикатов изучает свойства операций над предикатами и формул, образованных с помощью этих операций. При этом имеются в виду только такие свойства, которые не зависят от природы элементарных предикатов, входящих в формулы. Поэтому символы элементарных предикатов, входящих в формулы, могут обозначать любые предикаты от соответствующих переменных. Говорят, что символы предикатов, входящих в формулы, являются предикатными переменными в отличие от предметных переменных, от которых эти предикаты зависят. Например, формула содержит один двуместный предикатный символ. При замещении его конкретным предикатом , определенным на множестве действительных чисел R, получаем истинное предложение: Для всякого действительного числа х существует большее его действительное число у. При замещении Р предикатом (x>y), определенным также на R, получим истинное предложение: Д ля всякого действительного числа х существует меньшее его действительное число у.

Главным рабочим инструментом в логике предикатов является понятие эквивалентности формул, которое определяется следующим образом. Формулы А и В эквивалентны, если

· множества их свободных переменных совпадают;

· при любом замещении входящих в формулы А и В предикатных символов постоянными предикатами эти формулы переходят либо в один и тот же предикат, либо в предложения, имеющие одинаковые таблицы истинности. Разумеется, все вхождения одноименных предикатных символов в А и В должны заменяться одним и тем же предикатом.

Формулы А и В называются равносильными, если их истинностные таблицы совпадают во всех моделях, обозначается А~В. Отношение равносильности есть эквивалентность. Оно разбивает множество формул логики предикатов на классы равносильных формул. Все равносильности языка логики высказываний справедливы также для логики предикатов. Но в логике предикатов появляются новые равносильности, содержащие кванторы. Пусть х, у - переменные, не обязательно разные, А(х,у), В(х), С(х) - формулы, Е - формула, не содержащая свободных вхождений переменной х. Тогда справедливы общезначимые эквивалентности логики предикатов.

Общезначимые эквивалентности:

1. Замена связанной переменной:

╞ "xB(x) «"yB(y);

╞ $xB(x) «$ yB(y).

2. Перестановка одноименных кванторов:

╞ " x " y A(x,y) «" y " x A(x,y);

╞ $ x $ yA(x,y) «$ y $ x A(x,y).

3. Пронесение отрицания через кванторы:

╞ Ø " xC(x) «$ x(ØC(x));

╞ Ø$ xC(x) «" x(ØC(x)).

4. Введение отрицания в формулу:

╞ " xC(x) «Ø ( $ x(ØC(x)));

╞ $ xC(x) «Ø ( " x(ØC(x))).

5. Дистрибутивность квантора общности относительно конъюнкции:

╞ " xB(x) & " xC(x) «" x(B(x)&C(x)),

╞ E & " xC(x) «" x(E&C(x)).

6. Дистрибутивность квантора существования относительно дизъюнкции:

╞ $ xB(x) Ú$ xB(x) « $ x(B(x) Ú C(x)),

╞ (E Ú $ xC(x)) «$ x(E Ú B(x)).

7. Дистрибутивность квантора существования относительно конъюнкции:

╞ E & $ xC(x) «$ x(E & C(x)).

8. Дистрибутивность квантора общности относительно дизъюнкции:

╞ E Ú" xC(x) «" x(E Ú C(x)).

Общезначимые импликации логики предикатов

1. Правило пронесения квантора существования через конъюнкцию:

╞ ( $ х (А(х) & В(х)) ®$ хА(х) & $ хВ(х)).

2. Правило пронесения квантора общности через дизъюнкцию

╞ ( " хА(х) Ú " хВ(х) ® "х (А(х) Ú В(х))).

3. Смена квантора:

╞ ( " х В(х) ®$ х В(х));

4. Перестановка разноименных кванторов:

╞ ( $ х " у А(х,у) ®" у$х А(х,у)).

Приведем пример доказательства общезначимой импликации 4.

Доказательство от противного.

Пусть неверно, что ╞ ( $ х " у А(х,у) ® " у $ х А(х,у)). Это возможно, если найдется такая модель, в которой формула $ х " у А(х,у) будет истинна, а формула " у $ х А(х,у) - ложна. Пусть в предметной области найдется такое значение х=х₀, что I[" у А(х₀,у) ]=1, т.е. " у I[ А(х₀,у) ]=1.

Из предположения о ложности заключения импликации получаем: в предметной области найдется такое значение у=у₀, при котором I[$ хА(х,у₀) ] =0, т.е. " х I[ А(х,у₀) ] =0. Следовательно, I[ A(x₀,y₀) ]=0. В то же время из предположения об истинности посылки импликации имеем I[ A(x₀,y₀) ]=1.

Получение противоречия означает, что предположение о ложности рассматриваемой импликации неверно. Следовательно, общезначимость импликации 4 доказана.

⇐ Предыдущая 9 10 11 12 131415 16 17 18 Следующая ⇒