Отношение логического следования в логике предикатов

Формула ЛП может быть истинна во многих интерпретациях, но пос­кольку число универсумов интерпретации потенциально бесконечно, то никто не может гарантировать, что не найдется хотя бы один, в котором данная формула окажется ложной.

Пусть α и β, как и прежде, обозначают соответственно множества формул, образующих посылки и заключение доказательства в ЛП.

Отношение логического следования в ЛП сохраняет все свойства от­ношения логического следования в ЛВ - рефлексивность, несимметрич­ность и транзитивность. Но при этом обладает определенной специфи­кой, которая связана с введением кванторов.

Если α и β не содержат свободных вхождений пред­метных переменных, тогда заключениеβ логически следует из посылокα, если и только если невозмож­на (противоречива) интерпретация, в которой α ис­тинно, а заключение β ложно

Кванторы общности и существования не являются независимыми. Любой из них может быть определен через противоположный квантор.

Доказательство. Допустим, истинно. Тогда существует ин­

терпретация, при которой по крайней мере один элемент универсума не обладает свойством φ. Пусть константа а является именем этого элемен­та. Тогда истинно - фа и тем самым истинноОбратное утверж­

дение доказывается аналогично. Следовательно, отрицание квантора всеобщности равносильно введению квантора существования с одновре­менным отрицанием всей области его действия. QED.

Доказательство.

по крайней мере один элемент универсума не обладает свойством φ. По­лучаем противоречие, из которого следует, что такой интерпретации не существует. Следовательно,является необходимым следстви­

ем (х) фх. Обратное утверждение доказывается аналогично. QED.

Итак, отрицание любого квантора равносильно замене его на проти­воположный при одновременном отрицании всей области его действия.

Отношения между кванторами соответствуют требованиям логичес­кого квадрата традиционной логики (рис. 7.1).

Формулы, соединенные диагоналями, находятся в отношении проти­воречия (вместе не могут быть ни истинными, ни ложными). Формулы, соединенные вертикальными (левой и правой) линиями, - в отношении подчинения (из истинности универсально квантифицированной формулы следует истинность экзистенциально квантифицированной, из ложности экзистенциально квантифицированной следует ложность универсально

Рис. 7.1. Отношения между кванторами квантифицированной; но обратные следования неверны). Формулы, со­единенные верхней горизонтальной линией, - в отношении противопо­ложности (вместе не могут быть истинными, но могут быть ложными). Формулы, соединенные нижней горизонтальной линией, - в отношении частичной совместимости (вместе не могут быть ложными, но могут быть истинными).

Если некоторая формула содержит вхождения свободных перемен­ных, то на их место могут подставляться термы. Пусть ф (x/t)обозначает операцию подстановки терма tна место свободной переменной xв фор­муле фх.

Чтобы подстановка оказалась правильной, необходимо выполнить следующие условия.

1. Если терм t- предметная константа, то подстановка проводится без ограничений.

2. Если терм t- предметная переменная, то ни одно вхождение tне должно оказаться связанным в результате подстановки tна место пере­менной х в формуле фх.

Подстановка (Ех) Рху (y/z) ? (Ех) Pxzявляется правильной, так как вхождение переменной zне является связанным в формуле (Ех) Рху. Под­становка (Ех) Рху(y/x) ? (Ех) Рхх неправильная, потому что терм x, под­ставленный вместо у, оказался связанным квантором (х). Неправильные подстановки приводят к противоречию. Пусть Рху обозначает отноше­ние «х больше у». Пусть U = «натуральные числа». Тогда формула (Ех) Рхх, полученная в результате неправильной подстановки, означает, что

«существует такое натуральное число, которое больше самого себя», что очевидно ложно.

Доказательство. Допустим, имеется интерпретация, при которой ис­тинно (х) фх и ложна формула фа, где константа а является результатом подстановки вместо переменной х. Тогда истинна формула - фа и тем самым истинна формула (Ех) -φx. Но формула противоречит допущению (х) фх. Откуда следует, что такой интерпретации не существует и универ­сально квантифицированная переменная может заменяться любой пред­метной константой. QED.

Доказательство. Допустим, имеется интерпретация, при которой истинна формула фа, где константа а является результатом подстановки вместо переменной х, и ложна формула (Ех) φx. Но тогда истинна фор­мула - (Ех) фх и тем самым формула (х) -φx. Из истинности фа следует истинность (Ех) φx, что противоречит - (Ех) φx и тем самым формуле (х) - φx. Значит, указанная интерпретация невозможна и из выполнимости формулы ф для произвольной предметной константы следует истинность ее экзистенциальной квантификации. QED.

7.5.