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

       Доказательство. Докажем сначала, что аксиомы А1 – А3 являются
тавтологиями.
       Предположим, что
                                       ⎧ A = 1,
                       ⎧⎪ A = 1,       ⎪
 A → (B → A) = 0 ⇔ ⎨                 ⇔ ⎨ B = 1,
                        ⎪⎩ B → A = 0, ⎪
                                       ⎩ A = 0.
       Полученное противоречие доказывает, что аксиома А1 – тавтология.
       Предположим, что
 ( A → (B → C )) → (( A → B ) → ( A → C )) = 0 ⇔
                                    ⎧ A → (B → C ) = 1,
   ⎧⎪ A → (B → C ) = 1,             ⎪
⇔⎨                                ⇔ ⎨ A → B = 1,          ⇔
    ⎪⎩ ( A → B ) → ( A → C ) = 0,   ⎪
                                    ⎩ A → C = 0,
     ⎧ A → (B → C ) = 1,     ⎧ A → (B → C ) = 1,       ⎧ B → C = 1,   ⎧ C = 1,
     ⎪                       ⎪                         ⎪              ⎪
     ⎪ A → B = 1,            ⎪ B = 1,                  ⎪ B = 1,       ⎪ B = 1,
⇔⎨                       ⇔⎨                        ⇔ ⎨               ⇔⎨
     ⎪ A = 1,                ⎪ A = 1,                  ⎪ A = 1,       ⎪ A = 1,
     ⎪ C = 0,                ⎪ C = 0,                  ⎪ C = 0,       ⎪ C = 0.
     ⎩                       ⎩                         ⎩              ⎩
         Полученное противоречие доказывает, что аксиома А2 – тавтология.
         Предположим, что
                                           ⎧ ¬B → ¬A = 1,
 (¬B → ¬A) → ((¬B → A) → B ) = 0 ⇔ ⎪⎨                             ⇔
                                           ⎪⎩ (¬B → A) → B = 0,
                         ⎧ ¬B = 1,
     ⎧ ¬B → ¬A = 1,      ⎪                     ⎧ ¬A = 1,    ⎧ A = 0,
     ⎪                   ⎪ ¬ B  → ¬ A = 1,     ⎪            ⎪
⇔ ⎨ ¬B → A = 1, ⇔ ⎨                        ⇔ ⎨ A = 1, ⇔ ⎨ A = 1,
     ⎪                   ⎪ ¬B → A = 1,         ⎪            ⎪
     ⎩ B  = 0,           ⎪ B = 0,              ⎩ B = 0,     ⎩ B = 0.
                         ⎩
         Полученное противоречие доказывает, что аксиома А3 – тавтология.
         Таким образом, все аксиомы исчисления высказываний представляют собой
тавтологии. Теоремы выводятся по правилу вывода MP, следовательно, по ранее
полученным результатам (см. Глава 1. Высказывания, формулы, тавтологии.),
также являются тавтологиями, что и требовалось доказать.

     Следствие. Исчисление высказываний непротиворечиво.
     Доказательство. Предположим противное, то есть в исчислении есть теоремы
A и ¬A . По доказанной теореме, A и ¬A являются тавтологиями (тождественно
истинными формулами), следовательно, формула A одновременно является
тождественно истинной и тождественно ложной, что является противоречием.

     Лемма. ├ A → A .



                                      18