Интерпретация и логические отношения в логике предикатов (стр. 4 )

Виды формул в классической логике предикатов

Напомним, что законом логической теории является формула, истинная при любых допустимых в этой теории интерпретациях нелогических символов, которые входят в состав данной формулы. В логике предикатов интерпретация нелогических символов осуществляется посредством выбора некоторой возможной реализации ℑ = <U, I> и приписывания значений предметным переменным φ. Поэтому в данной теории понятие логического закона будет конкретизироваться следующим образом:

Формула А является законом классической логики предикатов (общезначимой формулой), если и только если А принимает значение «истина» в каждой возможной реализации ℑ и при каждом приписывании значений предметным переменным φ, т. е.

ℑφ|A|ℑφ = и.

Из данного определения непосредственно вытекает следующая трактовка опровержимой (необщезначимой) формулы:

Формула А опровержима в логике предикатов (не является законом этой логики) тогда и только тогда, когда существует реализация ℑ и существует функция приписывания предметным переменным φ, при которых А принимает значение «ложь». Таким образом:

ℑφ|A|ℑφ = л.

Утверждение «Формула А общезначима» будем записывать так: «⊨ А».

Примером общезначимой формулы является ∀xP(x) ⊃ ∃хР(х). Покажем, что эта формула действительно является законом логики предикатов.

Будем рассуждать от противного. Пусть ∀xP(x) ⊃ ∃хР(х) необщезначимая (опровержимая) формула. Тогда существует реализация ℑ и приписывание φ, при которых |∀xP(x) ⊃ ∃хР(х)|φ = л. Тогда, согласно (F5), |∀xP(x)|φ = и и |∃хР(х)|φ = л. Истинность ∀xP(x), согласно (F6), означает, что P(x) истинно при любом приписывании, отличающемся от φ не более, чем значением x. Ложность ∃хР(х), согласно (F7), означает, что P(x) ложно при любом подобном приписывании. Рассмотрим какое угодно конкретное приписывание ψ указанного типа. Получается, что, с одной стороны, |P(x)|ψ = и, а с другой, |P(x)|ψ = л. Таким образом, мы пришли к противоречию. Следовательно, допущение необщезначимости формулы ∀xP(x) ⊃ ∃хР(х) неверно и она действительно является законом логики предикатов.

Чтобы продемонстрировать опровержимость некоторой формулы, достаточно найти такую реализацию ℑ = <U, I> и приписывание φ, при которых эта формула примет значение л. Покажем, например, что формула ∃хР(х) ⊃ ∀xP(x) является опровержимой.

Выберем в качестве области интерпретации U множество людей. Пусть интерпретирующая функция I сопоставляет предикаторной константе Р множество мужчин. Исходное приписывание φ выбирается произвольным образом. Если переменной х приписать в качестве значения Сократа, то в нашей реализации ℑ = <U, I> формула Р(х) окажется истинной, ведь Сократ является мужчиной, т. е. элементом I(Р). Итак, существует такое приписывание ψ, что |P(x)|ψ = и, откуда следует, что |∃хР(х)|φ = и при произвольном φ. Если же переменной x приписать в качестве значения жену Сократа – Ксантиппу, т. е. выбрать приписывание ξ такое, что ξ(х) = Ксантиппа (а всем другим переменным ξ сопоставляет те же значения, что и ψ), то Р(х) окажется ложной формулой, поскольку Ксантиппа не является мужчиной: |P(x)|ξ = л. Последнее означает, что |∀xP(x)|φ = л. Истинность ∃хР(х) и ложность ∀xP(x) в ℑ при приписывании φ свидетельствует о том, что |∃хР(х) ⊃ ∀xP(x)|φ = л. Данная формула является опровержимой, поскольку мы указали реализацию и приписывание, при которых она ложна.

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

Формула А языка логики предикатов выполнима, если и только если существуют реализация ℑ и приписывание значений предметным переменным φ, при которых А принимает значение «истина», т. е.

ℑφ|A|ℑφ = и.

Покажем, что формула ∃хР(х) ⊃ ∀xP(x), необщезначимость которой была только что установлена, является выполнимой. Для этого достаточно указать конкретную реализацию ℑ = <U, I> и приписывание φ, при которых она истинна.

Пусть U снова является множеством людей, но пусть теперь I сопоставляет Р пустое множество (например, множество людей, побывавших на Солнце), функция φ может быть произвольной, так как рассматриваемая формула не содержит свободных индивидных переменных. Ясно, что ни один человек не является элементом I(Р), ведь у пустого множества нет элементов. Поэтому формула P(x) ложна при приписывании х любого объекта из U, т. е. |P(x)|ψ = л для любого ψ. А из этого, согласно (F7), следует, что |∃хР(х)|φ = л. Но если антецедент импликативной формулы ложен, то, согласно (F5), сама эта формула истинна, т. е. |∃хР(х) ⊃ ∀xP(x)|φ = и. Следовательно, рассматриваемая формула выполнима.

Формула А является невыполнимой тогда и только тогда, когда она принимает значение «ложь» в каждой реализации ℑ и при любом приписывании φ, т. е.

ℑφ|A|ℑφ = л.

В качестве примера покажем, что формула ¬∃хР(х) & Р(а) невыполнима.

Будем рассуждать от противного. Предположим, что эта формула выполнима. Тогда существуют реализация ℑ = <U, I> и приписывание φ, при которых она истинна. Поскольку наша формула является конъюнктивной, ее истинность, согласно (F3), означает, что |¬∃хР(х)|φ = и и |Р(а)|φ = и. Истинность Р(а), согласно (F1), свидетельствует о том, что I(а) ∈ I(Р). А истинность ¬∃хР(х) равносильна, согласно (F2), ложности ∃хР(х). Последнее, согласно (F7), означает, что |P(x)|ψ = л при любом приписывании ψ, которое отличается от φ разве что значением x. В частности |P(x)|ψ = л при таком ψ, которое приписывает x тот же объект, что функция I сопоставляет константе а, т. е. ψ(x) = I(a). Отсюда, в соответствии с (F1), следует, что ψ(x), а значит и I(a) не содержится в I(P), что противоречит ранее полученному утверждению I(а) ∈ I(Р). Поэтому допущение о выполнимости формулы ¬∃хР(х) & Р(а) неверно, и она невыполнима.

Логическая истинность, ложность и недетерминированность

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

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

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

(1) Если всякий храбр, то кто-то храбр.

(2) Если кто-то храбр, то всякий храбр.

(3) Не существует храбрецов, но Ромео храбр.

Сопоставим одноместному предикатору «храбрый» предикаторную константу Р, а имени «Ромео» – предметную константу а.

В этом случае логической формой высказывания (1) будет формула вида ∀xP(x) ⊃ ∃хР(х). Ранее было установлено, что она является общезначимой. Поэтому высказывание (1) логически истинно.

Логической формой высказывания (2) является формула ∃хР(х) ⊃ ∀xP(x). Выше было показано, что эта формула не общезначима, но выполнима. Поэтому высказывание (2) логически недетерминировано.

Наконец, рассматривая высказывание (3), устанавливаем, что оно является логически ложным, поскольку его логическая форма – ¬∃хР(х) & Р(а) – относится к числу невыполнимых формул.

Приведем далее список схем наиболее важных законов логики предикатов первого порядка – схем общезначимых формул.

1. Законы удаления ∀ и введения ∃:

∀αA ⊃ A(t),        A(t) ⊃ ∃αА,

где A(t) – результат подстановки вместо всех свободных вхождений переменной α в формулу А терма t.

2. Закон подчинения:

∀αA ⊃ ∃αА.

3. Закон непустоты предметной области:

∃αА ∨ ∃α¬А.

4. Законы пронесения кванторов:

∀α(A & В) ≡ (∀αA & ∀αB),

∃α(А & В) ⊃ (∃αА & ∃αВ),

∃α(А & В) ≡ (А & ∃αВ), если α не свободна в А,

∃α(A ∨ B) ≡ (∃αA ∨ ∃αВ),

(∀αA ∨ ∀αB) ⊃ ∀α(A ∨ В),

∀α(A ∨ В) ≡ (A ∨ ∀αB), если α не свободна в А,

∀α(A ⊃ В) ⊃ (∀αA ⊃ ∀αB),

∀α(A ⊃ В) ≡ (A ⊃ ∀αB), если α не свободна в А,

∀α(A ⊃ B) ≡ (∃αА ⊃ В), если α не свободна в В,