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

 

 

Определение. Выводом из конечной совокупности формул Н называется всякая конечная последовательность  формул В1,В2,…,Вк, всякий член которой удовлетворяет одному из следующих трех условий:

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

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

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

Как было показано в предыдущем примере, выводом из совокупности формул Н={А,В} является конечная последовательность формул:

А, В, (А→А)→((А→В)→(А)), (А→В), А→А, (А→В)→(А)), А→В, А, . (см. формулы 1,2,3,7,5,6,8).

Если же здесь воспользоваться правилом сложного заключения, то вывод можно записать так:

 А, В, (А→А)→((А→В)→(А)), В→(А→В), А→А, А→В, . (см. формулы 5, 7, 1, 3).

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

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

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

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

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

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