ИСЧИСЛЕНИЕ ПРЕДИКАТОВ УЗКОЕ, исчисление предикатов первой ступени

— логическое исчисление (см. Ло-гико-математическое исчисление), определяющее с помощью доказуемых в нем формул логические законы, записываемые на специальном формальном языке перрой ступени (языке И. п. у.). Этот язык отличается от языка логики предикатов высших ступеней тем, что в его ф-лах кванторы (см. Логические операции) употребляются только с предметными переменными, но не с предикатными или функциональными. В кибернетике само И. п. у., его язык и формализацию теорий на базе И. п. у. используют для автоматизированного поиска доказательств теорем (см. также Доказательство теорем на ЭВМ), в информационно-логических системах, в лингвистике математической, в автоматов теории, в теории формальных языков, в распознавании образов и т. п.

Существуют неклассические И. ц. у. (см. Логики неклассические) и различные формулировки классического И. п. у. Полную формулировку классического И. п. у. изложили Д. Гильберт и В. Аккерман (1928).

Рассмотрим одну из формулировок классического И. п. у. Язык классического И. п. у. задают тройкой где А — алфавит, — мн-во термов, Ф — мн-во ступени. Алфавит А состоит из следующих символов: 1) счетное мн-во предметных переменных счетное мн-во предикатных символов среди которых пропозициональные символы, символы высказываний; 3) счетное мн-во функциональных символов число аргументов, «арность» предикатов и ф-ций, которые сопоставляют данным предикатным и функциональным символам в интерпретации языка 1-й ступени); 4) счетное мн-во предметных постоянных (символов нульместных функций) логические связки кванторы технические символы: скобки и запятая Мн-во термов определяется следующим образом: 1) любая предметная переменная и предметная постоянная есть терм; 2) если функциональный символ, то терм; 3) никаких других термов, кроме тех, которые получаются согласно 1) и 2), нет. Пример терма: . Ф-лы И. п. у. определяются следующими

правилами образования: 1) каждый пропозициональный символ есть если — предикатный символ, произвольные термы, то определенные в 1) и элементарными ф-лами; 3) если F и у — предметная переменная, то каждое из выражений есть никаких других ф-л И. п. у., кроме тех, которые получаются согласно 1) — 3), нет. В ф-лах областью действия квантора и соответственно . К правилам экономии скобок, введенным в исчислении высказываний, прибавим еще такие правила: будем писать вместо вместо где Вхождение переменной у в данную связанным, если оно является вхождением в некоторый квантор или или же находится в области действия этого квантора; в противном случае вхождение переменной у в свободным. Например, в и 2-е вхождения переменной -связанные, а свободное. замкнутой, если она не имеет свободных вхождений предметных переменных.

Произвольная система вида

из символов языка И. п. сигнатурой. Ф-ла И. п. у., содержащая предметные, предикатные и функциональные символы только из а, наз. ф-лой сигнатуры а. Если взять только такую часть А алфавита А и все только такие термы и ф-лы языка И. п. у., в которые входят предметные, предикатные и функциональные символы только из а, то получим некоторый язык который наз. языком 1-й ступени в алфавите А или языком 1-й ступени сигнатуры а. В частности, и сам язык И. п. у. является языком определенной сигнатуры. Язык 1-й ступени сигнатуры, в которую входят только все предикатные символы языка И. п. у. (т. е., в которой языком чистого И. п. у., а соответствующее исчисление — чистым И. п. у.

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

Интерпретацией языка И. п. у. наз. пара образованная из непустого мн-ва D — области интерпретации и отображения действующего следующим образом: каждому предикатному символу оно ставит в соответствие определенный -местный предикат в D (т. е. гс-местную функцию в D со значениями «истинно» и «ложно», или 1 и 0), каждому функциональному символу — — -местную операцию в функцию типа и каждой предметной постоянной — некоторый элемент из D. Пусть И. п. у., в которой — список всех ее переменных, имеющих свободные вхождения в F. Будем обозначать через результат подстановки в F вместо предикатных, функциональных символов и предметных постоянных именно тех конкретных предикатов, ф-ций и элементов из D, которые ф-ция ставит в соответствие символам из F. Для из D обозначим через соответственно результат подстановки каждого символа вместо всех свободных вхождений переменной соответственно в Так как в выражении стоят лишь имена конкретных предикатов, функций и элементов, то оно обозначает уже какое-то конкретное высказывание, истинность или ложность которого в области D определяется согласно обычному содержанию логических операций. истинной (соответственно, ложной) в интерпретации для заданных значений , ее свободных предметных переменных; 2) истинной (ложной) в интерпретации истинной (ложной) в области тождественно истинной, общезначимой (тождественно ложной, всегда ложной); 5) выполнимой в интерпретации выполнимой в области D; 7) выполнимой тогда и только тогда, если соответственно: 1) выражение истинно (соответственно, ложно) в истинна (ложна) в I для произвольных значений ее свободных переменных; истинна (ложна) в каждой интерпретации с областью истинна (ложна) в каждой непустой области истинна для каких-нибудь значений ее свободных переменных выполнима в какой-нибудь интерпретации с областью выполнима в какой-нибудь непустой области. Например, пусть некоторая интерпретация сопоставляет предикатному символу предикат Тогда истинна в I, так как для каждого из N истинно утверждение Говорят, что является логическим следствием мн-ва ф-л Г (обозначение ), если для любой интерпретации и для любых значений из D всех свободных переменных, входящих в какие-либо формулы из имеет место следующее: если все ф-лы из

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

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

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

Пусть К — класс ф-л сигнатуры а, ЗЛ — алгебр. система сигнатуры а, задаваемая интерпретацией Если из К истинна или выполнима в I, то говорят, что она истинна или выполнима и в алгебр, системе ЯЛ. Если все ф-лы в К замкнуты и истинны в I, то скажем, что ЯЛ является моделью для мн-ва ф-л К, а также, что мн-во К выполнимо, совместно, имеет модель (см. Моделей теория). Зададим аксиомы и правила вывода И. п. у. произвольной сигнатуры а. Терм свободным для переменной если никакое свободное вхождение i; в F не находится в области действия никакого квантора или гдеа — переменная, входящая в t. Если терм t свободен для переменной в формуле то все вхождения переменных в терм t переходят в свободные вхождения этих переменных в . В этом случае подстановку в терма t вместо всех свободных вхождений можно считать правильной, корректной. Аксиомами И. п. у. сигнатуры а являются: 1) все ф-лы, полученные из аксиом исчисления высказываний заменой произвольными ф-лами сигнатуры а; 2) все ф-лы вида где сигнатуры a, a -терм сигнатуры а, свободный для Аксиомы И. п. у., в отличие от специфических аксиом матем. исчислений наз. логическими аксиомами. Правила вывода И. п. у. следующие: 1) modus ponens: из можно получить Р; 2) правила Бернайса: если ф-ла а не содержит свободных вхождений переменной то из а можно получить а и из а можно получить . Формальной теорией 1-й ступени сигнатуры а или логико-математическим исчислением 1-й ступени сигнатуры а наз. тройка , где М—язык 1-й ступени сигнатуры — мн-во всех логических аксиом сигнатуры а и правил вывода И. п. у., А — разрешимое мн-во матем., или специфических, аксиом данной теории. Пара или тройка логическим исчислением, теория же матем. исчислением, основанным на логическом исчислении теории Т наз. выводимой в теории Т из гипотез Г (что записывается так: в теории Т) тогда и только тогда, когда она является либо аксиомой, либо ф-лой из Г, либо может быть получена из некоторых выводимых в Г из Г ф-л по правилам вывода. Ф-ла F теории Т, выводимая из пустого мн-ва гипотез, наз. доказуемой в Т или теоремой теории Т. Моделью формальной теории Т 1-й ступени сигнатуры а наз. алгебр, система, в которой истинны все теоремы теории Т.

Для удобства проведения формальных доказательств в И. п. у. вводится ряд производных правил: правило обобщения: подстановки терма вместо всех свободных вхождений переменной; подстановки ф-лы вместо предикатного символа; переименования связанной переменной и др. Одним из производных правил является теорема дедукции, аналогичная теореме дедукции в исчислении высказываний, но несколько сложнее формулируемая. Из теоремы дедукции вытекает, что доказуемость в теории 1-й ступени некоторой замкнутой равносильна доказуемости в И. п. у. некоторой , где F — конъюнкция конечного числа определенных ф-л из А. Т. о., теоремы любого матем. исчисления 1-й ступени превращаются в некоторые теоремы логического исчисления — И. п. у.

И. п. у. сигнатуры а с равенством — это исчисление на языке 1-й ступени сигнатуры а (без равенства!) такое, что в самой сигнатуре а имеется спец. двухместный предикатный символ, обозначаемый обычно через , а к аксиомам И. п. у. сигнатуры а присоединяются аксиомы

и все аксиомы вида

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

И. п. у. любой сигнатуры а полно как логическое исчисление (является семантически полным логическим исчислением): всякое логическое следствие из любого мн-ва Г ф-л сигнатуры о выводимо из Г в И. п. у. сигнатуры а. В частности, всякая тождественно истинная формула И. п. у. (т. е., всякое логическое следствие из пустого мн-ва ф-л) доказуема в нем (теорема Гёделя о полноте, 1930). Следовательно, в И. п. у. доказуемы все законы логики, выразимые на языке 1-й ступени, и только они. Семантическая полнота И. п. у. следует из более общей теоремы Гёделя — Мальцева: всякое непротиворечивое мн-во замкнутых ф-л И. п. у. имеет модель. Отсюда следует локальная теорема Мальцева для счетных сигнатур: мн-во Г замкнутых ф-л сигнатуры а имеет модель тогда и только тогда, когда каждое конечное подмн-во мн-ва Г имеет модель. Из семантической полноты И. п. у. также легко следует теорема компактности: если для мн-ва Г ф-л и для ф-лы F И. п. у., то для некоторого конечного под-мн-ва мн-ва

И. п. у. не является просто полным, т. е. в нем существует замкнутая именно, любая замкнутая выполнимая, но не тождественно истинная ф-ла) такая, что ни F ни не доказуемы в И. п. у. Присоединив к аксиомам И. п. у. все ф-лы вида , которые недоказуемы в И. п. у., получим непротиворечивое исчисление.

Проблема установления тождественной истинности ф-л 1-й ступени — неразрешима (теорема Чёрча, 1936). Отсюда и из теоремы Гёделя о неполноте следует неразрешимость проблемы: является ли произвольная ф-ла И. п. у. в нем теоремой или нет.

В рамках формальных теорий 1-й ступени можно формализовать (т. е., представить в виде теорем этих теорий) достаточно обширные разделы математики. Напр., имеются формулировки формальной теории мн-в 1-й ступенв, в которых можно вывести обычный классический анализ и значительную часть общей теории множеств. В частности, в формальной теории мн-в (1-й ступени) можно формализовать теорему и доказательство о существовании несчетно-бесконечных мн-в. Вместе с тем, согласно теореме Левенгейма — Сколема, еслв некоторое мн-во ф-л И. п. у. с равенством вмеет модель, то оно имеет конечную или счетную модель. Это т. н. парадокс Сколема.

Наряду с ранее введенными термами иногда пользуются как термами выражениями вида которые интерпретируются как «то единственное z, для которого истинно определенными описаниями. При этом в определении терма , свободного для в F, следует говорить не о переменной входящей в , а лишь о ее свободных вхождениях в . Для И. п. у. с определёнными описаниями справедлива т. н. теорема об устранимости определенных описаний. Иногда при определении И. п. у. задают не схемы аксиом, а конкретные аксиомы. При этом среди правил вывода появляется правило подстановки формулы вместо предикатного символа и усложняется формулировка теоремы дедукции. Имеется весьма естественная формулировка И. п. у., принадлежащая нем. математику Генцену (1909—45) (см. Генцена формальные системы).

Лит.: Новиков П. С. Элементы математической логики. М., 1973; Гильберт Д., Аккерман В. Основы теоретической логики. Пер. с нем. М.. 1947 [библиогр. с. 297—298]; Клини С. К. Математическая логика. Пер. с англ. М., 1973 [библиогр. с. 451 —465]; Чёрч А. Введение в математическую логику. Пер. с англ., т. 1. М., 1960; Линдон Р. Заметки по логике. Пер. с англ. М., 1968 [библиогр. с. 123]; Мендельсон Э. Введение в математическую логику. Пер. с англ. М., 1971 [библиогр. с. 296—309]. В. Ф. Костырко.