Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

ponens, примененное к тавтологиям, приводит к тавтологии. И так как всякую теорему можно доказать применением только правила modus ponens к аксиомам, то теорема есть тавтология. Что и требовалось доказать. Теорема 4.4. Исчисление высказываний непротиворечиво, т.е. не существует формулы А такой, чтобы А и —Л были ее теоремам Доказательство. Согласно только что доказанной теореме 4.3, каждая теорема теории L является тавтологией. Отрицание тавтологии не является тавтологией. Следовательно, ни для какой формулы А невозможно, чтобы А и —А были теоремами исчисления высказываний. Заметим, что все остальные свойства теории L рассматриваем после выяснения ее непротиворечивости. Полнота исчисления высказываний. При описании формальных аксиоматических систем отмечалось, что свойство полноты характеризует достаточность теорем этой теории для некоторых целей. Исчисление высказываний будем считать полным в широком смысле, если в ней доказуема каждая формула, являющаяся тавтологией. Иначе можно сказать, что исчисление высказываний называется полной в широком смысле теорией, если множество теорем покрывает множество формул, являющихся тавтологиями. Вводят, кроме того, понятие полноты в узком смысле. Исчисление высказываний называется полным в узком смысле, если присоединение к ее аксиомам какой-нибудь не выводимой в ней формулы приводит к противоречивой теории. Полнота в узком смысле означает, что аксиомы теории уже нельзя пополнить независимой аксиомой так, чтобы получить непротиворечивую теорию. Иначе можно сказать, что множество теорем Т такой теории еще не покрывает всего множества формул Ф (теория непротиворечива), но всякие попытки расширить множество Т приводят к тому, что Т покрывает все Ф, т.е. теория становится противоречивой. Покажем, что исчисление высказываний полно в широком смысле. Докажем сначала вспомогательную лемму. Лемма 4.3. Пусть А есть формула, а - пропозициональные буквы, входящие в и пусть задано некоторое распределение истинностных значений для Bi,B2 ,...,Bk. Пусть тогда В \ есть Bi , если Bi принимает значение И, и ]Bi, если Bi принимает значение Л, и пусть, наконец, А ' есть А, если при этом распределении А принимает значение И, и —А, если А принимает значение Л. Тогда В 'i,B '2,---,В 'k \-А'. Доказательство. Будем считать, что формула А записана без сокращений, т.е. без использования символов &, v, =. Доказательство проведем индукцией по числу («) вхождений в А примитивных связок (связок —1 и =^). Если и=0, то А представляет собой просто букву Bi и утверждение леммы сводится к очевидным утверждениям: Bi \-Вi и —Bi \ —\Bi. 116