2.7. Связь между алгеброй высказываний и исчислением

высказываний

 

 

Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные исчисления высказываний как переменные алгебры высказываний, т. е. переменные в содержательном смысле, принимающие два значения: истина и ложь (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.  Каждая тождественно истинная формула алгебры высказываний доказуема в исчислении высказываний.