§ 3. Выводимость

1. Некоторые производные правила.

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

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

1. Наши первоначальные правила замены

2. Правила соединения, разъединения и перестановки посылок.

3. Правило контрапозиции.

4. Правила замены для эквивалентности.

5. Правила сокращения кратной посылки в импликации и присоединения произвольной посылки.

6. Правило силлогизма.

7. Схемы для конъюнкции и дизъюнкции.

8. Правило объединения двух взаимно обратных импликаций в эквивалентность.

9. Схема эквивалентности.

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

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

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

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

Правило (у): От формулы

можно перейти к формуле

Это правило допускает, как легко видеть, обобщение на случай импликаций с более чем двумя посылками.

Тем самым схема (а) обобщается на случай импликации с двумя или более посылками. С другой стороны, любое выражение

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

можно перейти к

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

мы применяем схему (а) и получаем

эта формула вместе с тождественной формулой по схем» заключения дает нам формулу

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

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

можно получить формулы

и

Первый переход осуществляется следующим образом. Из формулы (а) подстановкой вместо мы получаем формулу

вместе с исходной формулой по правилу силлогизма она дает нам

а отсюда по схеме (а) получается формула

Совершенно аналогичным образом мы можем получить и формулу

мы только должны будем вместо формулы (а) применить формулу в которой теперь вместо должно быть подставлено а вместо схемы (а) мы должны будем применить схему

Из правила (6) мы можем легко получить еще одно правило; Правило Из формулы

можно получить формулы

и

С этой целью достаточно разложить заданную эквивалентность и обе искомые на импликации и применить к ним правило (6).