Математическая логика и теория алгоритмов. Галуев Г.А. - 15 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 15 из 64
© 2003 Галуев Геннадий Анатольевич
Доказательство непротиворечивости исчисления высказываний будем искать в
следующих рассуждениях. Предположим, найдено некоторое свойство формул такое,
что
• Аксиомы обладают этим свойством
• При каждом применении правил вывода, если посылки обладают этим
свойством, то и заключение тоже
• Две формулы вида А и ⎤А не могут обе обладать этим свойством.
Тогда
в силу первых двух предположений каждая доказуемая формула обладает
этим свойством и в силу третьего предположения система оказывается непротиворе-
чивой.
Свойство формул, которое можно использовать, вытекает из логической интер-
претации исчисления высказываний (в рамках упоминавшейся выше теории моде-
лей), а именно: доказуемые пропозиционные формулы все оказываются тавтология-
ми, т.е. тождественно
истинными или общезначимыми формулами, которые всегда
принимают значение «истина» (1) при любом распределении значений истинности
составляющих их пропозиционных букв (в этом случае примитивные связки приобре-
тают смысл логических операций &, ∨ →, и т.д.)
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
о
о
н
н
е
е
п
п
р
р
о
о
т
т
и
и
в
в
о
о
р
р
е
е
ч
ч
и
и
в
в
о
о
с
с
т
т
и
и
.
. Для того, чтобы пропозиционная форма А
была доказуемой (или выводимой из тождественно истинных формул Г) в исчислении
высказываний необходимо, чтобы она была тождественно истинной, т.е. если ├А, то А
– тавтология.
Справедливость этой теоремы вытекает из
следующих лемм:
Лемма 1.
Пропозиционная формула, являющаяся аксиомой, тождественно истинна.
Для доказательства достаточно построить таблицы истинности для аксиом, полу-
ченных по схемам АК1, АК2, АК3.
Лемма 2.
Если при некотором применении правила вывода МР посылки А и А→В являются
тождественно истинными пропозиционными формами, то и заключение В является
тождественно истинной формулой.
Доказательство
. Рассмотрим таблицу истинности.
А В А А→В
В
1 1 1 1 1
1 0 1 0 0
0 1 0 1 1
0 0 0 1 0
Табл. 2
Видно, что единственная пара значений истинности А и В, дающая значение 1
обоим посылкам А и А→В это пара А=1, В=1. Эта пара даёт значение 1 и для заклю-
чения В=1.
Следствие. Исчисление высказываний непротиворечиво, т.е. ни для какой фор-
мулы А не имеют место одновременно А и ⎤
А.
Доказательство.
Допустим, что одна из формул А или ⎤А доказуема. Тогда, согласно теореме, эта
формула тавтология. С помощью таблицы истинности убеждаемся, что другая форму-
ла будет тождественно ложной и, следовательно, в силу теоремы недоказуемой.
Полнота.
Для доказательства полноты теории L надо показать, что каждая тавтология яв-
ляется теоремой теории L. Для доказательства этого факта в математической логике
сформулированы и доказаны следующие утверждения.
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
о
о
п
п
о
о
л
л
н
н
о
о
т
т
е
е
.
.
Если формула А теории L является тавтологией, то
она яв-
ляется теоремой теории L.

Страницы