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

Дадим более строгую формулировку условий истинности и ложности произвольных формул вида ∀αA и ∃αА. Пусть α1, α2,..., αn,… – список всех отличных от α предметных переменных, и пусть φ приписывает α индивид u из U, а переменным α1, α2,..., αn,…, соответственно, индивиды u1, u2,..., un,… из U. Посредством ψ будем обозначать функцию, сопоставляющую переменным α1, α2,..., αn,… те же самые элементы универсума u1, u2,..., un,…, что сопоставляет и φ, а переменной α – объект v из U, который может не совпасть, а может и совпасть с u (значением α при φ). Ясно, что приписывание ψ отличается от приписывания φ не более чем значением, которое эта функция сопоставляет переменной α. Итак:

(F6)        |∀αА|φ = и ⇔ для любой функции ψ, отличающейся от функции φ не более чем приписыванием значений для переменной α, верно, что |А|ψ = и.

|∀αА|φ = л ⇔ существует функция ψ, отличающаяся от функции φ не более чем приписыванием значений для переменной α, для которой верно, что |А|ψ = л.

Иными словами, формула ∀αA принимает значение «истина» в ℑ при приписывании φ, когда ее подкванторная часть A оказывается истинной в данной реализации при приписывании переменной α любого объекта v из универсума U (а всем другим переменным – тех же самых значений). Если же в универсуме найдется такой объект v, что при указанном приписывании формула A ложна, то и ∀αA в ℑ при исходном приписывании φ принимает значение «ложь».

(F7)        |∃αА|φ = и ⇔ существует функция ψ, отличающаяся от функции φ не более чем приписыванием значений переменной α, для которой верно, что |А|ψ = и.

|∃αА|φ = л ⇔ для любой функции ψ, отличающейся от функции φ не более чем приписыванием значений для переменной α, верно, что |А|ψ = л.

Таким образом, формула ∃αA принимает значение «истина» в ℑ при приписывании φ, когда существует по крайней мере один объект v из универсума U такой, что формула A оказывается истинной при приписывании переменной α данного объекта (а всем другим переменным – тех же самых значений). Если же A окажется ложной при приписывании переменной α любого элемента универсума, формула ∃αA примет в реализации ℑ при φ значение «ложь».

Из определений (F6) и (F7) видно, что, для установления истинности или ложности формул ∀αA и ∃αА в возможной реализации ℑ при приписывании φ несущественно, какой именно объект это φ сопоставляет в качестве значения подкванторной переменной α. Вообще, при решении вопроса о том, какое значение принимает та или иная формула логики предикатов, важно указать только те индивиды, которые φ приписывает свободным переменным, входящим в данную формулу.

В качестве примера установим в заданной уже ранее конкретной реализации ℑ = <U, I> и при заданном конкретном приписывании φ значения следующих формул: (м) ∃хР(х), (н) ∃хQ(y, x), (о) ∀xP(f(x)), (п) ∀хQ(g(х, а), у).

(м)         Формула ∃хР(х) не содержит свободных переменных. Чтобы определить ее значение в ℑ при φ, необходимо, согласно (F7), выяснить, существует ли в универсуме U (т. е. в множестве целых положительных чисел) объект v такой, что |Р(х)|ψ = и, где ψ приписывает переменной х значение v, а остальным переменным (если они имеются в формуле) – те же значения, что и φ. Последнее, согласно (F1), имеет место тогда, когда ψ(x), т. е. v, является элементом I(Р) – в нашем случае элементом множества четных чисел. Итак, мы должны установить, существует ли среди целых положительных чисел число v, которое является четным. Поскольку такое число действительно существует, |∃хР(х)|φ = и.

(н) Формула ∃xQ(y, х) содержит свободную переменную у, которой φ приписало число 1. Выясним, существует ли целое положительное число v, такое что |Q(y, х)|ψ = и, где ψ(x) = v, а ψ(у) = 1. С учетом того, что I(Q) есть множество всех таких пар чисел, первое из которых больше второго, а также, в соответствии с (F1), нам следует установить, имеется ли целое положительное число v такое, что 1 > v. Поскольку такого числа нет, то, согласно (F7), можно сделать вывод: |∃xQ(y, х)|φ = л.

(о)         Чтобы установить значение в ℑ при φ замкнутой формулы ∀xP(f(x)), необходимо, в соответствии с (F6), выяснить, для всякого ли приписывания ψ, отличающегося от φ разве что значением переменной x, верно, что |Р(f(х))|ψ = и. Последнее, согласно (F1), имеет место, если значение терма f(x) при ψ является элементом I(Р), т. е. четным числом. Поскольку I сопоставляет f операцию возведения в квадрат, имеем: |f(х)|ψ = ψ(x)2. Итак, мы должны установить, для всякого ли целого положительного числа v верно, что v2 является четным. Но данное утверждение неверно для некоторых чисел, например числа 1. Итак, если ψ сопоставляет переменной x число 1, то |Р(f(х))|ψ = л. Отсюда, в силу (F6), имеем: |∀xP(f(x))|φ = л.

(п)         Формула ∀xQ(g(x, а), у) содержит свободную переменную у, которой φ сопоставляет 1. Ответим на вопрос, для всякого ли приписывания ψ, отличающегося от φ не более чем значением переменной x, верно, что |Q(g(x, а), у)|ψ = и. Если мы учтем, какие значения в ℑ принимают константы Q, g и а, и тот факт, что ψ(у) = φ(у) = 1, то данный вопрос будет звучать так: для всякого ли целого положительного числа v верно, что v + 2 > 1? Поскольку ответ на этот вопрос утвердительный, то, в соответствии с (F6), |∀xQ(g(x, а), у)|φ  = и.

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

Напомним, что законом логической теории является формула, истинная при любых допустимых в этой теории интерпретациях нелогических символов, которые входят в состав данной формулы. В логике предикатов интерпретация нелогических символов осуществляется посредством выбора некоторой возможной реализации ℑ = <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)|φ = л. Данная формула является опровержимой, поскольку мы указали реализацию и приписывание, при которых она ложна.

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