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

Вводят, кроме того, понятие полноты в узком смысле. Исчисле­ ние высказываний называется полнымвузкомсмысле, если присоеди­ нение к ее аксиомам какой-нибудь, не выводимой в ней формулы, приводит к противоречивой теории. Полнота в узком смысле означает, что-аксиомы теории уясе нельзя пополнить независимой аксиомой так, чтобы получить непротиворечивую теорию. Иначе моясно сказать, что множество теорем Т такой теории еще не покрывает всего множества формул Ф (теория непротиворечива), но всякие попытки расширить множество Т приводят к тому, что Т покрывает все Ф, т.е. теория ста­ новится противоречивой. Покажем, что исчисление высказываний полно в широком смысле. Докажем сначала вспомогательную лемму. Л е м м а 4.3. Пусть А есть формула, а - пропози­ циональные буквы, входящие в и пусть задано некоторое распреде­ ление истинностных значений для Л Ь В ^-.-.- В А - Пусть тогда В', есть В,, если Bi принимает значение Я, и 1 В,, если В, принимает значение Л, и пусть, наконец, А ' есть А, если при этом распределении А при­ нимает значение И, н ~\ А, если А принимает значение Л. Тогда В\,В'ъ...,В\ УА'. Доказательство. Будем считать, что формула А записана без сокращений, т.е. без использования символов &, v, Доказательство проведем индукцией по числу (и) вхождений в Л примитивных связок (связок 1 и =>). Если «=0, то А представляет собой просто пропозициональную букву В\ и утверждение леммы сводится к очевидным утверждениям: b^ I-S, и15 , |-1S,. Допустим теперь, что лемма верна при любом ]<п. Случай 1. А имеет вид отрицания: 1 В. Число вхождений прими­ тивных связок в В, очевидно, меньше п. 160