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

1. Доказать, что (эту формулу называют рефлексивностью импликации).

Воспользуемся аксиомой

и выполним подстановку . Тогда получим

(1)

Применяя правило заключения к аксиоме и формуле (1), получим

(2)

В формуле (2) осуществим подстановку

В результате получим доказуемую формулу

(3)

Применяя правило заключения к аксиоме IV₂ и формуле (3), получим (4)

Наконец, осуществив подстановку в формуле (4) вместо формулы , получим

3. Правила вывода доказуемых формул из аксиом.

Исчисление высказываний опирается на 11 аксиом и 2 простейших правила вывода. Все аксиомы являются правильными сложными высказываниями. Они разделены на 4 группы.

Система аксиом исчисления высказываний

Первая группа аксиом:

I₁

I₂

Вторая группа аксиом:

II

II

II

Третья группа аксиом:

II

II

II

Четвертая группа аксиом:

IV

IV

IV

1. Правило подстановки

Если формула доказуема в исчислении высказываний, – переменное высказывание – любая формула исчисления высказываний, то формула, полученная в результате замены всюду в формуле переменной формулой _, является также доказуемой формулой.

Это правило носит название правила подстановки и символически записывается так:

Правило подстановка схематически запишется так

Читается эта запись следующим образом: “Если формула доказуема, то доказуема и формула ”.

2. Правило заключения (ПЗ)

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

1. 2.3. Определение доказуемой формулы

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

а) всякая аксиома является доказуемой формулой;

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

в) формула , полученная из доказуемых формул и путем применения правила заключения, есть доказуемая формула;

г) никакая другая формула исчисления высказываний не считается доказуемой.

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

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

(из методички Глушаня. НЕ ПИСАТЬ ЦЕЛИКОМ, СОКРАТИТЬ, ВЫБРАТЬ ТОЛЬКО ГЛАВНОЕ!!!!!)

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) по тому же правилу получаем , что и требовалось доказать.