Решение. Правило 1 – из гипотезы A и ввиду АA по (MP) AА

Правило 1 – из гипотезы A и ввиду АA по (MP) AА.

Правила 2 – 4 – тривиально допустимы. Вывод, обосновывающий секвенцию выше черты, обосновывает и секвенцию ниже черты;

Правило 5 – из B, AC по теореме о дедукции BАC. Отсюда и из Г А по правилу добавления Г, BАC; Г, BА. Применяя (MP), получим Г, BC.

Пример 3.5

Доказать логические правила техники естественного вывода в ИП (см. с. 59-60).

Решение

Приведем доказательства некоторых из правил (остальные доказываются аналогично).

- введение. Это есть в точности теорема о дедукции.

- удаление. Из данных выводов Г A, Г AB вывод для Г B получим с помощью (MP).

Ú- введение. Имеем: Г A. Кроме того, AA Ú B (это аксиома). По (MP) Г A Ú B.

Ú- удаление. Из данных Г, AC; Г, BC по теореме о дедукции Г AC и Г BC. Кроме того, (AC)((BC)(A Ú B C)) (это аксиома). Дважды применяя (MP), получим: Г A Ú BC. По закону тождества (и правилу добавления) Г, A Ú B A Ú B. По (MP) Г, A Ú BC.

- удаление. Из Г, A (y) C по теореме о дедукции следует, что Г A (y) C. По правилу обобщения Г y (A (y) C) (здесь существенно, что y не входит свободно в Г). Имеем аксиому y (A (y) C)( y (A (y) C)). По (MP) Г y A (y) C. Аналогично x A (x) y A (y). Отсюда Г, xA (x) yA (y). Следовательно, по (MP) Г, xA (x) C.

-введение. Из Г, A В и Г, BA по теореме о дедукции Г AB, Г BA, Г (AB)(BA), что и означает по определению эквивалентности Г AB.

Пример 3.6

Доказать в ИП, что A Ú B Ø(Ø A Ø B).

Решение

Согласно -введению достаточно установить A Ú B Ø(Ø A Ø B) и Ø(Ø A Ø B) A Ú B.

Начнем с первой секвенции. Слева у нее стоит дизъюнкция, поэтому, разбирая случаи согласно Ú- удалению, достаточно установить два факта:

A Ø(Ø A Ø B) и B Ø(Ø A Ø B).

Установим только первый, второй устанавливается симметрично. Для вывода отрицания Ø(Ø A Ø B) достаточно допустить Ø A Ø B и вывести противоречие, т.е. использовать Ø-введение. Противоречие будет состоять в выводе A и Ø A. Итак, для вывода A Ø(Ø A Ø B) с помощью Ø-введения достаточно установить: A,Ø A Ø BA и A,Ø A Ø B Ø A.

Первая секвенция выводима по закону тождества. Для вывода второй согласно -удалению достаточно показать: A,Ø A,Ø B Ø A, что также следует из закона тождества.

Теперь установим: Ø(Ø A Ø B) A Ú B. Здесь наше рассуждение будет косвенным. Согласно Ø-удалению достаточно установить: Ø(Ø A Ø B)

ØØ(A Ú B). А для этого согласно Ø-введению следует, допустив Ø(A Ú B), вывести противоречие.

Мы докажем:

Ø(Ø A Ø B),Ø(A Ú B) Ø(Ø A Ø B) и Ø(A Ú B)Ø A Ø B.

Первая секвенция, очевидно, выводима по закону тождества. Вторую секвенцию получим по -введению. Достаточно вывести:

Ø(A Ú B)Ø A и Ø(A Ú B)Ø B.

Мы выведем первую секвенцию, вторая выводится симметрично. Используя
Ø- введение, достаточно вывести:

Ø(A Ú B), A Ø(A Ú B) и Ø(A Ú B), A A Ú B.

Но первая из этих секвенций очевидна, а вторая получается с помощью
Ú-введения из Ø(A Ú B), A A.

Пример 3.7

Вывести A ÚØ A.

Дата добавления: 2014-01-06