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

 

Будем рассматривать конечную совокупность формул Н={А1,А2,…,Аn}.

Определение формулы, выводимой из совокупности Н.

1)Всякая формула AiÎH, является формулой, выводимой из Н.

2) Всякая доказуемая формула  выводима из Н.

3) Если формулы С и С→В выводимы из совокупности Н, то формула В также выводима из Н.

Если  некоторая формула В выводима из совокупности Н, то это записывают так: Н├В.

Нетрудно видеть, что класс формул, выводимых из совокупности Н, совпадает с классом доказуемых формул  в случае, когда совокупность Н содержит только доказуемые формулы, и в случае, когда Н пуста.

Если же совокупность формул Н содержит хотя бы одну не доказуемую формулу, то класс формул, выводимых из Н, шире класса доказуемых формул.

Пример.

Доказать, что из совокупности формул Н={А, В} выводима формула .

Так как AÎH и BÎH, то по определению выводимой формулы

Н├А,                                                                                                             (1)

Н├В.                                                                                                   (2)

Возьмем аксиомы и , и выполним подстановки и .

В результате получим доказуемые формулы, которые выводимы из Н по определению выводимой формулы, т. е.

Н├(А→А)→((А→В)→(А)),                                              (3)

Н├В→(А→В),                                                                                  (4)

Так как формула А→А доказуема, то Н├А→А.                              (5)

Из формул (5) и (3) по правилу заключения получаем:                                                          Н├(А→В)→(А)).                                                                           (6)

Из формулы (2) и (4) по правилу заключения получаем:

Н├А→В .                                                                                      (7)

Из формул (7) и (6) по правилу заключения получаем:

Н├А .                                                                               (8)

И, наконец,  из формул (1) и (8) получаем:

Н├                                                                        (9)

Ясно, что при доказательстве выводимости формулы из совокупности формул можно пользоваться не только основным правилом заключения, но и правилом сложного заключения. Тогда, пользуясь этим правилом, предложение (9) можно получить из предложений (5), (7), (1) и (3).