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

Случай 2в. В принимает значение И, С принимает значение Л. Тогда А принимает значение Л, следовательно, А ' = —А, В' есть В, А С есть —iC. Таким образом, из (4.12) и (4.13) получим соответственно B'I,B'2,...,B'K B'J,B'2,...,B'K - в, (4.19) -^С. (4.20) По п. е) леммы 4.2 имеем: УВ ^ ( ^ с ^ -п(В^)). (4.21) Из (4.19) и (4.21) ПОMP следует в'ьВ-2 В\[ - , С = > ( 4 . 2 2 ) а ИЗ (4.20) и (4.22) по MP следует в 'i.B 2 в 'i- h -^(в^:). Последнее является требуемым, ибо —^(В^>С) естьАЛемма доказана. Теорема 4.5 (о полноте). Если формула А теории L является тавтологией, то она является теоремой теории L Доказательство. Предположим, что А есть тавтология и Bi,B2,...,Bk - пропозициональные буквы, входящие в А. При каждом распределении истинностных значений для букв Bi,B2,...,Bk имеем в силу леммы 4.3: B'],B'2,...,B'k \- А (А' совпадает с А, так как А всегда принимает значение И). Поэтому в случае, когда Bk принимает значение И, получим B'],B'2,...,B'K.],BK \-А , а когда В^ принимает значение Л, имеем: В'I,B'2,...,B\.I, -NBK\-A. Отсюда по теореме дедукции получим соответственно: В-,,В'2 в г, [Bt^A, (4.23) В'ьВ'2,...,Вк-1 (4.24) По лемме 4.2(ж) имеем: |- (BK^A) =^((^BK^A) =^А). (4.25) Теперь ПОMP из (4.23) и (4.25) получим В-,,В'2 в\., \-(^Bt^A)^A. (4.26) Далее снова по MP из (4.26) и (4.24) следует В-,.В-2 В'ы Ы- Таким образом, из B'i.B'2 В\ \-А получили B'i,B'2 B'f^.i [- А, т.е. ИСКЛЮЧИЛИ B'k. Точно также исключим B'k -i и так далее, после к таких шагов придем к \-А т.е. А является теоремой, что и требовалось доказать. Можно доказать и полноту в узком смысле, см., например, [8]. Примем без доказательства. Независимость аксиом. Отдельная аксиома дедуктивной теории, в том числе и исчисления высказываний, является независимой, если эту аксиому 118