Формулы исчисления высказываний можно
интерпретировать как формулы алгебры высказываний. Для этого будем трактовать
переменные исчисления высказываний как переменные алгебры высказываний, т. е.
переменные в содержательном смысле, принимающие два значения: истина и ложь (1
и 0).
Операции
определим так же, как
в алгебре высказываний. При этом всякая формула исчисления высказываний при
любых входящих в нее переменных будет принимать одно из значений 1 или 0,
вычисляемое по правилам алгебры высказываний.
Введем понятие значения формулы исчисления
высказываний. Пусть А –формула исчисления
высказываний, х1,х2,…,хn – попарно различные переменные, среди
которых находятся все переменные, входящие в формулу А. Обозначим через а1, а2,…,аn набор значений этих переменных, состоящих из 1 и 0, длины
n. Очевидно, что
вектор (а1,
а2,…,аn) имеет
2n значений.
Имеют место три теоремы, которые
устанавливают связь между основными фактами алгебры высказываний и исчисления
высказываний.
Теорема 1. Каждая формула, доказуемая в исчислении
высказываний, является тождественно истинной в алгебре высказываний.
Формулировка этой теоремы содержит в себе три положения:
1)Каждая аксиома исчисления высказываний – тождественно
истинная формула в алгебре высказываний.
2)Правило подстановки, примененное к тождественно истинным
формулам, приводит к тождественно истинным формулам.
3)Правило заключения, примененное к
тождественно истинным формулам, приводит к тождественно истинным формулам.
Теорема 2.( о выводимости).
Пусть А –некоторая
формула исчисления высказываний; х1,х2,…,хn
– набор переменных, содержащих все переменные, входящие в формулу А; а1, а2,…,аn – произвольный фиксированный набор значений
этих переменных. Обозначим через Н конечную совокупность формул
, где 
Тогда:
1)
Если Ra1,a2,..,an(A)=1, то H├A .
2) Если Ra1,a2,..,an(A)=0,
то H├
, где Ra1,a2,..,an(A)–значение
формулы А на наборе а1, а2,…,аn.
Теорема 3. Каждая тождественно истинная формула
алгебры высказываний доказуема в исчислении высказываний.