Понятие вывода

Определение 3.6. Выводом из конечной совокупности формул Н называется всякая конечная последовательность формул B₁, B₂, ..., В_п, всякий член которой удовлетворяет одному из следующих трех условий:

1) он является одной из формул совокупности Н,

2) он является доказуемой формулой,

3) он получается по правилу заключения из двух любых предшествующих членов последовательности B₁, B₂, ..., В_п.

Из определений выводимой формулы и вывода из совокупности формул следуют очевидные свойства вывода:

1) всякий начальный отрезок вывода из совокупности Н есть вывод из Н;

2) если между двумя соседними членами вывода из Н (или в начале, или в конце его) вставить некоторый вывод из Н, то полученная новая последовательность формул будет выводом из Н;

3) всякий член вывода из совокупности Н является формулой, выводимой из Н;

4) если Н  W, то всякий вывод из Н является выводом из W;

5) для того чтобы формула В была выводима из совокупности Н, необходимо и достаточно, чтобы существовал вывод этой формулы из Н.

Правила выводимости

Пусть Н и W – две совокупности формул исчисления высказываний. Будем обозначать через Н, W их объединение, то есть H,W = Н  W.

В частности, если совокупность W состоит из одной формулы С, то будем записывать объединение H  {C} в виде Н,C.

Рассмотрим основные правила выводимости.

1)

Это правило следует непосредственно из определения вывода из совокупности формул.

2)

3)

4)

5) Теорема дедукции:

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

Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные исчисления высказываний как переменные алгебры высказываний, то есть переменные в содержательном смысле, принимающие два значения: истина и ложь (1 и 0).

Операции Ù, ,  и ¬ определим так же, как в алгебре высказываний (см. лекцию 1). При этом всякая формула исчисления высказываний при любых входящих в нее переменных будет принимать одно из значений 1 или 0, вычисляемое по правилам алгебры высказываний.

Введем понятие значения формулы исчисления высказываний.

Пусть А – формула исчисления высказываний, x₁, х₂, ..., х_п – попарно различные переменные, среди которых находятся все переменные, входящие в формулу А. Обозначим через α₁, α₂, ..., α_п набор значений этих переменных, состоящий из 1 и 0, длины п. Очевидно, что вектор (α₁, α₂, ..., α_п) имеет 2ⁿ значений.

Определим значение формулы А на одном таком наборе значений переменных, обозначая его через .

1. Если для формулы А ее подформула самой большой глубины есть x_i, то

2. Если определены значения всех подформул глубины k+1, то подформулы глубины k, полученные в результате операций A_i Ù A_j, A_iA_j, A_iA_j, ¬A_i будут иметь значения:

Рассмотрим три теоремы, которые устанавливают связь между основными фактами алгебры высказываний и исчисления высказываний.

Теорема 3.1. Каждая формула, доказуемая в исчислении высказываний, является тождественно истинной в алгебре высказываний.

Теорема 3.2. (о выводимости). Пусть А – некоторая формула исчисления высказываний; x₁, х₂, ..., х_п – набор переменных, содержащий все переменные, входящие в формулу А; α₁, α₂, ..., α_п – произвольный фиксированный набор значений этих переменных. Обозначим через Н конечную совокупность формул , где

1. Если ,то Н├А.

2. Если , то .

Теорема 3.3. Каждая тождественно истинная формула алгебры, высказываний доказуема в исчислении высказываний.