Математическая логика и теория алгоритмов. Сергиевская И.М. - 15 стр.

5. A → Bk +1 .
     Таким образом, доказано, что Γ ├ A → Bk +1 , следовательно, по методу
математической индукции, Γ ├ A → Bn , то есть Γ ├ A → B . Теорема доказана.

       Справедлива и обратная теорема.

        Теорема. Γ ├ A → B ⇒ Γ , A ├ B .
        Доказательство. Построим вывод:
1.   Γ.
2.   A.
3.   A → B . По условию теоремы, эта формула выводима из Γ .
4.   B.                                             МР 2, 3.
        Теорема доказана.

     На основании теоремы дедукции получена теорема о полноте исчисления
высказываний. Доказательство этой теоремы довольно громоздко, поэтому
желающие могут ознакомиться с ним в [12].

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

    Следствие. Множество всех теорем исчисления высказываний совпадает с
множеством всех тавтологий.

     Теорема дедукции позволяет строить выводы многих формул в исчислении
высказываний.

В Содержание.




       Построение вывода в логике высказываний.

       Пример. Докажем, что выводима формула (¬B → ¬A) → ( A → B ) .
Сокращенно это записывается так: ├ (¬B → ¬A) → ( A → B ) .
       По теореме, обратной теореме дедукции, посылку можно перенести в левую
часть:
¬B → ¬A ├ A → B .
       Проделаем эту операцию еще раз:
 ¬B → ¬A , A ├ B .



                                         20