Интерпретации и модели. Общезначимые формулы и логические отношения в логике предикатов

При изложении классической логики высказываний мы выделили несколько этапов в семантическом построении логических теорий:

  • (1) задание правил интерпретации нелогических символов языка;
  • (2) придание точных значений логическим символам и формулировка условий истинности и ложности формул;
  • (3) введение понятия закона логической теории - общезначимой формулы (формулы, принимающей значение «истина» при любой интерпретации нелогических символов);
  • (4) определение основных логических отношений между формулами в теории, в частности отношения логического следования.

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

На перв ом этапе необходимо задать класс допустимых интерпретаций нелогических символов языка. Суть данной процедуры - указать, объекты каких типов могут быть сопоставлены в качестве значений нелогическим символам различных категорий. Например, в классической логике высказываний каждой пропозициональной переменной может быть сопоставлен только один из двух абстрактных объектов - «истина» или «ложь».

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

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

Процедуре интерпретации нелогических символов языка логики предикатов предшествует выбор некоторого непустого множества U, которое называют областью интерпретации или универсумом рассмотрения {рассуждения).

Условие непустоты множества U (т. е. наличие в нем по крайней мере одного элемента) является единственным требованием, предъявляемым к области интерпретации в классической логике предикатов. Таким образом, в этой теории в качестве исходной предметной области может выступать произвольное непустое множество (например, множество натуральных чисел, множество людей, множество городов, множество химических элементов и т. д.).

Интерпретация нелогических символов в логике предикатов ре- лятивизируется относительно некоторого наперед выбранного универсума U. В качестве значений этим символам могут сопоставляться лишь объекты, заданные каким-либо образом на данном универсуме.

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

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

Интерпретация предметных констант. Предметные константы, как уже говорилось, - это параметры имен естественного языка. Значениями имен являются отдельные предметы, индивиды. Поэтому предметным константам в качестве значений также должны приписываться индивиды, но не любые, а те, которые содержатся во множестве U. Так, если U есть множество людей, то функция I может приписать в качестве значения предметной константе а, например, Аристотеля, а константе b - также Аристотеля или какого-либо другого человека, скажем Сократа. Таким образом:

Глава III. Классическая логика предикатов

Функция I сопоставляет каждой предметной константе к

произвольный элемент множества U, т. е.

где «е» - знак отношения принадлежности элемента множеству.

Интерпретация предикаторных констант. Предикаторные константы являются параметрами предикаторов естественного языка. Выше отмечалось, что значениями предикаторов можно считать множества (классы) объектов, причем элементами множеств, представляемых одноместными предикаторами, являются индивиды; двухместными предикаторами - пары индивидов; трехместными предикаторами - тройки индивидов и т. д. Предикаторным константам в логике предикатов приписываются значения того же типа, только это приписывание релятивизируется относительно выбранной области интерпретации U.

Одноместной предикаторной константе функция I сопоставляет произвольное множество (возможно пустое) элементов универсума U, т. е. значением одноместной предикаторной константы является некоторое подмножество множества U.

Так, если U есть класс городов, то константе Р1 функция I может приписать, скажем, 1) пустое множество (например, множество городов, расположенных на северном полюсе), 2) множество российских городов, 3) множество городов с населением более 1 млн. человек и даже 4) множество всех городов (ведь любое множество является подмножеством самого себя).

Двухместной предикаторной константе функция I сопоставляет произвольное множество пар, состоящих из элементов U. Множество всех пар, в состав которых входят элементы U, называется второй декартовой степенью (или декартовым квадратом) множества U и обозначается U . Таким образом, значением двухместной предикаторной константы при интерпретации I является произвольное (возможно пустое) подмножество U2.

Если U есть класс городов, то константе Q2 может быть сопоставлено, например, 1) множество таких пар городов, первый из которых расположен севернее второго, 2) множество таких пар городов, первый из которых превосходит по населению второй. Пара городов <Санкт-Петербург, Москва> принадлежит первому из указанных множеств, поскольку Санкт-Петербург действительно расположен севернее Москвы, но не принадлежит второму множеству, так как Санкт-Петербург не превосходит по населению Москву. Что же касается другой пары <Москва, Санкт-Петербург>, то она, наоборот, принадлежит второму множеству, но не принадлежит первому.

Трехместной предикаторной константе сопоставляется некоторое множество троек, состоящих из элементов области интерпретации U. Иначе говоря, значением такой константы является произвольное подмножество множества всех троек, составленных из элементов U. Указанное множество называют третьей декартовой степенью множества U и обозначают U3.

Например, предикаторной константе R3 в случае, если U - класс городов, может быть сопоставлено множество таких троек городов, первый из которых расположен между вторым и третьим. В состав данного множества войдет, скажем, тройка <Москва, Киев, Новгород^ поскольку Москва расположена между Киевом и Новгородом, но не войдет тройка <Киев, Москва, Новгород>, ведь Киев не расположен между Москвой и Новгородом.

В общем случае значением /7-местной предикаторной константы будет некоторый подкласс множества U" (п-ной декартовой степени U) , которое представляет собой класс всевозможных /7-ок, составленных из элементов U:

Каждой /7-местной предикаторной константе Пп функция I сопоставляет в качестве значения произвольное множество я-членных последовательностей, состоящих из элементов универсума U, т. е.

1(ПП) с U",

где «с=» - знак включения одного множества в другое. Полагается, что первая декартова степень U (т. е. U1) есть само множество U.

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

Если в качестве универсума U выбрано множество натуральных чисел, то одноместной предметно-функциональной константе f1 интерпретационная функция I может, например, сопоставить операцию возведения в квадрат, поскольку эта операция, во-первых, является одноместной и, во-вторых, ее можно задать на множестве натуральных чисел, так как квадрат любого натурального числа сам является числом натуральным.

При том же универсуме двухместной предметно-функциональной константе g2 может быть сопоставлена операция сложения, поскольку она является двухместной и сумма любых двух натуральных чисел есть натуральное число. Итак:

Каждой «-местной предметно-функциональной константе Ф" интерпретационная функция I сопоставляет произвольную «-местную функцию, аргументами и значениями которой являются элементы множества U, т. е.

1(ФП) есть «-местная операция на универсуме U.

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

Моделью (<возможной реализацией языка) называется любая пара п = , такая что U - непустое множество, а I - функция, удовлетворяющая следующим условиям:

  • (1) I(k) е U,
  • (2) 1(Пп)сип,
  • (3) 1(Ф") есть «-местная операция, заданная на U,

где к - произвольная предметная константа, Пп - произвольная «-местная предикаторная константа, а Ф" - произвольная «-местная предметно-функциональная константа.

Интерпретация предметных переменных. Рассмотрим далее, как сопоставляются значения остальным нелогическим символам языка, а именно предметным переменным. Эта процедура также ре- лятивизирована относительно универсума U и осуществляется с помощью особой семантической функции ср, приписывающей значения предметным переменным.

Каждой предметной переменной в качестве значения функция ср приписывает произвольный элемент множества U, т. е.

где а - произвольная предметная переменная.

Обратим внимание, что с одной и той же моделью п = , если U содержит более одного элемента, можно связать бесконечное число различных приписываний значений предметным переменным. Иначе говоря, в указанных случаях имеется бесконечно много различных функций ср, ср', ф", ф'"... приписывания значений предметным переменным (две такие функции считаются различными, если они хотя бы одной переменной приписывают разные значения). Отмеченное обстоятельство обеспечивает возможность варьировать значения переменных при фиксированной интерпретации констант.

Второй этапе построении логики предикатов - задание правил, позволяющих устанавливать значения термов и формул всевозможных типов. Эти значения обусловлены выбором конкретной модели (возможной реализации) к = и конкретного приписывания элементов U предметным переменным (т. е. выбором функции ф). Возможными значениями термов являются индивиды из области интерпретации U, а возможными значениями формул - оценки «истина» и «ложь». Данный факт свидетельствует о том, что, с семантической точки зрения, термы выступают в качестве аналогов имен, а формулы - аналогов предложений естественного языка.

Правила приписывания значений термам. Покажем, как можно определить значение некоторого терма t в произвольной модели к = при некотором приписывании значений предметным переменным ф. Будем употреблять запись «|t|«значение терма t в модели к при приписывании ф».

Глава III. Классическая логика предикатов

Согласно определению терма (см. § 1 данной главы), t является либо 1) некоторой предметной константой к, либо 2) некоторой предметной переменной а, либо 3) сложным выражением вида n(tb tn), где Ф" - «-местная предметно-функциональная константа, a ti, t2,..., t„ - термы. Сформулируем правила установления значения терма t для каждого из этих трех случаев.

(Т1) Если терм t есть предметная константа к, то его значением в модели л при приписывании ср является тот индивид, который интерпретационная функция I сопоставляет константе к, т. е.

(Т2) Если терм t есть предметная переменная а, то его значением в л при приписывании ср является тот индивид, который сопоставляется переменной а посредством ср, т. е.

(ТЗ) Пусть t есть сложный терм Ф^П, t2,..., tn). Для того чтобы установить его значение в модели л при приписывании ср, необходимо: во-первых, выделить операцию, которую функция I сопоставляет предметнофункциональной константе Фп, т. е. найти 1(ФП); во- вторых, установить значения термов tj, t2,..., tn в той же модели при том же приписывании, т. е. найти |ti|n|q>; и в-третьих, применить операцию 1(Ф") к аргументам |ti|2|n|2,..., t„) в л = при приписывании ср. Таким образом,

|Ф"(1ь t2,..., t„)|9 = [1(ФП)№|ф, |12|ф,..., Itnlcp).

Приведем примеры установления значений термов в конкретной модели при конкретном приписывании значений предметным переменным. Пусть область интерпретации U есть множество целых положительных чисел. Пусть интерпретационная функция I сопоставляет константе а число 2, одноместной предметно-функциональной константе f - операцию возведения в квадрат, а двухместной предметно-функциональной константе g - операцию сложения. Пусть также предметной переменной у функция ср приписывает значение 1, т. е. ср(у) = 1. Определим, какие значения в данной модели к = и при указанном приписывании (р принимают следующие термы: (а) а; (б)у; (в) f(a); (г) g(у, а); (д) f(g(у, а)); (е) g(f(a), j).

  • (а) Поскольку а - предметная константа, значением этого терма, согласно пункту (Т1), является объект, сопоставленный функцией I константе а, т. е. число 2. Итак, |а|ф = 1(a) = 2.
  • (б) Поскольку у - предметная переменная, то ее значением, согласно пункту (Т2), является объект, который (р приписывает переменной у, т. е. число 1. Таким образом, [у|ф = ф(у) = 1.
  • (в) Установим значение сложного терма f(a). Предметно-функциональной константе f в нашей модели сопоставлена операция возведения в квадрат; значением терма а, как было показано в примере (а), является 2. Действуя в соответствии с пунктом (ТЗ), мы должны применить операцию 1(f) к аргументу |а|ф, т. е. возвести в квадрат число 2. Полученное в результате этого число 4 является искомым значением терма f(a). Таким образом, |Г(а)|ф = [I(f)](|a|9) = 22 = 4.
  • (г) Установим значение сложного терма g(у, а). Предметнофункциональной константе g в нашей модели сопоставлена операция сложения. Значениями термов у и а, как было показано в примерах (б) и (а), являются, соответственно, числа 1 и 2. Чтобы вычислить значение g{у, а), мы должны, согласно пункту (ТЗ), применить операцию 1(g) к аргументам [у|ф и |а|ф, т. е. сложить 1 и 2. В результате получим число 3 - значение терма g(у, а). Итак, |g(y, а)|ф = [l(g)](Lv|ф) =1+2 = 3.
  • (д) Для того чтобы установить значение терма f(g(y, а)), необходимо применить операцию 1(f), т. е. операцию возведения в квадрат, к объекту |g(y, а)|ф. Но значением g(y, а), как было показано в примере (г), является число 3. Поэтому возводим в квадрат число 3 и получаем число 9, которое и является значением терма f(g(y, а)).
  • (е) Для определения значения терма g(f(a), j) надо сложить значения термов f(a) и у, т. е. числа 4 и 1 (см. примеры (в) и (б)). Таким образом, значением g(f(a), j) будет 4 + 1, т. е. число 5.

Глава III. Классическая логика предикатов

Правила приписывания значений формулам. Значениями формул в модели л при произвольном приписывании ср являются объекты «истина» и «ложь». В дальнейшем в качестве сокращения для выражения «значение формулы F в модели к при приписывании значений предметным переменным ф» будем использовать запись «|F|V». Указание на приписывание ф здесь особенно важно, поскольку при установлении истинности или ложности формул вида VaA и За А приходится определять значения их подформул, варьируя приписывания значений предметным переменным. Процедура установления значений формул (так же, как и подобная процедура для термов) будет осуществляться в рамках одной и той же возможной реализации, поэтому в записи «|F|л.

Формулы, в соответствии с их определением (см. § 1 данной главы), можно разбить на три группы: (i) элементарные формулы - выражения вида n"(ti, t2,..., t„), где П" - «-местная предикаторная константа, а ti, t2,..., t„ - термы; (ii) сложные формулы, главным знаком которых является пропозициональная связка, - это выражения видов -iA, (А & В), (А v В) и (A Z) В), где А и В - формулы; (iii) сложные формулы, главным знаком которых является квантор, - это выражения видов VaA и ЗаА, где а - предметная переменная, а А - формула.

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

(i) Условия истинности и ложности элементарных формул. Чтобы установить значение элементарной формулы ПП(Ч, t2,..., t„) в модели л = при приписывании ф, необходимо: во-первых, выяснить, какое именно подмножество множества Un сопоставляется предикаторной константе Пп, т. е. найти 1(ПП); во-вторых, определить, какие значения принимают в данной модели при данном приписывании термы ti, t2,..., t„, т. е. найти |ti|ф, |t2|p,..., |tn|(p; и наконец установить, является ли последовательность <П|Ф, |t2|n|cp> элементом множества 1(П"). Если данная последовательность принадлежит ему, то формула nn(ti, t2,..., tn) принимает значение «истина», в противном случае она примет значение «ложь». Таким образом,

где «<=>» - метаязыковая эквиваленция («если и только если»).

Для разъяснения данного определения рассмотрим конкретную модель л = и конкретное приписывание предметным переменным ф, которые использовались ранее в примерах (а)-(е). Договоримся, что одноместной предикаторной константе Р интерпретационная функция I сопоставляет множество четных чисел, а двухместной предикаторной константе Q - множество таких пар целых положительных чисел, первое из которых больше второго.

Определим, какие значения в л при ф принимают элементарные формулы (ж) Q(f(a), у) и (з) P(g(y, а)).

  • (ж) Чтобы установить значение формулы Q(f(a), j) в данной модели при данном приписывании, необходимо, согласно (F1), ответить на вопрос, принадлежит ли пара <|f(a)|v, [у|ф> множеству I(Q). В примерах (в) и (б) было установлено, что значениями термов f(a) и у при приписывании ф являются, соответственно, числа 4 и 1. В данной модели I(Q) есть множество таких пар чисел, первое из которых больше второго. Пара <4, 1> принадлежит этому множеству, так как 4 больше 1. Поэтому |Q(f(a),jOI«> = «•
  • (з) Для установления значения формулы P(g(y, а)) следует выяснить, принадлежит ли значение терма g(у, а) множеству 1(Р).

В примере (г) было показано, что |g(у, а)|ф = 3. В нашей модели 1(Р) есть множество четных чисел. Поскольку число 3 не принадлежит этому множеству, формула P(g(y, а)) примет значение л в л при приписьюании ф.

(ii) Условия истинности и ложности формул, главным знаком которых является пропозициональная связка. Значения сложных формул видов —iA, (А & В), (A v В) и (А з В) в произвольной модели при произвольном приписывании значений предметным переменным обусловлены тем, какие значения в той же модели при том же приписывании принимают подформулы А и В. Таким образом, установив значения формул А и В в модели л при приписывании ф, мы можем однозначно определить, какими - истинными или ложными - в этой модели при этом же приписывании являются формулы -А, (А & В), (A v В) и (А з В).

Сформулируем условия истинности и ложности формул указанных типов, опираясь на смысл пропозициональных связок —?, &, v, z>, зафиксированный в предыдущей главе.

Глава III. Классическая логика предикатов

Покажем теперь в качестве примера, каким образом в заданной выше конкретной модели к = и при конкретном приписывании ф устанавливаются значения формул: (и) Q(f(a), v) v P(g(y, a)); (к) 4Q(f(a),y) v P(g(y9 а))); (л) Q(f(a), у) з P(g(y, a)).

  • (и) Чтобы установить значение дизъюнктивной формулы Q(f(a ),у) v P(g(y, а)) в модели п при ф, необходимо знать значение ее подформул Q(f(a),j) и P(g(y, а)). В примере (ж) было показано, что |Q(f(a),j)|Q = и, а в примере (з) - что |P(gCv, а))|ф = л. Поскольку одна из двух формул принимает в п при ф значение и, постольку, согласно (F4), и вся дизъюнктивная формула истинна в этой модели при этом приписывании, т. е. |Q(f(a),jO v P(g(y, а))|ф = и.
  • (к) Чтобы определить, какое значение в п при ф принимает формула —i(Q(f(a), j) v P(g(y, а))), нужно знать значение ее подформулы, стоящей за знаком отрицания. Как показано в примере (и), эта подформула истинна в к при ф. Поэтому, согласно (F2), ее отрицание примет значение л, значит I—'(Q(f(a), j) v P(g(y, а)))|ф = л.
  • (л) Установим значение в п при ф импликативной формулы Q(f(a), j) з P(g(y, а)). Ранее показано, что ее антецедент Q(f(a),_y) является истинным, а консеквент P(g(y, а)) - ложным. Поэтому, согласно (F5), сложная формула примет значение л, т. е. |Q(f(a),j) з P(g(y, а))|ф = л.
  • (in) Условия истинности и ложности формул, главным знаком которых является квантор. С содержательной точки зрения, выражение вида VaA следует считать истинным, если каждый индивид предметной области удовлетворяет условию, выраженному в А. Если же в предметной области существует индивид, не удовлетворяющий данному условию, то VaA окажется ложным. Что же касается утверждений вида За А, то их естественно считать истинными в том случае, когда существует индивид, удовлетворяющий выраженному в А условию, и ложными, если каждый индивид ему не удовлетворяет.

В логике предикатов условия истинности и ложности формул VaA и За А в модели л при <р определяются сходным образом. Для того чтобы установить значения этих формул, осуществляется перебор (просмотр) индивидов из универсума U. Он производится путем варьирования значения переменной а, т. е. рассматриваются все возможные приписывания vj/, сопоставляющие переменной а различные элементы U, но сохраняющие неизменными (как при исходном ср) значения других предметных переменных. Осуществляя разные приписывания подобного рода, устанавливают, какой - истинной или ложной - в каждом из этих случаев оказывается формула А.

Если А оказывается истинной, какой бы индивид из U мы ни приписывали переменной а (сохранив при этом значения других предметных переменных), то формула VaA примет значение «истина» в модели п = при приписывании ср. Если же в U найдется индивид, при приписывании которого переменной а формула А окажется ложной, то VaA примет значение «ложь».

Если приписав а какой-то элемент U (и сохранив при этом значения других переменных) мы обнаружим, что формула А принимает значение «истина», то и формулу ЗаА следует считать истинной в модели л = при исходном ср. Если же А оказывается ложной, какой бы объект ни был приписан а, то ЗаА примет значение «ложь».

Дадим более строгую формулировку условий истинности и ложности произвольной формулы вида VaA и произвольной формулы вида ЗаА. Пусть аь аг,..., а„,... - список всех отличных от а предметных переменных, и пусть ср приписывает а индивид и из U, а переменным ai,a2,..., an,..., соответственно, индивиды щ, мг,..., ип,... из U. Посредством |/ будем обозначать функцию, сопоставляющую переменным ai, аг,..., осп,... те же самые, что и ср - элементы универсума щ, мп,..., а переменной a - объект v из U, который может не совпасть, а может и совпасть с и (значением а при <р). Ясно, что приписывание |/ отличается от приписывания ср не более, чем значением, которое эта функция сопоставляет переменной а. Итак:

(F6) |VaA|«p = и для любой функции |/, отличающейся от ср не более, чем приписыванием значений для переменной а, верно, что |A|V = и.

|VaA|,p = л существует функция ц/, отличающаяся

от функции ср не более, чем приписыванием значений для переменной а, такая что |A|v = л.

Иными словами, формула VaA принимает значение «истина» в модели к при приписывании ср, когда ее подкванторная часть А оказывается истинной в данной модели при приписывании переменной a любого объекта v из универсума U (а всем другим переменным - тех же самых значений). Если же в универсуме найдется такой объект v, что при указанном приписывании формула А ложна, то и VaA в модели п при исходном приписывании ср принимает значение «ложь».

(F7) |ЗаА|ф = и <^> существует функция |/, отличающаяся от функции ср не более, чем приписыванием значений для переменной а, такая что |A|V = и.

|ЗаА|ф = л <=> для любой функции |/, отличающейся от функции ср не более, чем приписыванием значений для переменной а, верно, что |A|V = л.

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

Анализ (F6) и (F7) свидетельствует, что для установления значений формул видов VaA и ЗаА в модели п при приписывании ср несущественно, какой именно объект это ср сопоставляет в качестве значения подкванторной переменной а. Вообще, при решении вопроса о том, какое значение принимает та или иная формула логики предикатов, важно указать только те индивиды, которые ф приписывает свободным переменным, входящим в данную формулу.

В качестве примера установим в заданной ранее конкретной модели к = <11, 1> и при конкретном приписывании ф значения формул (м) ЗхР(х), (н) 3*Q(y, х), (о) VxP(f(x)), (п) V*Q(g(*, а), у).

  • (м) Формула ЗдгР(лг) не содержит свободных переменных. Чтобы определить ее значение в п при ф, необходимо, согласно (F7), выяснить, существует ли в универсуме U (т. е. в множестве целых положительных чисел) объект v, такой что |P(x)|v = и, где ф приписывает переменной х значение v, а остальным переменным - те же значения, что и ф. Последнее, согласно (F1), имеет место тогда, когда |/(jc), т. е. v, является элементом 1(Р) - в нашем случае элементом множества четных чисел. Итак, мы должны установить, существует ли число у, которое является четным. Поскольку такое число действительно существует, |ЗдгР(эг)|ф = и.
  • (н) Формула 3.xQ(j, х) содержит свободную переменную у, которой ф приписало число 1. Выясним, существует ли целое положительное число v, такое что |Q(y, jc)|v = и, где V|/(jc) = v, а ф(у) = 1. С учетом того, что 1(Q) есть множество всех таких пар чисел, первое из которых больше второго, а также, в соответствии с (F1), нам следует установить, имеется ли целое положительное число v, такое что 1 > v. Поскольку такого числа нет, то, согласно (F7), можно сделать вывод: |3*Q(y, *)|ф=л.
  • (о) Чтобы установить значение в п при ф замкнутой формулы VjcP(f(jt)), необходимо, в соответствии с (F6), выяснить, для всякого ли приписывания ф, отличающегося от ф разве что значением переменной х, верно, что |P(f(x))|v = и. Последнее, согласно (F1), имеет место, если значение терма f(x) при ф является элементом 1(Р), т. е. четным числом. Поскольку 1 сопоставляет f операцию возведения в квадрат, |f(jc)|v = фС*)2. Итак, мы должны установить, для всякого ли целого положительного числа v верно, что v2 является четным. Но данное утверждение неверно для некоторых чисел, например числа 1. Итак, если ф сопоставляет переменной л: число 1, то |P(f(x))|v = л. Отсюда, в силу (F6), имеем: |VjcP(f(jc))|

    - л.

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

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

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

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

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

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

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

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

Будем рассуждать от противного. Пусть VxP(x) з ЗхР(лг) необщезначимая (опровержимая) формула. Тогда существует возможная реализация п и приписывание (р, при которых |VjcP(jc) з 3jcP(jc)|,p = л. Тогда, согласно (F5), |УлгР(лг)|ф - и и |ЗдсР(дс)|ф = л. Истинность Ул:Р(дс), согласно (F6), означает, что Р(.х) истинно при любом приписывании, отличающемся от ср не более, чем значением х. Ложность Зл:Р(дс), согласно (F7), означает, что P(jc) ложно при любом подобном приписывании. Рассмотрим какое угодно конкретное приписывание ц/ указанного типа. Получается, что, с одной стороны, |P(.*;)|V = и, а с другой, |Р(*)|? — л. Таким образом, мы пришли к противоречию. Следовательно, допущение о необщезначимости формулы Ул:Р(л:) з ЗлгР(дс) неверно и она действительно является законом логики предикатов.

Чтобы продемонстрировать опровержимость некоторой формулы, достаточно найти такие модель п = и приписывание ср, при которых эта формула примет значение л. Покажем, например, что формула 3:tP(jt) з VjcP(jc) опровержима.

Выберем в качестве области интерпретации U множество людей. Пусть интерпретационная функция I сопоставляет пре- дикаторной константе Р множество мужчин. Исходное приписывание ср выбирается произвольным образом. Если переменной л: приписать в качестве значения Сократа, то в нашей модели п = формула Р(лг) окажется истинной, ведь Сократ является мужчиной, т. е. элементом 1(Р). Итак, существует такое приписывание р, что |Р(*)|? = и, откуда следует, что |ЗдсР(*)|ф = и при произвольном ср. Если же переменной л: приписать в качестве значения жену Сократа - Ксантиппу, т. е. выбрать приписывание такое, что ?(л:) = Ксантиппа (а всем другим переменным ? сопоставляет те же значения, что и р), то Р(л:) окажется ложной формулой, поскольку Ксантиппа не является мужчиной: |Р(дг)|? = л. Последнее означает, что |Ул:Р(дг)|ф = л. Истинность Зл:Р(л:) и ложность VjcP(a:) в п при ф свидетельствует о том, что |Зл:Р(л:) з /дгР(лг)|ф - л. Данная формула является опровержимой, поскольку мы указали модель и приписывание, при которых она ложна.

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

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

Покажем, например, что формула Зл:Р(л:) з VxP(x), необще- значимость которой была только что установлена, является выполнимой. Для этого достаточно указать конкретные модель 71 = и приписывание ф, при которых она истинна.

Пусть U снова является множеством людей, но пусть теперь I сопоставляет Р пустое множество (например, множество людей, побывавших на Солнце), функция ф может быть произвольной, так как рассматриваемая формула не содержит свободных индивидных переменных. Ясно, что ни один человек не является элементом 1(Р), ведь у пустого множества нет элементов. Поэтому формула P(jc) ложна при приписывании х любого объекта из U, т. е. IPCx)^ - л для любого ф. А из этого, согласно (F7), следует, что |ЗлгР(лг)|ф - л. Но если антецедент импликативной формулы ложен, то, согласно (F5), сама эта формула истинна, т. е. |3a*P(jc) з VjcP^)^ - и. Следовательно, рассматриваемая формула выполнима.

Из последнего определения вытекает, что:

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

В качестве примера покажем, что формула -нЗл:Р(л:) & Р(а) является невыполнимой.

Будем рассуждать от противного. Предположим, что эта формула выполнима. Тогда существует возможная реализация к = и приписывание ср, при которых она истинна. Поскольку наша формула является конъюнктивной, ее истинность, согласно (F3), означает, что |—i3jcP(jc)|,p = м и |Р(а)|ф = и. Истинность Р(а), согласно (F1), свидетельствует о том, что 1(a) е 1(Р). А истинность —|Зд:Р(л:) равносильна, согласно (F2), ложности Зд'Р(дг). Последнее, согласно (F7), означает, что |P(jc)|v = л при любом приписывании j/, которое отличается от ф разве что значением л:. В частности |P(jc)|w = л при таком ф, которое приписывает л: тот же объект, что функция 1 сопоставляет константе а, т. е. |/(jc) = 1(a). Огсюда, в соответствии с (F1), следует, что ф(лг), а значит 1(a) не содержится в 1(Р), что противоречит ранее полученному утверждению 1(a) е 1(Р). Поэтому допущение о выполнимости формулы —|ЗдгР(лг) & Р(а) неверно, и она невыполнима.

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

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

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

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

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

  • (1) Если всякий храбр, то кто-то храбр.
  • (2) Если кто-то храбр, то всякий храбр.
  • (3) Не существует храбрецов, но Ромео храбр.

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

В этом случае логической формой высказывания (1) будет формула /л:Р(л:) =э Зл:Р(л:). Ранее было установлено, что она является общезначимой. Поэтому высказывание (1) логически истинно.

Логическая форма высказывания (2) может быть выражена формулой Зл:Р(л:) =э VjcP(a:), которая, как было показано выше, опровержима и выполнима. Поэтому высказывание (2) логически неде- терминировано.

Наконец, высказывание (3) является логически ложным, поскольку его логическая форма--|Зл:Р(л:) & Р(а) - относится к числу

невыполнимых формул.

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

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

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

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

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

Покажем, например, что формулы 3atQ(a", у) и Зле—iQ(jc, у) совместимы по истинности. Для этого достаточно найти конкретную модель и = и конкретное приписывание ф, при которых каждая из этих формул истинна.

Выберем в качестве U множество городов. Пусть I сопоставляет двухместной предикаторной константе Q множество таких пар городов, первый из которых севернее второго. Пусть ср приписывает переменной у, свободной в указанных формулах, город Москву, а остальным переменным - произвольные города. Рассмотрим теперь приписывания |/ и отличающиеся от ф не более, чем значением х. Пусть функция |/ переменной у так же, как и ф, сопоставляет Москву, ах- Мурманск. Поскольку Мурманск севернее Москвы, пара <Мурманск, Москва> содержится в I(Q) и, значит, |Q(x, j)|v = и. Отсюда, согласно (F7), следует, что |3xQ(x, д>)|ф = и. Пусть функция Ъ, переменной у снова сопоставляет Москву, ах - Астрахань. Поскольку Астрахань не севернее Москвы, пара <Астрахань, Москва> не содержится в I(Q), и |Q(jc, j)|e = л. Тогда, согласно (F2), |—iQ(x, j)|t - и, откуда по (F7) получаем: |3дс—iQ(xr, ^)|фи. Таким образом, формулы 3xQ(x, у) и Зх—iQ(x, j) в рассмотренной нами модели п = при приписывании ф одновременно принимают значение «истина».

С использованием тех же самых U, I и ф можно показать совместимость по ложности формул Vx—iQ(x, j) и VxQ(x, j).

Только что было установлено, что |Q(x, j)|v - и. Отсюда по (F2) следует: |—iQ(x, j)|v = л. Тогда, согласно (F6), |Vx—iQ(x, ^)|ф = л. Кроме того, имело место |Q(x,j)|g = л. Отсюда вытекает: |VxQ(x, ^)|ф - л. Таким образом, в данной модели и при данном приписывании формулы Vx—iQ(x, j) и VxQ(x, одновременно ложны. Следовательно, они совместимы по ложности.

Формулы Vx-iQ(x, у) и VxQ(x, j) не являются вместе с тем совместимыми по истинности.

Чтобы доказать это, будем рассуждать от противного. Допустим, что они совместимы по истинности. Это означает, что существует модель к = и приписывание ф, при которых обе формулы принимают значение «истина». С учетом того, что функция ф отличается от самой себя не более, чем значением х, и используя (F6), получаем: |-iQ(x, ^)|ф - и и |Q(x, j)|9 = и. Но из того, что

Глава III. Классическая логика предикатов

|—iQ(j»c, д^)|ф = и, в силу (F2), следует, что |Q(x,j)|0 = л. В рассуждении получено противоречие. Значит, исходные формулы по истинности несовместимы.

С помощью похожего рассуждения несложно доказать несовместимость по ложности формул 3a:Q(x, у) и Зх—iQ(jc, у).

Подведем итог рассмотрению последних примеров. Исходя из них можно утверждать, что формулы /х—iQ(jc, j) и VxQ(x, j) находятся в отношении противоположности (контрарности), поскольку они совместимы по ложности, но несовместимы по истинности, а формулы 3a:Q(jc, .у) и Зл;—iQ(x, j) - в отношении подпротивоположности (субконтрарности), так как они, наоборот, совместимы по истинности, но несовместимы по ложности.

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

Допустим, что это не так. Тогда существуют модель л - и приписывание ср, при которых формулы Р(а) и Q(a) истинны, а формула Зх(Р(лт) & Q(x)) ложна. Истинность Р(а) и Q(a), согласно (F1), означает, что 1(a) е 1(Р) и 1(a) е I(Q). Поэтому, если переменной х приписать объект 1(a) посредством функции |/ (которая всем другим переменным припишет те же объекты, что и ср), то |P(xr)|v = и и |Q(jc)|v = и. Отсюда, в силу (F3), вытекает, что |Р(дс) & Q(jt)|w = и. Используя (F7), получаем, что |Зх(Р(х) & Q(jc))|«p = и. Но |Зх(Р(х) & 0(х))|ф = л согласно принятому допущению. Налицо противоречие, свидетельствующее о неверности этого допущения. А потому:

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

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

§2. Интерпретации и модели. Общезначимые формулы

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

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

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

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

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

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

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

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

Покажем, что из формул Зл;Р(л;) и 3jcQ(jc) логически не следует формула Зл:(Р(лг) & Q(jc)). Для этого достаточно найти какую-нибудь модель л = и приписывание <р, при которых формулы ЗлгР(лг) и 3jcQ(jc) примут значение «истина», а формула 3jc(P(x) & Q(x)) - значение «ложь».

Рассмотрим в качестве универсума U множество животных. Пусть интерпретационная функция I сопоставляет константе Р множество волков, а константе Q множество зайцев. Поскольку все анализируемые формулы замкнуты, приписывание ср выбирается произвольно. Формула ЗлгР(л:) истинна в указанной модели п = при (р, так как переменной х можно приписать в качестве значения животное (элемент U), которое является волком. Формула 3xQ(x) также истинна, поскольку л: можно приписать в качестве значения зайца (т. е. элемент I(Q)). Однако, какое бы животное мы ни приписали л:, оно не может оказаться одновременно и волком, и зайцем, т. е. |Р(дс) & Q(x)|w = л при любом |/. Последнее свидетельствует о ложности формулы Зл;(Р(л;) & Q(x)) в модели л = при ф. Таким образом, формула Злг(Р(лг) & Q(jc)) не следует логически из формул Зл:Р(л:) и 3jcQ(a:), т. е. рассматриваемое умозаключение неправильно.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >