Раздел II . Исчисление натуральных выводов.

Примеры натуральных выводов.

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

Прежде всего, мы покажем на нескольких примерах, как в действительности протекают такие рассуждения; для этой цели мы рассмотрим три «истинные формулы» и попытаемся установить их истинность по возможности наиболее естественным путем.

 

1.1. 1-й пример: [XÚ(Y&Z)]É[(XÚY)&(XÚZ)]

Будем рассуждать так: пусть справедливо X или Y&Z. Рассмотрим следующие 2 случая:

1) Справедливо X;

2) Справедливо Y&Z.

В 1-м случае из допущения следует справедливость как XÚY, так и XÚZ, а, следовательно, и справедливость (XÚY)&(XÚZ).

В случае 2 имеет место Y&Z, т.е. как Y, так и Z.

Из Y следует XÚY, а из Z следует XÚZ.

Итак, и в этом случае справедливо (XÚY)&(XÚZ).

Таким образом, данная теорема справедлива.

 

1.2. 2-й пример: ($x"yFxy)É("y$xFxy)

Будем рассуждать так: существует такой x, что для всякого y справедливо Fxy.

Пусть a – один и таких x. Следовательно, для всех y имеет место Fxy.

Пусть b – некоторый произвольный объект. Тогда имеет место Fab.

Итак, существует некоторый x, а именно a, такой, что имеет место Fxb. Так как b любое, то это имеет место для всех объектов, т.е. для любого y существует некоторый x, такой, что имеет место Fxy. Этим рассматриваемое утверждение доказано.

 

1.3. 3-й пример. Требуется установить, что ($xFx)É("yFy) – интуиционистски истинная формула.

Мы будем рассуждать так: предположим, что не существует такого x, для которого имело бы место Fx. Отсюда надо вывести, что для всех y имеет место Fy.

Пусть a – некоторый объект, для которого Fa справедливо. Отсюда следует: существует x, для которого имеет место Fx, а именно, таким является a. Это противоречит предположению $ x Fx.

Итак, мы пришли к противоречию, т.е. Fa не может быть справедливо. А так как a мы брали совершенно произвольно, то, следовательно, для всех y имеет место Fy. Что и требовалось доказать.

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

 

 

Построение исчисления NJ.

2.1. В этом параграфе будет описано исчисление «натуральных» интуиционистских выводов истинных формул.

Интуиционистская логика не включает:

1) Закон исключенного третьего: AÚ =U.

2) Закон снятия двойного отрицания: =A.

Ограничение, накладываемое на интуиционистские выводы, вводится пока что без объяснения; обоснование такого ограничения и расширения исчисления на классические заключения (путем присоединения закона исключенного третьего) будет дано ниже.

Важнейшее внешнее отличие NJ-выводов от выводов в системах Рассела, Гильберта, Гейтинга следующее: в последних истинные формулы выводятся из некоторого множества «логических основных формул» посредством применения немногих правил вывода; натуральные же выводы исходят вообще не из логических аксиом, а из допущений, из которых делаются логические заключения. А затем посредством некоторых дальнейших заключений результат делается уже независимым от допущений.

Мы будем называть исчисления первого порядка NJ-выводов логическими.

 

2.2. После этих предварительных замечаний определим понятие NJ-вывода следующим образом.

NJ-вывод состоит из формул, расположенных в виде дерева.

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

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

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

Оба эти отклонения служат для удобства формулировки понятия вывода и не являются существенными.)

Исходные формулы вывода являются допущениями; каждая из них в выводе поставлена в соответствие в точности H-фигуре заключения (при этом данная исходная формула стоит «выше» (1, 3.5) нижней формулы этой H-фигуры заключения, что в дальнейшем будет пояснено подробнее).

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

(Таким образом, заключение делает полученное в его результате высказывание независимым от сопоставленного ему допущения.)

В соответствии со сказанным конечная формула вывода не зависит ни от каких допущений.

2.2.1. Перечень допустимых фигур заключения.

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

Из некоторой схемы получается NJ-фигура заключения, если

вместо U, B, C, D подставить любые формулы;

вместо "xFx (соответственно вместо $xFx) любую формулу, внешним знаком которой является " (соответственно $), где x обозначает стоящую за ним связанную предметную переменную;

вместо Fa – формулу, которая получается в результате замены в Fx связанной предметной переменной x всюду, где она имеется, свободной предметной переменной a.

(В качестве a может быть, например, взята переменная, уже входящая в Fx. Для заключения AE и EB эта возможность исключается приведенным ниже ограничением на переменные, а для AE и EE эта возможность сохраняется. (Если x совсем не входит в Fa, то Fa, естественно, равна Fx.) Очевидно, что Fa всегда является подформулой "xFx и $xFx в соответствии с определением подформулы в 1, 2.2.)

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

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

Обозначения отдельных схем фигур заключения:

UE, UB и т.д., означает, что построение по ним фигуры заключения являются фигурами «введения» (binfűhrung – введение) (Е) или «удаления» (beseitigung – удаление) (В) логических знаков:

Схемы фигур заключения:

UE – введение и	UB – удаление и	OE – введение или
ОB – удаление или [U]  [B]	AE – введение всеобщности	AB – удаление всеобщности
EE – введение существования	EB – удаление существования         [Fa]	FE – введение следования [U]
FB – удаление следования	NE – введение отрицания                     [U]	NB – удаление отрицания

 

Собственной переменной некоторой АЕ (соответственно ЕВ) мы называем свободную предметную переменную, обозначенную в соответствующей схеме посредством а. (Предполагается, что она существует, т.е. что она существует, т.е. что связанная предметная переметная, обозначенная посредством х, входит в формулу, обозначенную посредством Fx.)

Ограничение на переменные:

NJ-вывод должен удовлетворять еще следующим условиям (об их смысле см. §3):

собственная переменная АЕ не должна входить ни в формулу, обозначенную в схеме посредством "xFx, ни в одно из допущений, от которых эта формула зависит;

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

На этом определение «NJ-выводов» заканчивается.