31. Вывод на основе противоречия.

Этот закон используется в теореме о полноте (снятия двойного отрицания). Некорректно исходить самой этой теоремы при доказательстве.

X|-~~X или |-X->~~X

Доказательство:

5. ~X,X|-X

6. ~X,X|-~X

7. По теореме опровержения гипотез, в которой в качестве отрицания выступает Х получаем: X|-~~X

8. По теореме дедукции |-X->~~X

Если в исчислении высказывания можно было доказать противоречие, то можно было бы доказать всЁ. Формально из X,~X|-Y.

Возьмем множество гипотез

3. X,~X,~Y|-X

4. X,~X,~Y |- ~X

Это случай описанный в лемме о снятии отрицания с гипотез. Получаем X,~X|-Y

Эта теорема устанавливает факт, что когда в целях убеждения аудитории используют противоречивые основания и гипотезы, в дальнейшем наукообразно можно вывести любой факт. Такое свойство отличает псевдонаучную теорию от научной. Целые системы, построенные на противоречивых посылках встречают в политике, экономике и т.д.

32. Независимость системы аксиом исчисления высказывания l.

Покажем, что ни одна аксиома не может быть выведено из остальных, используя правило вывода. Утверждение следует понимать, что ни один пример схемы аксиом не может быть получен из примеров других схем аксиом. Схемы аксиом: А1 нельзя вывести из А2 и А3.

Общий принцип доказательства: находится свойство, которым обладают все схемы, кроме выбранных. После чего показываем, что свойство сохраняется правилом вывода. Будем использовать специальную интерпретацию формул исчисления высказываний на основе трехзначной логики. Зададим таблицу истинности для логических связок:

А ~А

0. 1

1. 1

2. 0

А В A->B

0 0 0

1 0 2

2 0 0

По таблице показано, что схемы аксиом тождественно равны 0, что неверно для схемы аксиом А1. По таблице видно, что если А=0 и A->B=0 то и В=0. Следовательно свойство тождественного равенства 0 при такой интерпретации логических связок сохраняется правилом логического вывода. Следовательно схема аксиом А1 не зависит от схем аксиом А2 и А3. Для доказательства независимости А2 от А1 и А3 поступают аналогично, только используют другие таблицы логических связок.

А ~А

0 1

1 0

2 1

А В A->B

0 0 0

1 0 0

2 0 0

Для доказательства воспользуемся: введем специальный оператор h(F) где F- формула исчисления высказываний. Этот оператор устраняет все знаки отрицания из формулы F. Если применить оператор к схемам аксиом А1 и А2, то получаем тавтологию.

Покажем, что свойство формулы оставаться тавтологией после применения оператора h сохраняется правило МР, т.е. h(A->B)=h(A)->h(B). Если формула А тавтология и формула A->B тавтология, и, при этом, они остаются тавтологиями после применения оператора h, т.е. если h(A) h(A->B) то и h(B) тавтология. Покажем, что А3 не тавтология после применения h. h((~B->A)->((~B->A)->B)))=(B->A)->((B->A)->B) подставим в формулу в качестве В А. Получаем (A->A)->(A->A)->A получаем И->(И->A)=А в результате интерпретация формулы зависит от А. Так для схемы аксиом А3 не свойственно оставаться тавтологией после применения h. В результате доказали независимость всей системы аксиом.

Другие системы аксиом.

Система аксиом Гилберта и Акермана. Используются логические связки v, ~ и схемы аксиом:

1) (AvA)->A A->B=~AvB

2) (A->(AvA))

3) AvB->BvA

4) (B->C|-(AvB->AvC

33. Теорема|-F1&F2&..Fn->G:

Из множества формул F1..Fn |-G тогда и только тогда когда выводима |-F1&F2&..Fn->G. Если мы в рамках исчисления высказываний L то & считается сокращенной записью. A&B=~A->~B AvB=~A->B

Доказательство:

Проводим на основе теоремы дедукции. То что выводима G означает, что из множества формул F1,F2..Fn-1 |- Fn->G. В соответствии со следствием теоремы последовательно перенося за знак выводимости запишем: |-F1->(F2->..(Fn->G)..)*.

Нам нужно показать, что G выводима из F1..Fn тогда и только тогда, когда вторая часть условия теоремы тавтология. Воспользуемся эквивалентными преобразованиями. Формула * является тавтологией тогда и только тогда когда тавтологией является формула ~F1v(F2->..->(Fn->G)..) Последовательно раскрывая импликацию через дизъюнкцию получаем ~F1v~F2v..FnvG={По закону ДеМоргана}=~(F1&F2..Fn)vG=F1&F2&..Fn->G. Таким образом * является тавтологией, значит выводима тогда и только тогда, когда тавтологией является вторая часть условия теоремы, значитвыводима и 1-я часть условия теоремы.