§ 6. Дедуктивное равенство и дедукционная теорема

1. Понятие дедуктивного равенства; два существенных случая дедуктивного равенства; переводимость и дедуктивное равенство.

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

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

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

может быть выведено из из . Однако обратное утверждение места не имеет: переводимость из дедуктивного равенства не вытекает.

Поясним это на следующих двух типичных примерах:

1. Формула

(А как отдельно взятая формульная переменная) дедуктивно равна формуле 1 А. Действительно, 1 А получается из А путем подстановки; с другой стороны, из 1 А мы можем подстановкой получить , а затем, воспользовавшись тождественной формулой

получить и А.

Однако переводимость места не имеет; действительно, если бы формула

была выводима в исчислении предикатов, то в нем была бы выводима вообще любая формула, что, как мы видели, места не имеет.

2. Формула

дедуктивно равна формуле

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

была выводима, то выводима была бы и

Однако это не так, потому что формула эта не является даже 2-тождественной.

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

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

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

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

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