Производные правила вывода

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

1. Правило одновременной подстановки (ПОП). Пусть − доказуемая формула, − переменные, − любые формулы исчисления высказываний. Тогда результат одновременной подстановки в вместо соответственно формул является доказуемой формулой. Схематично операция одновременной подстановки записывается так:

.

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

2. Правило сложного заключения (ПСЗ). Это правило применяется к формулам вида и формулируется так: если формулы и доказуемы, то доказуема и формула .

Схематически это правило записывается так:

ПСЗ легко доказывается последовательным применением ПЗ. Действительно, если формулы и доказуемы, то согласно ПЗ доказуема формула . Но так как формулы и доказуемы, то доказуема и формула

Продолжая эти рассуждения, мы докажем, наконец, что формула L доказуема.

3. Правило силлогизма (слово силлогизм греческое и означает дедуктивное логическое умозаключение). Если доказуемы формулы и , то доказуема формула т.е.

Это правило аналогично свойству транзитивности в обычной алгебре: если то

Докажем справедливость правила силлогизма. Для этого сделаем следующие одновременные подстановки:

и

Получим доказуемые формулы

(1)

(2)

Кроме того, по условию

(3)

(4)

Из формул (4) и (2) согласно ПЗ получаем

(5)

Но тогда из формул (5), (3) и (1) согласно ПСЗ получаем

,

что и требовалось доказать.

4. Правило контрпозиции. Если доказуема формула , то доказуема и формула , т.е.

Доказательство. Сделаем одновременную подстановку

в результате получаем

(1)

Но по условию доказуема формула

(2)

Из формул (2) и (1) согласно ПЗ имеем , что и требовалось доказать.

5. Правило снятия двойного отрицания (ПСДО). Если доказуема формула , то доказуема и формула т.е.

Если доказуема формула , то доказуема формула т.е.

Доказательство. Выполним подстановки

и ,

получим

(1)

(2)

Но по условию

(3)

(4)

Таким образом, из формул (3) и (2) по правилу силлогизма получаем , а из формул (1) и (4) по тому же правилу получаем , что и требовалось доказать.