9. Некоторые проблемы аксиоматического исчисления предикатов

   1. Разрешимость

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

Проблема разрешимости для исчисления предикатов, в отличие от исчисле­ния высказываний, оказалась связанной с серьезными трудностями, завися­щими от точного определения понятия алгоритма. После появления точного определения алгоритма появилась возможность доказать, что проблема раз­решимости для исчисления предикатов неразрешима, т. е. необходимый в ЭТОЙ проблеме алгоритм невозможен .

2. Непротиворечивость и независимость

Противоречивым называется такое исчисление, в котором какая-либо фор­мула доказуема вместе со своим отрицанием. Эта проблема для исчисления предикатов решается в положительном смысле. Для доказательства непроти­воречивости достаточно обнаружить какую-нибудь невыводимую формулу в исчислении предикатов.

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

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

3. Полнота в узком смысле

Логическая система называется полной в узком смысле, если нельзя без про­тиворечия присоединить к ее аксиомам в качестве новой аксиомы никакую не выводимую в ней формулу так, чтобы полученная при этом система была бы непротиворечивой.

В отличие от исчисления высказываний, исчисление предикатов оказывается неполным в узком смысле. К его аксиомам можно присоединить без проти­воречия недоказуемую в нем формулу xF(x) —> xF(x). Все предметы то­ждественны — таков содержательный смысл этой формулы. Приведем для доказательства лишь соображения, носящие общий характер. Каждая выводимая формула исчисления высказываний имеет выводимый аналог в исчислении предикатов и может быть присоединена к аксиомам это­го исчисления. Например, такая: А—> А. Она выводима в исчислении выска­зываний. Если область определения М предиката F(x) состоит из одного элемента х, то А—> А превращается в исчислении предикатов в формулу xF(x) —> xF(x), которая будет истинной. Она не будет истинной, если М содержит больше, чем один элемент. Однако из общелогических поло­жений нельзя заключить, что область М содержит более одного элемента. Таким образом, исчисление предикатов неполно в узком смысле.