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

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

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

∃α(А ⊃ В) ≡ (∀α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> при приписывании φ одновременно принимают значение «истина».

С использованием тех же самых U, I и φ можно показать совместимость по ложности формул ∀x¬Q(x, у) и ∀xQ(x, у).

Только что было установлено, что |Q(x, y)|ψ = и. Отсюда по (F2) следует: |¬Q(x, y)|ψ = л. Тогда, согласно (F6), |∀x¬Q(x, у)|φ = л. Кроме того, имело место |Q(x, у)|ξ = л. Отсюда вытекает: |∀xQ(x, у)|φ = л. Таким образом, в данной реализации и при данном приписывании φ формулы ∀x¬Q(x, у) и ∀xQ(x, у) одновременно ложны. Следовательно, они совместимы по ложности.

Но ∀x¬Q(x, у) и ∀xQ(x, у) не являются совместимыми по истинности.

Чтобы доказать это, будем рассуждать от противного. Допустим, что они совместимы по истинности. Это означает, что существуют реализация ℑ = <U, I> и приписывание φ, при которых обе формулы принимают значение «истина». С учетом того, что функция φ отличается от самой себя не более, чем значением x, и используя (F6), получаем: |¬Q(x, y)|φ = и и |Q(x, у)|φ = и. Но из того, что |¬Q(x, y)|φ = и, в силу (F2), следует, что |Q(x, у)|φ = л. В рассуждении получено противоречие. Значит, исходные формулы по истинности несовместимы.

С помощью похожего рассуждения несложно доказать несовместимость по ложности формул ∃xQ(x, y) и ∃х¬Q(x, y).

Подведем итог рассмотрению последних примеров. Исходя из них, можно утверждать, что формулы ∀x¬Q(x, у) и ∀xQ(x, у) находятся в отношении противоположности (контрарности), поскольку они совместимы по ложности, но несовместимы по истинности, а формулы ∃xQ(x, y) и ∃х¬Q(x, y) – в отношении подпротивоположности (субконтрарности), так как они, наоборот, совместимы по истинности, но несовместимы по ложности.

Перейдем теперь к рассмотрению примеров установления отношения логического следования в логике предикатов. Покажем, что из формул Р(а) и Q(a) логически следует ∃х(Р(х) & Q(х)).

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

P(a), Q(a) ⊨ ∃x(P(х) & Q(х)).

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

Р(а), Q(а)

∃х(Р(х) & Q(х)).

Правильным, в частности, является такое умозаключение:

Отелло ревнив

Отелло простодушен

Некоторые ревнивые люди простодушны.

Постараемся далее ответить на вопрос, является ли правильным другое умозаключение:

Существуют ревнивые люди.

Существуют простодушные люди.

Некоторые ревнивые люди простодушны.

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

∃хР(х), ∃хQ(х)

∃х(Р(х) & Q(х)).

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

Рассмотрим в качестве универсума U множество животных. Пусть интерпретирующая функция I сопоставляет константе Р множество волков, а константе Q множество зайцев. Поскольку все анализируемые формулы замкнуты, приписывание φ выбирается произвольно. Формула ∃хР(х) истинна в указанной реализации ℑ = <U, I> при φ, так как переменной x можно приписать в качестве значения животное (элемент U), которое является волком. Формула ∃хQ(x) также истинна, поскольку x можно приписать в качестве значения зайца (т. е. элемент I(Q)). Однако, какое бы животное мы ни приписали x, оно не может оказаться одновременно и волком, и зайцем, т. е. |Р(x) & Q(x)|ψ = л при любом ψ. Это свидетельствует о ложности формулы ∃х(Р(х) & Q(x)) в реализации ℑ = <U, I> при φ. Таким образом, формула ∃х(Р(х) & Q(x)) не следует логически из формул ∃хР(х) и ∃хQ(x), т. е. рассматриваемое умозаключение неправильно.