Хотя процесс доказательства в логике аналогичен доказательствам в математике, но между ними есть и существенное различие; оно заключается в том, что в математике мы имеем дело со специфическими математическими объектами - числами, фигурами, функциями и т.п., а в логике - с высказываниями, т.е. с логическими объектами. Чтобы отличить объекты разного уровня, для представления высказываний в математике используется предметный язык, а для анализа предметного языка - метаязык, на котором формулирует свои утверждения исследователь. Проще говоря, чтобы рассуждать об объектах предметного языка, необходим метаязык, выступающий в качестве языка второго уровня. Это обстоятельство следует всегда иметь в виду в дальнейшем.
Чтобы построить доказательство высказывания или формулы в исчислении высказываний, необходимо:
1) указать те аксиомы или недоказуемые формулы, из которых выводятся все доказуемые формулы или теоремы;
2) точно сформулировать правила вывода теорем из аксиом.
В принципе к аксиомам исчисления высказываний могут быть отнесены все тавтологии (общезначимые высказывания), большинство из которых нетрудно проверить с помощью таблиц истинности. Но обычно ограничиваются перечислением небольшого числа аксиом, из которых стремятся вывести по правилам логики другие общезначимые высказывания (теоремы). Но любую теорему можно считать аксиомой, и из новой системы получить прежнюю аксиому как теорему. Обычно выбор аксиом происходит на основании удобства и целесообразности построения исчисления высказываний. Мы могли бы выбрать в качестве аксиом некоторые из законов исчисления высказываний, приведенные в разд. 3.4.
Кроме аксиом, для вывода теорем необходимы правила вывода. В исчислении высказываний обычно используются два правила: правило отделения и правило подстановки.
Правило отделения (modus ponens - МР) разрешает из двух высказываний вида А и А → В, как посылок, вывести заключение В. Схематически это правило можно представить так:
Горизонтальная черта здесь отделяет заключение от посылок. В качестве посылок выступают антецедент А и сама импликация А → В, заключением служит консеквент импликации. Таким образом, это правило разрешает нам отделить заключение от его посылок как самостоятельное знание. Так, в математике мы постоянно формулируем теоремы без указания тех посылок, из которых они выведены. Если при доказательстве ограничиваются только правилом отделения, тогда для этого необходимо убедиться в истинности посылок и правильности логического вывода. Поскольку в математике посылками служат в конечном счете аксиомы, принимаемые истинными без доказательства, постольку само доказательство сводится к проверке правильности логического вывода. В эмпирических науках, кроме того, необходимо обосновать истинность посылок, которыми могут служить различного рода допущения (эмпирические законы или обобщения, гипотезы, принципы, постулаты или даже целые теории).
Правило подстановки разрешает вместо любой переменной в исчислении высказываний подставлять любое другое высказывание, но для того чтобы получить истинное высказывание в качестве заключения, необходимо, чтобы исходная формула была истинной.
Весьма простая система аксиом для исчисления высказываний была построена Б. Расселом и А.Н. Уайтхедом, а затем усовершенствована Д. Гильбертом. Она состоит из четырех аксиом:
1) x ∨ х → х.
2) х → х ∨ у.
3) x ∨ y → y ∨ x.
4) (х → у) → ((z ∨ x) → (z ∨ у)).
Аксиома 1 утверждает, что высказывание истинно, если дизъюнкция этого высказывания с самим собой истинна.
Аксиома 2 означает, что когда высказывание истинно, то к нему можно присоединить любой - истинный или ложный - дизъюнктивный член, так как дизъюнкция будет истинной, если один из членов будет истинным высказыванием.
Аксиома 3 представляет собой закон коммутативности для дизъюнкции.
Аксиома 4 утверждает, что в случае истинности импликации к ее антецеденту и консеквенту можно присоединить любой дизъюнктивный член, ибо он не повлияет на истинность импликации. Нетрудно заметить, что во всех формулах, выражающих аксиомы, можно заменить импликацию эквивалентным выражением: (х → у) (¬ ↔ х ∨ у). Обычно для формулировки аксиом используются две логические операции, так как для выражения сложных высказываний их достаточно.
Опираясь на эти аксиомы, с помощью указанных выше правил вывода можно вывести другие истинные высказывания логики высказываний. При аксиоматическом подходе мы не обращаемся к содержательным способам установления истинности высказываний, а, предполагая аксиомы истинными, с помощью правил отделения и подстановки выводим другие истинные заключения. Этот подход можно сделать чисто формальным, если рассматривать аксиомы как исходные формулы, а логические правила вывода как правила преобразования одних формул в другие. Именно так осуществляется формальный вывод и доказательство в математике, но это занимает много времени и требует особого внимания. Однако с помощью производных правил вывода и ранее доказанных теорем процесс формального доказательства можно ускорить, хотя математики на практике не обращаются к формальным доказательствам, пока не сталкиваются с противоречиями либо парадоксами или пока не возникает необходимость в тщательной проверке всех шагов доказательства.