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

       |А & В|φ = л ⇔ |А|φ = л или |В|φ = л.

(F4)        |А ∨ В|φ = и ⇔ |А|φ = и или |В|φ = и.

       |А ∨ В|φ = л ⇔ |А|φ = л и |В|φ = л.

(F5)        |А ⊃ В|φ = и ⇔ |А|φ = л или |В|φ = и.

       |А ⊃ В|φ = л ⇔ |А|φ = и и |В|φ = л.

Покажем теперь в качестве примера, каким образом в заданной выше конкретной реализации ℑ и при конкретном приписывании φ устанавливаются значения формул: (и) Q(f(a), у) ∨ P(g(у, а)); (к) ¬(Q(f(а), у) ∨ Р(g(у, а))) и формулы  (л) Q(f(а), у) ⊃ Р(g(у, а)).

(и) Чтобы установить значение дизъюнктивной формулы Q(f(a), у) ∨ P(g(у, а)) в возможной реализации ℑ при приписывании φ, необходимо знать значения ее подформул, т. е. значения Q(f(a), у) и Р(g(у, а)). В примере (ж) было показано, что |Q(f(а), у)|φ = и, а в примере (з), – что |P(g(y, а))|φ = л. Поскольку одна из двух формул принимает в ℑ при φ значение и, постольку, согласно (F4), и вся дизъюнктивная формула истинна в этой реализации при указанном приписывании,
т. е. |Q(f(a), у) ∨ P(g(у, а))|φ = и.

(к) Чтобы определить значение формулы ¬(Q(f(а), у) ∨ Р(g(у, а))) в ℑ при φ, нужно знать значение ее подформулы, стоящей за знаком отрицания. Как показано в примере (и), эта подформула истинна в ℑ при φ. Поэтому, согласно (F2), ее отрицание примет значение л, т. е. |¬(Q(f(а), у) ∨ Р(g(у, а)))|φ = л.

(л) Чтобы установить в ℑ при приписывании φ значение импликативной формулы Q(f(а), у) ⊃ Р(g(у, а)) необходимо знать чему равно значение, входящих в нее подформул. Ранее показано, что ее антецедент Q(f(а), у) является истинным, а консеквент Р(g(у, а)) – ложным. Поэтому, согласно (F5), импликативная формула принимает значение л, т. е. |Q(f(а), у) ⊃ Р(g(у, а))|φ = л.

Условия истинности и ложности формул, главным знаком которых являются кванторы.

С содержательной точки зрения, выражение вида ∀αA следует считать истинным, если каждый индивид предметной области удовлетворяет условию, выраженному в А. Если же в предметной области существует индивид, не удовлетворяющий данному условию, то ∀αA окажется ложным утверждением. Что же касается выражений вида ∃αА, то их естественно считать истинными в том случае, когда существует индивид, удовлетворяющий выраженному в А условию, и ложными, если каждый индивид ему не удовлетворяет.

Разъясним смысл кванторов на простом примере. Пусть на некотором конечном множестве U, содержащем n элементов, именами которых являются индивидные константы а1, а2,..., аn, задано свойство Р. Тогда утверждение ∀хР(х) – «Всякий предмет из универсума U обладает свойством Р» – может быть заменено конечной конъюнкцией, говорящей о том, что каждый отдельно взятый предмет из универсума обладает свойством Р, а именно:

∀хР(х) ≡ Р(а1) & Р(а2) & ... & Р(аn).

В свою очередь, утверждение вида ∃хР(х) – «Существует предмет из универсума U, который обладает свойством Р» – может быть заменено конечной дизъюнкцией, говорящей о том, что по крайней мере один предмет из универсума обладает свойством Р, а именно:

∃хР(х) ≡ Р(а1) ∨ Р(а2) ∨ ... ∨ Р(аn).

Введение кванторов общности и существования в этом случае не является, вообще говоря, обязательным. Однако если универсум рассуждения U представляет собой бесконечное множество, то использование кванторов оказывается существенным, и без них обойтись уже нельзя. Последнее обусловлено тем, что мы не можем строить бесконечно длинные формулы.

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

Дадим более строгую формулировку условий истинности и ложности произвольных формул вида ∀α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, а), у)|φ  = и.