Философская энциклопедия - предикатов исчисление
Предикатов исчисление
ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ
общее название исчислений математической логики, являющихся формализацией тех разделов совр. логики, к-рые изучают субъектно-предикатную структуру предложений (высказываний), понимаемую в более широком, чем в традиц. логике, смысле: помимо теории свойств ("одноместных" предикатов) П. и. формализует и теорию отношений ("многоместных" предикатов). Оно охватывает исчисление высказываний (см. Логика высказываний), к-рое можно считать "исчислением нульместных предикатов" и строится обычно как его расширение. В основе П. и. лежит схема искусств, языка, отображающая субъектно-предикатную структуру предложений, т.е. их понятийное строение, причем, в отличие от традиционной силлогистики, субъект и предикат в П. и. принадлежат разным семантич. категориям: простые (имеющие лишь одно грамматич. сказуемое) предложения разговорного языка выражаются посредством обозначений типа А(х), В(у, z) и т.п., где буквы А, В и т.п. означают, каждая, нек-рое сказуемое (или предикат), а буквы х, у, z – те подлежащие или дополнения, к к-рым оно относится. Так, предложение "Николай любит Марию" может быть выражено, напр., в виде В(у, z), если мы условимся обозначать предикат "любить" буквой В, а имена "Николай" и "Мария" соответственно буквами у и z. Подобно тому, как это делается в исчислении высказываний, повествовательные предложения выражаются в П. и. формулами, образуемыми по строго опред. правилам из т.н. предикатных символов вида А (...), B(...,...), C(...,..., ...) и т.п., переменных (напр., х, у,...) и (в нек-рых случаях) символов конкретных предметов (внелогических констант) с помощью операторов логики высказываний и кванторов всеобщности и существования, являющихся логическими константами. Напр., предложение "все любят Марию" выражается в прежних обозначениях формулой ∀хВ(х, z), a предложение "существует человек, к-рый любит Марию" – формулой ∃хВ(х, z). Переменная х выражает здесь "неопределенного" (т.е. какого угодно, любого) человека; х играет роль подлежащего в предложении "человек х любит Марию". Формулу ∃xB(x, z) можно прочесть так: "существует человек х, к-рый любит Марию", для чего следует ввести условие о том, что переменной х сопоставлена предметная область (или "область изменения переменной"), состоящая из всех людей. Предложение – "все люди любят друг друга" выражается формулой ∀х∀уВ(х, у), где переменная у также выражает "неопределенного" человека. Поскольку для выражений более сложных предложений может потребоваться и большее число переменных, в языке П. и. необходимо иметь неогранич. запас переменных. Чтобы избежать здесь трудностей, связанных с понятием актуальной бесконечности, можно предположить, что переменные образуют алфавит x1, х2, х3,... и вводятся в рассмотрение по мере надобности; этот алфавит можно считать лишь потенциально бесконечным. В целях удобства можно и после этого продолжать пользоваться записью переменных в виде х, у, z и т.п., считая каждую из этих букв обозначением нек-рой переменной из алфавита x1, х2,... (см. также Квантор, Переменная). Предметной областью всех переменных алфавита можно было бы считать класс всех мыслимых объектов; однако поскольку с понятием "всех мыслимых объектов" связан ряд трудностей (см. Парадокс), обычно вместо указанной области выбирается область всех объектов, рассматриваемых в некоторой теории. Для каждой конкретной теории, к к-рой применяется П. и., этого, как правило, достаточно. Конечно, каждый язык, получаемый по описанной выше схеме, беднее естеств. разговорного языка, хотя бы уже потому, что логич. операторы последнего не исчерпываются указанными выше и содержат. напр., модальные операторы "возможно", "необходимо" и др. Однако путем расширения круга логич. констант можно достичь достаточного в логич. отношении сближения искусств, языка П. и. с той частью естеств. языка, к-рый используется в любом конкретном тексте. (На этот путь вступает, напр., лингвистика математическая при создании т.н. языков-посредников, применяемых при автоматич. переводе с одного языка на другой.) Поэтому П. и. в обрисованной выше трактовке рассматривается как осн. исчисление математич. логики.
При указанном выше естественном истолковании кванторов только замкнутые формулы получают истолкование в качестве предложений (конечно, в предположении, что дано истолкование для каждой предикатной буквы и указана область значений каждой переменной). Но и незамкнутые формулы получают нек-рые истолкования; при этом следует различать два истолкования таких формул, соответствующие след. двум случаям: 1) случаю, когда формула А(х) со свободной переменной x выражает предложение, доказанное для любого значения х; ф-ла А(х) истолковывается в этом случае так же, как и формула ∀хА(х) (т. н. интерпретация всеобщности); 2) случаю, когда появление формулы А (х) со свободной переменной x соответствует употреблению x в качестве нек-рого фиксированного значения этой переменной; с этим случаем мы встречаемся, когда, делая вывод из допущения, выражаемого ф-лой ∃хА(х), вводим в рассмотрение "такой предмет х, для к-рого справедливо А(х)"; т.к. это введение x выражается обычно словами: "допустим, что x обладает свойством А", то говорят, что тут налицо условная интерпретация (см. С. К. Клини, Введение в метаматематику, § 32). Если мы имеем дело с подобной ситуацией, то было бы очевидной ошибкой выводить из ф-лы А(х) формулу ∀хА(х) (если только область значений переменной x не состоит из одного единственного предмета).
Пусть со всеми переменными нек-рой формулы F связана одна и та же предметная область D. Если при нек-ром истолковании предикатных букв формулы F (как к.-л. свойств или отношений, определенных на D) и свободных переменных ф-лы F (как нек-рых предметов из D) эта ф-ла выражает высказывание, истинное в силу естественного (обычного) истолкования логич. констант, то F наз. выполнимой в о б л а с т и D формулой. Если это верно при любом выборе истолкования предикатных букв и свободных переменных формулы F, то F наз. общезначимой в области D. Ф-ла, общезначимая для любой непустой области, наз. (просто) общезначимой; ф-ла, общезначимая в к.-л. непустой области, называется в ы п о л н и м о й.
В математич. рассуждениях область значений переменных, как правило, бесконечна (напр., область всех натуральных чисел); поэтому при истолковании формул П. и. проявляются логические трудности, связанные с понятием математической бесконечности. При классич. подходе к математич. логике и математике эти трудности игнорируются, и о бесконечных областях рассуждают по тем же правилам, к-рые используются в рассуждениях о конечных областях. Квантор общности в формуле ∀xF(x) рассматривается в этом случае как сокращение для "бесконечной конъюнкции" F(t1)&F(t2)&...
(где tt, t2, ... совокупность всех предметов из области значений переменной х), а квантор существования в формуле ∃xF(x) как сокращение для "бесконечной дизъюнкции" F(t1)∨F(t2)∨.... Естественно, что при этом мн. законы классич. исчисления высказываний находят себе аналоги в классич. П. и. Так, законам де Моргана соответствуют общезначимые формулы классич. П. и. :
1) ∃xA(x) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ ∀xA(x),
2) ∀xA(x) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ ∃xA(x)
(где знак "ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ" обозначает операцию эквиваленции; формула вида UПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕB может рассматриваться как сокращение для формулы (U⊃B)&(B⊃U). А(х) в 1) и 2) и ниже означает произвольную формулу, в к-рую может входить но не обязательно входит переменная я. В П. и. имеют место дистрибутивности законы, выражаемые общезначимыми формулами:
3) ∀x(A(x)&B(x)) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ ∀xA(x)&∀xB(x),
4) ∃x(A(x)∨B(x)) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ ∃xA(x)∨∃xB(x);
в нем справедливы также общезначимые формулы:
5) ∀х(А∨В(х)) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ А∨∀хВ(х),
6) ∃х(А&В (x)) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ А&∃хВ(х),
7) ∀х(А&В(х)) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ A&∀xB(x),
8) ∃x(A∨B(x)) ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ А∨∃хВ(х)
(в к-рых А не содержит свободных вхождений переменной х) и ф-лы:
9) ∃x(A(x)&B(x))⊃∃xA(x)&∃xB(x),
10) ∀xA(x)∨∀xB(x)⊃∀x(A(x)∨B(x)).
Если А (х) обозначает нек-рую формулу, в к-рую может входить (но не обязательно входит) переменная х, то A(t) обозначает выражение, получающееся из А(х) подстановкой выражения t вместо всех свободных вхождений переменной x в А(х). В рассматриваемом до сих пор чистом П. и. подставляемое выражение должно быть переменной; в др. исчислениях, основанных на П. и., в качестве подставляемых выражений допускаются произвольные термы, т.е. выражения, составленные из переменных и внелогич. констант (обозначающих нек-рые конкретные предметы из предметной области) с помощью функциональных символов типа ´,+ и · для формальной арифметики. Переменные и внелогич. константы при этом также считаются термами; они наз. индивидуальными (или индивидными) переменными (соответственно константами); функциональные символы служат для обозначения функций, рассматриваемых в математич. теориях. Примерами термов для обыкновенной арифметики могут служить выражения х, 5, x + 5, 5y + x и т.п. Здесь + и (опущенный) знак умножения являются функциональными символами, а переменные х, у выражают неопредел. натуральное число. Если при подстановке t вместо всех свободных вхождений x в А (х) все вхождения переменных в t порождают свободные вхождения этих переменных в A (t), то эта подстановка t вместо x называется свободной. Если подставляемый терм t содержит переменную у, в частности если он совпадает с у, то подстановка является свободной в том и только в том случае, если никакое свободное вхождение x в А(х) не находится в области действия квантора по у, имеющегося в ф-ле А(х).
Если подстановка у вместо x в А (х) свободна, то очевидна общезначимость формул:
11) ∀xA(x)⊃A(y),
12) A(y)⊃∃xA(x).
Далее, общезначимы формулы, выражающие допустимость перестановки соседних одинаковых кванторов:
13) ∀х∀уА(х, у)⊃∀у∀хА(х, у),
14) ∃x∃yA(x, y)⊃∃y∃xΐ(x, y),
где А (х, у) любая формула, в к-рую могут входить переменные x w. у. Если соседние кванторы различны, то их перестановка, вообще говоря, приводит к нарушению общезначимости. Напр., утверждение о том, что для всякого натурального числа x существует равное ему число у, выражаемое формулой ∀х∃у(х=у), истинно, но утверждение, выраженное формулой ∃у∀х(х=у) (существует такое натуральное число у, к-рое равно любому натуральному числу х), ложно. Однако общезначима импликация
15) ∃х∀уА(х, y)⊃∀y∃xA(x, y).
К П. и. приложима теорема о замене эквивалентным, согласно к-рой, если эквиваленция СПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕЕ общезначима и ф-ла В получается из ф-лы А заменой части С на формулу E (хотя бы в одном месте формулы А), то ф-ла АПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕВ общезначима. Для образования ф-лы, эквивалентной отрицанию данной ф-лы F (т.е. для построения такой ф-лы G, что эквиваленция GПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕF общезначима), можно воспользоваться ф-лами (1) и (2) и законом де Моргана для образования отрицания в логике высказываний. В итоге отрицание всякой формулы П. и. оказывается эквивалентным такой формуле, в к-рой символ отрицания применяется только к предикатной букве. В силу закона двойного отрицания AПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕА к этому виду может быть приведена любая формула классич. П. и. (иначе говоря, всякая формула эквивалентна нек-рой формуле указ. вида). Вместе с предыдущими эквиваленциями (5)-(8), тавтологией классич. исчисления высказываний A