Функциональный анализ языка . . Функциональный анализ языка (стр. 8 )

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

ℑφ|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) ≡ (∃αА ⊃ В), если α не свободна в В,

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

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

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

(∃αА ⊃ ∀αB) ⊃ ∀α(A ⊃ В).

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

∀α∀βA ≡ ∀β∀αA,

∃α∃βA ≡ ∃β∃αA,

∃α∀βA ⊃ ∀β∃αA.

6. Законы отрицания кванторов:

¬∃αA ≡ ∀α¬A,

¬∀αA ≡ ∃α¬A.

7. Законы взаимовыразимости кванторов:

∀αA ≡ ¬∃α¬A,        

∃αА ≡ ¬∀α¬A.

Понятие модели

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

Формула А называется истинной в возможной реализации ℑ =
<U, I>, если она принимает значение «истина» в этой реализации при любом приписывании φ значений индивидным переменным, т. е.

φ|А|φℑ = и.

Возможная реализация ℑ называется моделью формулы А, если А является истинной в этой возможной реализации.

Возможная реализация ℑ называется моделью множества формул Г, если ℑ является моделью для каждой формулы А ∈ Г.

Отношения между формулами логики предикатов

Зададим в классической логике предикатов фундаментальные логические отношения – отношения совместимости по истинности, совместимости по ложности и логического следования. Пусть Г – произвольное непустое множество формул языка логики предикатов.

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

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

Из множества формул Г логически следует формула В (Г ⊨ В), если и только если не существует такой реализации ℑ и приписывания значений предметным переменным φ, при которых каждая формула из Г принимает значение «истина», а формула В – значение «ложь».

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

Выберем в качестве U множество городов. Пусть I сопоставляет двухместной предикаторной константе Q множество таких пар городов, первый из которых севернее второго. Пусть φ приписывает переменной у, свободной в указанных формулах, город Москву, а остальным переменным – произвольные города. Рассмотрим теперь приписывания ψ и ξ, отличающиеся от φ не более, чем значением х. Пусть функция ψ переменной у так же, как и φ, сопоставляет Москву, а х – Мурманск. Поскольку Мурманск севернее Москвы, пара <Мурманск, Москва> содержится в I(Q) и, значит, |Q(x, y)|ψ = и. Отсюда, согласно (F7), следует, что |∃xQ(x, у)|φ = и. Пусть функция ξ переменной у снова сопоставляет Москву, а х – Астрахань. Поскольку Астрахань не находится севернее Москвы, пара
<Астрахань, Москва> не содержится в I(Q), и |Q(x, у)|ξ = л. Тогда, согласно (F2), |¬Q(x, у)|ξ = и, откуда по (F7) получаем: |∃x¬Q(x, у)|φ = и. Таким образом, формулы ∃xQ(x, у) и ∃x¬Q(x, у) в рассмотренной нами реализации ℑ = <U, I> при приписывании φ одновременно принимают значение «истина».