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

Аналогичным образом доказываются пункты г) - ж). § 9. Два определения непротиворечивости Первое определение. Дедуктивная теория называется противоречивой (как уже определено), если ее множество теорем Т совпадает со всем множеством ее формул Ф (Т=Ф), и непротиворечивой в противном случае ((Т с^Ф) & (Т^Ф)). Второе определение. Дедуктивная теория называется противоречивой, если существует формула А такая, что в этой теории выводимо А и выводимо —i А\ если такой формулы не существует, то теория называется непротиворечивой. Теорема 4.2. Для теорий, содержащих исчисление высказываний, приведенные определения (не) противоречивости эквивалентны. Доказательство. Покажем, что из второго определения следует первое. Пусть существует формула^ такая, что выводима^ и —А\ Н (4.5) I—А. (4-6) В лемме 4.2 (в) доказано, что для любых формул АжВ имеет место: [ ^ ^ ( А ^ В ) . (4.7) Из (4.6) и (4.7) по MP получаем \-А^В, (4.8) а из (4.5) и (4.8) снова по MP имеем: |- В. Последнее и означает, что доказуема любая формула В, т.е. множество теорем совпадает с множество формул. Если примем первое определение, то в противоречивой теории доказуема любая формула, т.е. для любой формулы А получим, что А и —А являются теоремами, следовательно, теория противоречива согласно второму определению. § 10. Производные (доказуемые) правила вывода в исчислепии высказываний В исчислении высказываний (теории L) имеется только одно исходное правило вывода: modusponens {MP). При этом доказана теорема дедукции: если G,A\- В,то G \-А^В. Последнее представляет тоже некоторое правило вывода, но уже производное (доказуемое) правило, получающееся, если принять правило MP. Кроме этого производного правила вывода, оказывается, есть и другие. Рассмотрим некоторые из них. Пусть G - произвольное множество формул из L; А,В,С - произвольные формулы из L. Имеют место следующие производные правила вывода. 1. Правило перевертывания (контрапозиции) : если G,y4 \-В, то G, —iB \-^. Доказательство. 1) G/4 |- S - по условию; 113