ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

общее название исчислений математической логики, являющихся формализацией тех разделов совр. логики, к-рые изучают субъектно-предикатную структуру предложений (высказываний), понимаемую в более широком, чем в традиц. логике, смысле: помимо теории свойств ("одноместных" предикатов) П. и. формализует и теорию отношений ("многоместных" предикатов). Оно охватывает исчисление высказываний (см. Логика высказываний), к-рое можно считать "исчислением нульместных предикатов" и строится обычно как его расширение. В основе П. и. лежит схема искусств, языка, отображающая субъектно-предикатную структуру предложений, т.е. их понятийное строение, причем, в отличие от традиционной силлогистики, субъект и предикат в П. и. принадлежат разным семантич. категориям: простые (имеющие лишь одно грамматич. сказуемое) предложения разговорного языка выражаются посредством обозначений типа А(х), В(у, 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^BПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕAvB и правилом образования отрицания, это позволяет построить для каждой формулы классич. П. и. эквивалентную ей формулу в т.н. предваренной нормальной форме (см. Предваренная форма). Формулы (1) И (2) дают в классич. П. и. эквиваленции 16) ?xA(x) ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ ?хА(х), 17) ?хА(х) ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ ?xA(x), выражающие зависимости между кванторами. Рассмотренное здесь построение классич. П. и. является содержательным - в том смысле, что оно основано на нек-рой осмысленной (с классич. точки зрения) интерпретации употребляемых символов, согласно к-рой П. и есть формализация нек-рой части содержат. логики (логики предикатов). При аксиоматическом подходе (когда П. и. рассматривается именно как неинтерпретированное исчисление в собств. смысле слова) аксиомами обычно служат формулы, имеющие вид аксиом классич. исчисления высказываний, и формулы вида (11) и (12) - т.н. "аксиомы Бернайса" (по имени предложившего их швейц. ученого). Аксиомы Бернайса - это схемы аксиом: отд. аксиомы получаются при выборе в (11) и (12) конкретных формул в качестве А(х). Правилами вывода обычно являются modus ponens и два правила Бернайса: A?B(x) A??хВ(х) и В(х)?А ?xB(x)?A, в к-рых формула А предполагается не содержащей свободно переменной x. Доказуемыми формулами (теоремами) П. и. наз. те и только те формулы, к-рые либо являются аксиомами, либо могут быть получены из др. доказуемых формул по правилам вывода. При аксиоматич. подходе П. и. трактуется как формальная система, и в ее метатеории доказываются различные теоремы о доказуемости формул П. и. Т. к. эта метатеория имеет дело с бесконечными областями (области значений переменных, область всех формул П. и. и др.), то к рассуждениям метатеории применима вся та критика, к-рая относится к употреблению бесконечности в математич. рассуждениях и к-рая исторически связана с исследованием оснований теории множеств, с интуиционизмом и т.п. Поэтому в связи с каждым утверждением метатеории следует отдавать отчет в том, какими средствами это утверждение доказывается. Напр., непротиворечивость П. и. может быть доказана такими – т.н. ф и н и т н ы м и – средствами, в к-рых не используется понятие актуальной бесконечности, а в связи с каждым рассматриваемым конечным объектом (напр., предполагаемым выводом формулы вида А&А, допущение к-рого приводится к противоречию) и вовсе не используется понятие бесконечности, даже потенциальной. Такими же финитными средствами доказывается теорема о дедукции. Наряду с упомянутыми основными правилами вывода в П. и. имеются выводимые из них п р о и з в о д н ы е правила, дающие возможность от формул некоторого вида осуществлять переход к др. формулам. Важнейшие из них: а) правило обобщения A(х) ?хА(х); b) правило подстановки терма вместо предметной переменной А(х) А(у), где подстановка у вместо x в А(х) свободна; с) А(у) ?хA(х), где подстановка у вместо x свободна; это условие не исключает того, что переменная у может входить свободно в А(х); напр., это правило дает возможность получить формулу ?х(х=у) из ф-лы у=у; d) правило подстановки формулы вместо предикатной переменной: если доказуемая формула F содержит предикатный символ А(х1, ха, ..., хn) (т, е. если в F встречаются части вида А(y1,..., уn), где y1...,yn – переменные, не обязательно различные, подставленные вместо х1, ..., хn соответственно в А(х1, ..., хn)) и U (х1, ..., хn) – произвольная формула, содержащая свободно переменные х1, ..., хn (и, возможно, др. переменные z1, ..., zk), то доказуема формула F*, получающаяся из F заменой каждой части вида А (y1, ..., yn) на U(y1, ..., yn) при условии, что (?) каждая подстановка yi вместо xi в U(х1, ..., хn) свободна (для всех i=1, ..., n) и (?) ни одно из вхождений свободных переменных z1, ..., zk, отличных от х1, ..., хn, в ф-лу U(х1, ..., хn) не превращается при этом ни для какой заменяемой части А(y1,..., уn) в связанное вхождение к.-л., из этих переменных zj формулу F*; е) правило переименования связанной переменной: если F доказуемая формула, то доказуема всякая формула F*, получающаяся из F заменой (хотя бы в одном вхождении) некоторой части вида ?хА(х) на ?уА(у), где переменная у отлична от х, свободна для x в А (х) и не входит в А (х) (то же имеет место и для квантора ?). Известны и др. системы аксиом и правил вывода П. и. Так, можно вводить лишь один из кванторов (с соответств. ему аксиомой и правилом Бернайса), другой же определять посредством формулы (16) или (17), а соответствующие этому последнему квантору аксиому и правило Бернайса доказывать с помощью контрапозиции (см. Контрапозиции закон). Правила Бернайса можно заменить более естеств. правилом обобщения, добавив дополнительные схемы аксиом ?x(? ? В (х)) ? (А ? ?хВ (х)) и ?х(В(х) ? А) ? (?хB(х) ? А), где А - формула, не содержащая свободно переменной х. Существует и такая формулировка П. и., при к-рой в доказательствах рассматриваются лишь замкнутые формулы и единств, правилом вывода служит modus ponens. Все схемы аксиом, рассмотренные выше для П. и., изменяются при этом таким образом, что вместо указанных прежде формул в качестве аксиом берутся их замыкания (см. Замкнутая формула), а в качестве дополнит. аксиом присоединяются все формулы вида А??хА, ?х(А(х)?В(х))?(?хА(х)??xB(x)), ?х(В(х)?А)?(?хВ(х)?А), ?х?уА(х, y)??y?xA(x, у), где А -формула, не содержащая свободно переменной х. Класс доказуемых формул П. и. при всех этих формулировках не меняется (если не считать того, что при последней из них доказуемыми могут быть лишь замкнутые формулы). Важной является формулировка П. и. в виде т.н. секвенций исчисления, предложенная нем. ученым Г. Генценом (см. также Натуральное исчисление). Значение понятия доказуемости формулы в П. и. не только в том, что, согласно теореме о полноте (К. Гедель, 1930), доказуемость формулы классич. П. и. равносильна ее общезначимости и, т.о., доказуемые формулы классич. П. и. выражают законы классич. логики, но и в том, что важнейшие математич. теории допускают аксиоматич. построение, отобразимое в языке П. и., в основу к-рого, помимо аксиом и правил П. и., кладется конечное число замкнутых аксиом, характеризующих именно эту теорию (см. Метод аксиоматический). Если U – конъюнкция этих аксиом, а В – произвольная формула данной теории, то, согласно теореме о дедукции, формула В доказуема в рассматриваемой теории в том и только в том случае, если импликация U?В доказуема в П. и. Т.о., вопрос о доказуемости утверждений в математич. теориях (допускающих сведение к конечному числу "внелогических" аксиом) сводится к вопросу о доказуемости формул в П. и. Отсюда следует, что если бы в нашем распоряжении оказался метод для распознавания того, доказуема ли в П. и. та или иная формула, то он давал бы возможность распознавать доказуемость и в произвольной (конечно-аксиоматизуемой) формальной теории. Нахождение такого метода составляет задачу разрешения проблемы. Важнейшее значение имеет доказательство амер. математиком Черчем (1936) того, что проблема разрешения для П. и. неразрешима, т.е. что не существует общего метода, позволяющего распознавать доказуемость формул в П. и. (а значит, и в важнейших теориях математики). (Тем самым не существует и метода, позволяющего распознать, выполнима ли данная формула П. и. или нет.) Результат этот, показывающий – наряду с теоремой Геделя о неполноте арифметики (см. Метатеория, Полнота) – нереальность задачи полной и непротиворечивой формализации математики, дающей возможность в принципе решить любую математич. проблему, фактически вытекает уже из теоремы Геделя о полноте П. и. (этот факт стал ясен после точного определения понятия алгоритма, без которого не могла быть корректно сформулирована и сама проблема разрешения). Однако для различных частных случаев проблему разрешения все же удается решать (см. монографии В. Аккермана и Я. Шурани в списке лит.). С др. стороны, имеются результаты, относящиеся к сведению проблемы разрешения для произвольной формулы П. и. к решению этой проблемы для формул определ. вида (см. Д. Гильберт и В. Аккерман, Основы теоретической логики, перевод с нем., М., 1947, гл. 3, § 12). Помимо чистого П. и., важное значение имеет П. и. с равенством, в к-ром к числу предикатных букв добавляется "буква" = (х, у) с двумя переменными (обычно она записывается в виде х=у), определяемая аксиомами А) х=х (рефлексивность) и В) х=у?(F(x)?F(y)), где формулы F(x) и F (у) получаются свободной подстановкой x и, соответственно, у вместо z в произвольную формулу F (z). Из этих аксиом выводятся известные свойства равенства: симметричность, транзитивность и свойство замены равного равным (см. Правило замены равного равным): x =у?G(z1, ..., zk, x) ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ G(z1, ..., zk, у), в к-ром переменные x и у стоят на последнем месте чисто условно (поскольку вообще выбор порядка переменных в обозначении A (x1, ..., xn,) условен). Для классич. П. и. с равенством доказана (классич. средствами) теорема Геделя о полноте: всякая общезначимая формула этого исчисления доказуема; для него доказана также теорема Левенхейма (1915): всякая выполнимая формула выполнима в конечной или счетно-бесконечной области (а значит, в нек-рой области, состоящей из натуральных чисел). Сколем (1920) обобщил эту теорему для случая, когда вместо одной формулы речь идет о счетно-бесконечной последовательности формул, а сов. ученый А. И. Мальцев доказал ее для случая множеств формул произвольной мощности m, – в этом случае и выполнимость, имеет место в области мощности ? m (доказательство Мальцева использует средства теории множеств, в частности аксиому выбора). Важные приложения в алгебре, а также в основаниях геометрии находит следующее следствие из теоремы Левенхейма – Сколема: если каждое конечное множество, составленное из предложений F1, F2, ..., выполнимо в нек-рой непустой области, то все множество этих предложений одновременно выполнимо (и притом в области, не более чем счетно-бесконечной). Для классич. П. и. с равенством доказано, что всякая формула этого исчисления, содержащая, помимо предикатной буквы = (х, у), лишь одноместны предикатные буквы, доказуема, если она общезначима в любой непустой конечной области. Отсюда (классически) следует, что невозможно указать формулу, содержащую, помимо предикатной буквы = (х, у), лишь одноместные предикатные буквы и выполнимую только в бесконечной области. Это означает, что для характеристики свойства бесконечности невозможно ограничиться описанием, использующим, помимо равенства, лишь одноместные предикатные буквы (выражающие свойства объектов), а необходимо использовать по крайней мере двуместные предикатные буквы (выражающие отношения между объектами). Т.о., на языке рассматриваемого П. и. понятие бесконечности не может быть выражено в терминах одних только свойств (или, соответственно, к л а с с о в), – хотя бы и с помощью равенства, а требует использования теории отношений. В отличие от классич. исчисления высказываний, классич. П. и. не обладает полнотой в сильном смысле: именно, к нему можно присоединить без противоречия любую формулу, выражающую, что область значений переменных П. и. состоит из n предметов (где n – любое целое положительное число); такого рода формулы недоказуемы в П. и., причем ими исчерпываются все формулы, к-рые можно без противоречия присоединить к классич. П. и. Но для классич. П. и. справедлив нек-рый аналог теоремы о сильной полноте; именно, после добавления к классич. П. и. к.-л. недоказуемой формулы в качестве схемы аксиом, система формальной арифметики, основанная на этом П. и., становится ?-противоречивой, т.е. в ней будут доказуемы все формулы F (0), F (1),..., и ?nF(n) для некоторой формулы F(n), где областью значений переменной n являются натуральные числа. Для П. и. существуют более узкие, чем классическая, системы: интуиционистское, минимальное и положительное П. и. (см. Интуиционизм, Минимальная логика, Положительная логика). Каждое из них отличается от классического лишь тем, что в качестве схем аксиом исчисления высказываний в нем выбираются схемы аксиом интуиционистского, минимального или положительного исчисления высказываний; минимальное исчисление связано с положительным так же, как и в случае исчисления высказываний. Из приведенных выше формул в положительном П. и. доказуемы (3), (4), (6)-(15), а для (5) доказуема лишь импликация справа налево; кроме того, доказуемы формулы 18) ?х?уА(х, у)??хА(х, у), 19) ?xA(х, х)??х?yA(х, у), 20) ?xA(x)??xA(x) (эта ф-ла выражает непустоту предметной области; П. и. в рассматриваемой здесь форме к пустой области неприменимо), 21) ?x(A?B(x)) ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ A??xB(x), 22) ?x(A(x)?B) ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ ?xA(x)?B, 23) ?x(A(x)?B(x))?(?xA (x)??xB(x)), 24) ?xA ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ A, 25) ?xA ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ A, где А и В не содержат свободно х, а в (19) и (20) подстановка x вместо у в А(х, у) является свободной. Что касается минимального исчисления, то перечисленные формулы и подавно в нем доказуемы (как в более сильном, чем положительное). Поведение отрицаний и двойных отрицаний относительно кванторов общности и существования в различных системах П. и. характеризуется таблицами I – IV: В каждой из них все формулы классически эквивалентны, в минимальном же П. и. эквивалентны лишь любые две формулы каждой таблицы, не разделенные чертой или двойной чертой. Но для каждых двух формул одной таблицы, из к-рых первая выше второй, в минимальном П. и. доказуема импликация нижней формулы из верхней (напр., Ib?Ic1), тогда как обратная импликация не доказуема ни в минимальном, ни даже в интуиционистском П. и., если только эти формулы разделены чертой или двойной чертой. Но, если эти две формулы не разделены двойной чертой, то двойное отрицание этой обратной импликации доказуемо в интуиционистском П. и. Теорема о дедукции и правила вывода (a) - (d) верны для всех этих П. и. В совр. конструктивном направлении к аксиомам интуиционистского П. и. принято добавлять схемы аксиом ?х(Р(х)?Р(х)) ? (?хР(х)? ?xP(x)) и ?y1...?yn?х(Р(y1, ..., yn, x)?P((y1, ..., yn, x)) ? ?y1...?yn(?xP(y1, ..., yn, x)??xP(y1, ..., yn, x)) (n = 1, 2, 3...), называемые принципом Маркова; они недоказуемы в чистом интуиционистском П. и., и каждая из них независима от остальных его схем аксиом, т.е. не может быть доказана после их присоединения к остальным аксиомам исчисления (см. Независимость). Поэтому естественнее называть конструктивным не само интуиционистское П. и. (как это часто делается), а то П. и., к-рое получается из интуиционистского присоединением принципа Маркова, сохраняя за термином "интуиционистское П. и." его прежний смысл. При построении чистого П. и. предикатные буквы иногда рассматривают как переменные ("предикатные переменные" или "переменные предикаты") и понятие формулы изменяют так, что в формулах, наряду с этими переменными, допускают также пропозициональные переменные; последние можно трактовать как предикатные переменные с числом аргументных мест, равным нулю. Указ. выше схемы аксиом П. и. заменяются при этом построении отд. аксиомами; именно, схемам (11) и (12) соответствуют аксиомы с предикатной переменной А(х), а в пропозициональных аксиомах буквы заменяются соответствующими им пропозициональными переменными; добавляется правило подстановки (d) вместо предикатной переменной (для предикатных букв; при n = 0 это правило вырождается в правило подстановки для пропозиц. переменной, к-рое также принимается в качестве правила вывода). При таком построении П. и. усложняется формулировка теоремы о дедукции. Таким же образом может строиться и П. и. с равенством. При содержат. истолковании П. и. этого вида предикатной переменной А(х1,..., хn) соответствует пропозициональная функция, т.е. функция, принимающая в качестве своих значений высказывания, зависящие от различных значений переменных х1,..., хn Помимо чистого П. и. и П. и. с равенством, в различных вопросах приходится рассматривать т.н. прикладные П. и., в к-рых роль предикатных букв играют символы конкретных предикатов, рассматриваемых в той или иной предметной области данной дедуктивной науки. Т.о., для каждой дедуктивной науки строится свое прикладное П. и., являющееся, по существу, формализацией логики этой науки. Формулы строятся из предикатных символов так же, как из предикатных букв строятся формулы чистого П. и.; при этом на аргументных местах, наряду с индивидуальными переменными х, у,... для индивидуумов, могут встречаться и иные термы. В схемах аксиом (11) и (12) тогда вместо у может стоять любой терм t при условии, что подстановка этого терма вместо x в А (х) свободна. Каждому функциональному символу f (х1,..., хn) можно сопоставить предикатный символ P(х1,..., хn , у), значение которого определяется эквиваленцией ? (х1,..., хn, у) ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ у = f(х1,..., хn). Эта же эквиваленция позволяет перейти от рассмотрения предикатов к рассмотрению функций, что приводит к непринципиальному видоизменению П. и., называемому функциональным исчислением, в форме к-рого П. и. часто и рассматривается (см., напр. А. Черч, Введение в математическую логику, т. 1, М., 1960). Вместо функциональных символов иногда пользуются выражениями вида r?(х1,..., хn, у) (читается: "то у, для к-рого верно Р(х1,..., хn,у)"), к-рые выражают способ введения функциональных символов и наз. определенными описаниями. Определенные описания употребляются наравне с ранее рассмотренными термами, и единственное существ. отличие их от последних состоит в том, что в них есть связанная переменная у, в силу чего для определенных описаний определение свободной подстановки терма нуждается в естеств. уточнении, состоящем в том, что вместо "всех вхождений переменных в t" следует говорить о "всех свободных вхождениях...". Для всех рассмотренных разновидностей П. и. имеет место т.н. теорема об устранимости определенных описаний. Помимо опредед. описаний, рассматриваются еще т.н. н е о п р е д е л е н н ы е о п и с а н и я, обозначаемые ?уР(х1,..., хn, у) (читается: "такое у, для к-рого Р(х1,..., хn, у)"), к-рые можно вводить для любой ф-лы Р(х1,..., хn, у) произвольной формальной теории одновременно с т.н. "?-аксиомой": ?x1 ?xn (?yР (х1,..., хn y)? ? Р (х1,..., хn, ?уР(х1,..., хn, у))). Для неопредел. описаний также имеет место теорема об их устранимости. Различие между определенными и неопредел. описаниями соответствует различию между определенными и неопредел. артиклями (в тех языках, где таковые имеются). (Подробнее см. Описания операторы.) Доказательства теорем об устранимости описаний носят финитный характер (для неопредел. описаний пока известно лишь доказательство для классических П. и.). Неопредел. описания, как доказал Гильберт, могут заменить использование кванторов в классич. П. и., если ввести правило подстановки (b) (в к-ром в случае прикладного П. и. вместо у может стоять любой терм, подстановка к-рого вместо x в A(x) свободна) и правило переименования связанных переменных в неопредел. описаниях (для того чтобы такие описания можно было, не опасаясь путаницы, подставлять вместо переменных в др. описания). Именно, формулы вида ?xA(x) и ?xA(x) можно при этом рассматривать соответственно как сокращения для ф-л А(?хА(х)) и ?(?x?(x)); аксиомы и правила Бернайса будут при такой трактовке этих формул доказуемыми. ?хА(х) наз. также логической ?-функцией Гильберта, к-рую можно рассматривать как осуществляющую "выбор такого х, что А (х) верно для этого х, если оно вообще верно хотя бы для одного предмета". Иногда рассматриваются П. и. с несколькими алфавитами переменных, принимающих значения в разл. областях, - и даже П. и. с бесконечным числом таких алфавитов (как в нек-рых разновидностях теории типов). В таких случаях все приведенные выше формулы по-прежнему являются доказуемыми, за исключением формул (18) и (19). (Напр.: в (13) - (15) не требуется, чтобы переменные x а у принадлежали одному и тому же алфавиту.) Впрочем, для всякой теории с двумя алфавитами переменных х, у, ... и ?, ?,... можно ввести один новый алфавит ?, ?,... и новые предикатные буквы S(X), T(X), ..., если кванторы ?XF(X) и ?XF(X) истолковывать как сокращения для ?xF(x)&??F(?) и ?xF(x)???F(?) соответственно, а для предикатных букв S и ? ввести аксиомы S(X)ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ?x(X=x) и T(Х)ПРЕДИКА?ТОВ ИСЧИСЛЕ?НИЕ?? (Х=?), то данная формальная теория окажется вложенной в эту новую теорию с одним алфавитом переменных и будет от нее отличаться лишь несущественно. Все рассмотренные выше П. и. наз. П. и. первой ступени, или узким П. и. (или функциональным исчислением первой ступени). Большое значение имеют такие расширения П. и. этого вида, как П. и. второй ступени, в к-ром вместо предикатных букв имеются предикатные переменные и кванторы для этих переменных, а также ступенчатые исчисления, или теории типов, в к-рых предикаты или формулы могут быть допустимыми значениями аргументов др. предикатов. В ступенчатых П. и. во избежание парадоксов каждой предикатной букве приписывается нек-рое натур. число – ступень или тип – и аргументами этой предикатной буквы могут быть только предикатные буквы (или формулы) низших ступеней. Подробнее об этих П. и. см. Типов теория. Рассматриваются также П. и. с модальностями "возможно" и "необходимо" в качестве дополнит. пропозициональных операторов; см. Модальная логика. Основоположником П. и. является Фреге (1879), к-рый ввел пропозициональные функции и кванторы. Ч. Пирс снова и независимо от Фреге ввел кванторы в 1885; ему "же принадлежит и термин "квантор" (quantifer). Совр. обозначения в П. и. восходят к Пеано и Расселу. Первоначально П. и. 1-й ступени рассматривалось совместно с исчислениями более высоких ступеней: у Фреге (1903) – без теории типов (с чем и связана противоречивость его системы П. и.), у Рассела (1908) – в рамках теории типов (самый ранний вариант теории типов разработан Э. Шредером применительно к логике классов, 1898). Впервые самостоятельно и в полном объеме (но только для классич. случая) П. и. 1-й ступени рассматривалось Д. Гильбертом и В. Аккерманом (1928) и в более ранних работах того же Гильберта (1925, 1927). Правило подстановки было впервые корректно сформулировано Д. Гильбертом и П. Бернайсом (1934). Важные результаты, относящиеся к П. и., принадлежат также Левенхейму, Сколему, Г. Беману, Ж. Эрбрану, Куайну, П. Бернайсу, М. Шейнфинкелю, К. Геделю, Л. Генкину, Г. Генцену, А. Гейтингу, А. А. Маркову, Б. А. Трахтенброту, М. Вайсбергу, Л. Кальмару, К. Шютте и др. Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957 (имеется библ.); Яновская С. ?., Математическая логика и основания математики, в кн.: Математика в СССР за 40 лет, т. 1, М., 1959; Hilbert D. und Bernays Р., Grundlagen der Mathematik, Bd 1, B., 1934; Ackermann W., Solvable cases of the decision problem, Amst., 1954; Sur?nyi J., Reduktionstheorie des Entsctieidungsproblems im Pr?dikatenkalk?l der ersten Stufe, Bdpst, 1959. А. С. Москва