4. Теоремы о полноте для расширенного одноместного исчисления предикатов.

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

Мы сначала покажем, что всякая тождественная в конечном формула расширенного одноместного исчисления предикатов всегда будет выводимой. В самом деле, пусть тождественная в конечном формула этого исчисления. Указанным методом мы построим формулу дедуктивно равную формуле и составленную из количественных формул. Эта формула, согласно доказанному ранее, также должна быть тождественной в конечном. Мы можем считать, что имеет вид конъюнктивной нормальной формы, и тогда каждый ее конъюнктивный член в отдельности также должен быть тождественным в конечном. Каждый такой член имеет вид дизъюнкции количественных формул

и их отрицаний. Сначала, пользуясь эквивалентностью

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

для любых двух чисел таких, что могут быть получены эквивалентности

и

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

либо формула

либо формула

при этом и I будут по меньшей мере равны 2.

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

не является -тождественной, а формула

не является -тождественной.

Таким образом, следует принимать во внимание лишь случай формулы

Для того чтобы эта формула была тождественной в конечном, она должна быть, в частности, -тождественной. Но, как легко видеть, это имеет место только тогда, когда

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

Отсюда следует, что каждый конъюнктивный член конъюнктивной нормальной формы является выводимой формулой, а значит, и сама также будет выводимой. Но и дедуктивно равны, и, значит, также является выводимой формулой, что и требовалось доказать.

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

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

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

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

Пусть рассматриваемая нами формула. Для ее отрицания мы можем построить дедуктивно равную, построенную из количественных формул конъюнктивную нормальную форму которой каждый ее член имеет один из трех видов

Эта формула -общезначима тогда и только тогда, когда -общезначима формула Соответственно, формула -выполнима тогда и только тогда, когда -выполнимо отрицание

формулы К. Это отрицание может быть преобразовано в дизъюнкцию 2), построенную из членов следующих видов:

Для того чтобы дизъюнкция 2) была -выполнимой, необходимо и достаточно, чтобы -выполнимым был каждый из ее членов.

Итак, необходимое и достаточное условие -выполнимости

для члена состоит в том, что

для члена состоит в том, что

для члена состоит в том, что при этом условие понимается нами как

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

Таким образом, имеются только следующие три возможности:

1. Формула не является -выполнимой ни для какого числа и тогда она опровержима.

2. Формула -выполнима для любого числа

3. Формула -выполнима для тех (и только тех) чисел которые принадлежат фиксированному конечному числу интервалов

Какой из этих трех случаев имеет место на самом деле, мы можем выяснить по виду формулы а в третьем случае мы можем найти по ней и те интервалы, в которых лежат числа для которых -выполнима.

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

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