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

Формула ЛП может быть истинна во многих интерпретациях, но поскольку число универсумов интерпретации потенциально бесконечно, то никто не может гарантировать, что не найдется хотя бы один, в котором данная формула окажется ложной. Учитывая это обстоятельство, в ЛП отношение логического следования принято определять следующим образом. Пусть а и Д как и прежде, обозначают соответственно множества формул, образующих посылки и заключение доказательства в ЛП.

Если а и р не содержат свободных вхождений предметных переменных, тогда

заключение

рлогически следует из посылок а, если и только если невозможна (противоречива) интерпретация, в которой «истинно, а заключение рложно.

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

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

Теорема 1. ь -*(х)фх = (Ех)-лфх.

Доказательство. Допустим, истинно -«(.г)фх. Тогда существует интерпретация, при которой хотя бы один элемент универсума не обладает свойством ф. Пусть константа а будет именем этого элемента. Тогда истинно -1 фа и тем самым истинно (Ех) —1фх. Обратное утверждение доказывается аналогичным образом. Следовательно, отрицание квантора всеобщности равносильно введению квантора существования с одновременным отрицанием всей области его действия, QED.

Теорема 2. н (д)фх а —i (Er)-i0.r.

Доказательство. Допустим, имеется интерпретация, при которой истинно (х)фх и (Ех)-*фх. Из истинности (л)0tv следует, что все элементы универсума обладают свойством ф. Из истинности (Ех)-, фх следует, что хотя бы один элемент универсума не обладает свойством ф. Получаем противоречие, из которого следует, что такой интерпретации не существует. Следовательно, -(Ех)-*фх — необходимое следствие (х)фх. Обратное утверждение доказывается аналогично, QED.

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

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

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

Рис. 7.1. Квадрат отношений между кванторами.

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

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

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

• 1. Если терм t — предметная константа, то подстановка проводится без ограничений.
• 2. Если терм t — предметная переменная, то ни одно вхождение t не должно оказаться связанным в результате его подстановки на место переменной х в формуле фх.

Подстановка (Ех)Рху (у/г) = (Ex)Pxz правильная, так как вхождение переменной 2 не связанно в формуле (Ех)Рху. Подстановка (Ех)Рху (у/ х) — (Кх)Рхх неправильная, потому что терм х, подставленный вместо у, оказался связанным квантором (х). Неправильные подстановки приводят к противоречию. Пусть Рху обозначает отношение «л; больше у». Пусть U = «натуральные числа». Тогда формула (Ех)Рхх, полученная в результате неправильной подстановки, означает, что «существует такое натуральное число, которое больше самого себя», что очевидно ложно.

Теорема 3. (х)фх г ф (а/х).

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

Теорема 4. ф (а/лг) н (Ех)фх.

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