Семантика исчисления L определяется с помощью произвольной функции е:S
{0,1}=I, удовлетворяющей для всех А,В
S соотношениям 
и е(АВ)=е(А) е(В).
Функция е называется интерпретацией исчисления L.
Лемма 1 (об интерпретации исчисления L). Для каждой функции f: РI, заданной на множестве букв исчисления L, существует единственная интерпретация еf: SI исчисления L, ограничение которой на Р равно f, в том смысле, что еf(p) = f(p), для всех p P.
Доказательство. Пусть S0 = P, Sn+1 = Sn
{
A: ASn}{(AB):A,BSn}. Утверждение леммы доказывается по индукции. Положим ef(A)=f(A) для AS0. Предполагая, что ef уже определена на Sn, продолжим её на Sn+1 следующим образом: Если А=В, для некоторого ВSn, то положим ef(A) =
; аналогично, в случае A=(BC) при некоторых В, СSn, положим ef(BC) = ef(B) ef(C). В результате получаем функцию 
, ограничение которой на Р равно f.
Формула А исчисления L называется тавтологией, если е(А)=1, для любой интерпретации е:SI исчисления L.
Теорема (о полноте). Формула А исчисления высказываний L является тавтологией тогда и только тогда, когда она является теоремой исчисления L.
Доказательство. Если формула А является теоремой исчисления L, то, поскольку аксиомы являются тавтологиями и применение MP к тавтологиям Р и РQ даёт тавтологию, мы можем заключить, что А – тавтология. Это доказывает, что каждая теорема является тавтологией. Для доказательства обратного утверждения нам понадобится следующая лемма.
Лемма 2. Пусть формула А содержит переменные а1, а2, …, аn, и пусть задана некоторая функция f: { а1,а2,…,аn }I={0,1}. Тогда 
L А’, где 
и А’ обозначают следующие формулы:
Здесь ef обозначает интерпретацию исчисления L для случая, когда Р={ а1,а2,…,аn}, по лемме об интерпретации ef определяется функцией f единственным образом.
Доказательство леммы проведем по индукции, по количеству логических связок и в формуле А. В случае, когда А = а – переменная, имеем: а L а и а Lа.
Пусть А = В. Если ef(B) = 1, то ef(A) = 0 и А’ = А = В. По предположению индукции 
L В. Пользуясь теоремой L ВВ, получаем: L В = А’. Если же ef(B) = 0, то ef(A) = 1 и А’ = А= В. По предположению индукции: L В и В =А’.
Рассмотрим случай А = (ВС). По предположению индукции:
L В’ и L С’.
Если ef(B) = 0, то независимо от значения ef(C) имеем: ef(A)=1 и В’ = 
В, А’ = А. Но L В. С помощью теоремы L В
(ВС), получаем: L ВС.
Если ef(B) = 1 , то возможны 2 случая: – ef(C) = 1 или ef(C) = 0. В случае ef(C) = 1 имеем: ef(A) = 1 и С’ = С, А’ = А = (ВС). Имеем: L С и L С(ВС) (по аксиоме А1), следовательно, L ВС. В случае ef(В) = 1 и ef(С) = 0 имеют место: А’ =A=(BC), B’ = B, C’ =C. Имеем:
L В, L С.
Пользуясь теоремой L В(С(ВС)), получаем:
L (ВС) =А’. Лемма доказана.
Вернёмся к доказательству теоремы о полноте. Пусть А – тавтология. Тогда по доказанной лемме: L А, ибо ef(A) = 1 для любой интерпретации букв 
. Значит, существуют выводы: 
L А, и 
L А . По теореме о дедукции: 
L аnА и L anА. Пользуясь теоремой L (аnА) ((аnА) А) и применяя MP, получаем: L А. Повторяя этот процесс ещё n – 1 раз, приходим к теореме: L А, что и требовалось доказать.
Упражнение
Доказать выводимость формул:
L ВВ,
L В(ВС),
L В(С(ВС))
Следствие (теорема о непротиворечивости). Исчисление высказываний L непротиворечиво в том смысле, что не существует формулы А исчисления L, для которых А и А были бы теоремами.
Доказательство. По теореме о полноте, каждая теорема исчисления является тавтологией. Но отрицание тавтологии не является тавтологией, значит, ни для какой формулы А невозможно, чтобы А и А были теоремами
.