Математическая логика и теория алгоритмов

какой формулы а не имеет места \-аи \-]а, т.е. не может быть, что­ бы одновременно были выводимы awl а. Для доказательства непро­ тиворечивости исчисления высказываний (теории L) предварительно докаясем теорему. Теорема 4.3. Всякая теорема теории L есть тавтология. ! Доказательство. Легко убедиться, например, с помощью таб­ лиц истинности, что каждая аксиома теории L есть тавтология. Из­ вестно, что если а и а=:>в тавтологии, то и S тавтология (см. теорему 1.1), т.е. правило modusponens, примененное к тавтологиям, приводит к тавтологии. И так как всякую теорему можно доказать применением только правила modusp o n e n s к аксиомам, то теорема есть тавтология. Что и требовалось доказать. Теорема 4.4. Исчисление высказываний непротиворечиво, т.е. не существует формулы а такой, чтобы а и! а были ее теоремами. | Доказательство. Согласно только что доказанной теореме 4.3, каждая теорема теории l является тавтологией. Отрицание тавтологии не является тавтологией. Следовательно, ни для какой формулы а невозможно, чтобы A u l i были теоремами исчисления высказываний. Заметим, что все остальные свойства теории L рассматриваем после выяснения ее непротиворечивости. Полнотаисчисления высказываний. При описании формальных аксиоматических систем отмечалось, что свойство полноты характе­ ризует достаточность теорем этой теории для некоторых целей. Ис­ числение высказываний будем считать полнымв широкомсмысле, ес­ ли в ней доказуема каждая формула, являющаяся тавтологией. Иначе можно сказать, что исчисление высказываний называется полной в широком смысле теорией, если множество теорем покрывает мно­ жество формул, являющихся тавтологиями. 159