Аналогичным образом можно доказать остальные формулы алгебры высказываний.

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

Система исчисления высказываний может быть построена методом допущений. Этот метод ближе к обычным содержательно очевидным представлениям в том отношении, что доказательства в системах, построенных этим методом, почти не отличаются от математических доказательств и от рассуждений в других науках. Здесь оно излагается по книге Е. Слупецкого, Л. Борковского «Элементы математической логики и теории множеств».

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

1) Правило отделения (обозначает ПО):

ПО φ→ ψ

;

Читается эта схема так: «Если в доказательстве имеются уже формула φ→ ψ и формула φ независимо от порядка, в каком эти формулы входят в доказательство, то к доказательству можно присоединить в качестве строки и формулу ψ».

2) Правило введения конъюнкции

ВК φ

;

Способ чтения этой схемы аналогичен.

3) Правило удаления конъюнкции:

УК ,

Правило УК можно записать в виде одной схемы:

УК

Ψ

Правило введения дизъюнкции:

ВД ,

4) Правило удаления дизъюнкции:

УД φÚ ψ φÚ ψ

,

5) Правило введения эквивалентности:

6)Правило удаления эквивалентности:

УЭ ,

Прямое доказательство выражения φ1 →(φ2→( φ3→ …(φп-1 →φп)…) строится следующим образом:

1. В первых n-1 строках выписываются последовательно выражения φ1, φ2,… φп-1 в качестве условий теоремы.

2. К доказательству можно присоединить:

a) ранее доказанные теоремы в качестве новых строк;

b) новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

1. Доказательство закончено, если его последняя строка есть выражение φп. Последняя строка доказательства не нумеруется; тем самым отмечается, что доказательство закончено.

Косвенное доказательство выражения φ1 →(φ2→( φ3→ …(φп-1 →φп)…) строится следующим образом:

1. а) В первых n-1 строках выписываются последовательно выражения φ1, φ2,… φп-1 в качестве условий теоремы.

b) В n-ой строке выписывается выражение`φп в качестве допущения косвенного доказательства.

2. К доказательству можно присоединить:

a) ранее доказанные теоремы в качестве новых строк;

b) новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

3. Доказательство закончено, если в нем имеются две противоречащие строки. Окончание доказательства отмечается написанием в последней ненумерованной строке выражения «ПРТВРЧ» (сокращение слова «противоречие») с указанием справа номеров двух противоречащих строк.