Докажем полноту исчисления высказываний методом Кальмара.Теореме предпошлем две леммы.
Лемма 1.
Для каждого входа (строки) истинностной таблицы для любой из пяти, основных связок исчисления высказывания, введенных ранее, справедливо соответствующее соотношение выводимости.Эта лемма утверждает существование в общей сложности 18 отношений выводимости.
Лемма 2.
Пусть дана истинностная таблица некоторой формулы Е, содержащей ( разве лишь ) атомы P1,…, Рn. Тогда справедливо
Лемма 3.
Если формула Е леммы 2 общезначима, (т. е. |= Е), то P1 VØ P1,…,РnVØ Рn |- E.
Лемма 4.
Какова бы ни была формула А, имеем |- AV Ø А
Теорема 14.
Всякая общезначимая формула доказуема; символически: Если |=Е, то |- Е.
Этим завершается доказательство равносильности теории доказательств и теории моделей на уровне исчисления высказываний.