16. Исчисление предикатов. Общая формулировка

Примеры и упражнения предыдущего параграфа служат для обоснования утверждения, что обычный язык можно в значительной мере символизовать точным образом, если дополнить сентенциональные связки предикатами и кванторами. Исчисление предикатов занимается теорией вывода, основанной на структуре предложений, использующей связки, предикаты и кванторы. Таким образом, оно, в частности, представляет собой расширение исчисления высказываний. Тот тип исчисления предикатов, который мы будем рассматривать, допускает применение кванторов только к предметным переменным. Чтобы отличить этот простой тип исчисления от других,, его обычно называют узким исчислением предикатов или исчислением предикатов первого порядка. Кстати, мы не собираемся излагать узкое исчисление предикатов с такой же полнотой, как исчисление высказываний. Мы только сформулируем его и наметим, как его можно развить и применять. Отправной точкой послужит формулировка вроде той, какая была дана для исчисления высказываний в § 2.3.

Примем, что для каждого П = 0, 1, 2, ... дано некоторое число N-местных предикатов (или высказывательных функций от П переменных). Будем обозначать их символически через Р(Х, у) (для какого-нибудь одного двухместного предиката), Р(Х, у, Z) (для какого-нибудь одного трехместного предиката, который по необходимости будет отличаться от предиката, обозначенного через Р(Х, у), так как представляет собой функцию другого числа переменных), Q(X, у, Z) (для другого трехместного предиката), R (для 0-местного предиката, т. е. для высказывания) и т. д. Примем, что множество всех n-местных предикатов при П = 1, 2,... не пусто. В дальнейшем данные нам предикаты будем называть предикатными символами.

Пользуясь данным множеством предикатных символов, мы образуем выражения, которые будем называть «.формулами (исчисления предикатов)». Простая (или элементарная) формула есть выражение, получающееся из предикатного символа подстановкой в него вместо переменных, входящих в предикатный символ, каких-либо (не обязательно различных) переменных. Например, из предикатного символа Р(Х, у, Z) получаются простые формулы Р(Х, у, Z), Р(Х, у, у), Р(У, х, х) и Р(И, и, и). Мы расширим множество простых формул, присоединив к нему все те выражения, какие можно образовать, применяя повторно и всевозможными способами сентенциональные связки и кванторы. Точнее, мы расширим множество простых формул до такого наименьшего множества, которое удовлетворяет следующим условиям: если А и В — элементы данного множества, то элементами его будут и ~(A), (А)(В), (А)(В), (А)→(В) и (A)(B). Кроме того, если A — элемент данного множества, а Х —переменная, то (Х)А и ()A — тоже элементы этого множества. Элементы такого расширенного множества называются формулами. Те из них, которые не являются простыми, называются составными формулами.

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

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

Примеры

I. Предположим, что занимающийся аксиоматическим методом возьмется за построение теории, изложенной в главе I, как аксиоматической теории. Проанализировав, как развита эта тема, он может заключить, что все понятия теории вытекают из отношения принадлежности, т. е. из двухместного предиката «является элементом». Это может побудить исследователя создать систему такого типа, как описано выше, с применением одного-единственного предикатного символа , который должен обозначать принадлежность. Конечно, предполагаемая интерпретация предметных переменных истолковывала бы их как множества. Простые формулы такой системы состояли бы из всех выражений вида или, пользуясь более выразительным обозначением, . Затем можно было бы вводить с помощью определений, для удобства, другие предикаты. Приведем несколько таких примеров

означает ;

» ;

» ;

» ;

» .

Следующим шагом было бы принятие некоторых формул в качестве аксиом.

2. Как известно всякому ученику средней школы, основными понятиями элементарной геометрии являются «точки», «прямые» и отношение инцидентности «_____ лежит на .___». Формулируя аксиоматическую теорию, интерпретацией которой должна служить интуитивная геометрия, можно выбрать в качестве первичных терминов список предметных переменных (охватывающих точки и прямые), два одноместных предикатных символа, Р(х) и L(х), и один двухместный предикатный символ, I (х, у). Эти символы в написанном порядке можно читать как «х — точка», «х — прямая» и «х лежит на у». Среди аксиом могут оказаться следующие формулы:

(Х)Р(х); (X)L(X);

(X)(Y)(I(X, Y)*4L(Y, Х));

(х)(Р(х)→(У)(LУ)(х, у))).

3. В качестве первого шага в аксиоматизации теории частично упорядоченных множеств, описанной в главе I, можно ввести как первичные термины список предметных переменных и два двухместных предикатных символа, = (х, у) и < (х, у). Тогда простые формулы будут состоять из всех выражений вида х = у и х < у, если пользоваться привычными обозначениями. Мы могли бы принять за нелогические аксиомы теории (т. е. за аксиомы, служащие основой для создаваемой математической структуры) формулы

(х) (х = х), (х) (у) (х = у → у = х), (х) (у) (Z) (х = у у = Z → х = Z)

(это означает, что « = » есть отношение эквивалентности),

(х) (у) (х) (х = у х < Z → у < Z), (х) (у) (Z) (х = у Z < ! Х → Z < у)

(это выражает утверждение, что «равные величины можно подставлять вместо равных») и, наконец,

(х) ~ (х < х), (х) (у) (Z) (х < у у < Z → х < Z)

(устанавливая этим, что « < » выражает отношение порядка).

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

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

(х) /\ Q(X);

(У)(х);

(X) (Х) Р(X,Y);

(х) Q(х, у).

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

(X)Р(X, У)

Оба вхождения х связанные, а единственное вхождение у свободно. В формуле

(У)(х)(Р(х, У)→(Z)Q(Z))

Каждое вхождение каждой из переменных связанное. Переменная свободна в формуле, если по меньшей мере одно ее вхождение свободно: переменная связана в формуле, если по меньшей мере одно ее вхождение связано. Переменная может быть одновременно и свободной и связанной в формуле. Так обстоит, например, дело с z в формуле

(z)(P(z) (X) Q (x, z) → (Y)R(z, Y)) Q(z, x).

Если переменная свободна в формуле и входящим в формулу предикатам приписать значения, то эта переменная будет играть роль неизвестного в привычном смысле, поскольку формула становится высказыванием об этой переменной. Поясняющими примерами могут служить формулы х < 7 и (У) (у < x), в каждой из которых переменная х свободна. Формула

(У)(у < Х) (X)(X > 0),

В которой первое вхождение х свободно, а другие два связанные, иллюстрирует замечание, что, пока речь идет о смысле, свободное и связанное вхождения одной и той же переменной в одну и ту же формулу не имеют ничего общего. В самом деле, формула (x) (x > 0) является просто высказыванием и имеет тот же смысл, что и (и) (и > 0) и (W) (W > 0).

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

(x)(x2 — l = (x — 1)(х + 1))

Все вхождения x связанные, и, очевидно, х служит переменной. То, что в формуле

Х служит переменной, становится более понятным, если вспомнить, что эта формула имеет тот же смысл, что и

~(x)~(y≠x).

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

Упражнения

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

(a) (X) Р (X); (D) (Х) А (х) В (х);

(b) (х) Р (х) → Р (у); (е) (Х) (у) (Р(х) Q (у)) → (X)R(X);

(c) Р (X) → (X) Q (X); (F) (Х) (У) (Р (х, у) Q (Z)).

2. Пользуясь символами, введенными для предикатов, и арифметическими знаками (например, « + » и « < »), перевести:

(a) Если произведение конечного числа сомножителей равно нулю, то по меньшей мере один из сомножителей равен нулю (Рх обозначает «x есть произведение конечного числа сомножителей», a Gxyz — «x есть один из сомножителей числа y».

(b) Наибольший общий делитель чисел а и b делится на всякий их общий делитель (Fxy обозначает «х есть один из делителей числа у», a Gxyz — «z есть наибольший общий делитель чисел х и y»).

(c) Для всякого действительного числа х существует большее действительное число y(Rx).

(d) Существуют такие действительные числа х, у и z, что сумма чисел х и у больше, чем произведение чисел х и z.

(e) Для каждого действительного числа х существует такое у, что для каждого z, если сумма z и 1 меньше у, то сумма х и 2 меньше 4.

3. Абелеву группу можно определить как (непустое) множество А вместе с бинарной операцией в А, которая ассоциативна, коммутативна и такая, что для любых данных х и у из А уравнение x + z = y всегда имеет решение z в А. Хорошо известным примером служит Z с обычным сложением в качестве бинарной операции.

Можно дать формулировку в исчислении предикатов, взяв в качестве первичных терминов список переменных, двухместный предикатный символ = (х, у) и трехместный предикатный символ S (х, у, z). Простая формула х = у читается «х равно у», а простая формула S(x, у, z) читается «z есть сумма х и у». В качестве аксиом примем следующие формулы:

(х)(х = х);

(X)(у)(X=Y→Y=X);

(X)(у)(Z)(X=Y)Y=Z→X=Z);

(u)(v)(w)(x)(y)(z)(S(u, v, w)U=x /\ v = y /\ w = z → S(x, У, z);

(x)(y)(Z)S(x, У, z);

(x)(y)(z)(w)(S(x, y,z)S(x, y,w)→z=w);

(u)(v)(w)(x)(y)(S(u, v, w)S(w, x, У)S(v, x, z)→S(u, z, y));

(x)(y)(z)(S(x, y, z)→S(y, x, z));

(X)(Y)(Z)S(X, Z, Y).

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

< Предыдущая		Следующая >