Математическая логика и теория алгоритмов

1.4 Теорема дедукции

назад | оглавление | вперёд

 

       Дедукция – это процесс логического вывода, представляющий собой переход от посылок к заключениям, следствиям на основе применения правил логики. Основная теорема устанавливающая связь между импликацией и логическим выводом носит название теоремы дедукции. Ее суть состоит в следующем: если из посылок А выводимо по правилам логики некоторое заключение В, то импликация доказуема, т.е. выводима уже без всяких посылок (гипотез) из одних аксиом, которые являются логически истинными предложениями. Эта теорема имеет большое познавательное значение, поскольку в процессе дедукции позволяет вводить вспомогательные допущения (гипотезы), а затем освобождаться от них.

Теорема дедукции. Пусть Г – множество формул, А и В – формулы. Если , то и обратно.
Доказательство. Докажем эту теорему конструктивно, т.е. предложим алгоритм построения вывода из имеющегося вывода . Пусть вывод В из Г, А, причем En = В. Покажем индукцией по , что .
        10. i =1 Покажем, что . Возможны три случая:

  1. E1 - аксиома. Тогда следующий вывод доказывает необходимую выводимость.

    1.

    E1

    аксиома

    2.

    A1

    3.

    MP 1,2

  2. . Тогда рассмотрим вывод:

    1.

    E 1

    гипотеза

    2.

    A 1

    3.

    MP 1,2

  3. E 1. Тогда по правилу введения импликации имеем или
        20. Пусть теперь для всех i < k . Покажем, что . Возможны четыре случая:
  1. ;
  2. ;
  3. ;
  4. Eк получена по правилу modus ponens из формул и .
       Для первых трех случаев доказательство аналогично случаю i = 1. Для четвертого случая по индукционному предположению имеется вывод для всех i < k и вывод . Достроим вывод.
       
       Таким образом, для всех k . При k = n получаем или .
       В обратную сторону доказательство также конструктивное. Пусть имеется вывод , состоящий из n формул. Достроив его следующим образом, получим вывод .
       
       Теорема доказана.

Следствие 1. Если , то и обратно.
Доказательство. Положим в теореме дедукции .

       Следствие доказано.

Следствие 2 (Правило транзитивности). .
Доказательство.

1.

гипотеза

2.

гипотеза

3.

A

гипотеза

4.

В

MP 3,1

5.

С

MP 4,2

6.

пункты 1-5

7.

теорема дедукции

       Следствие доказано.

Следствие 3 (Правило сечения). .
Доказательство.

1.

гипотеза

2.

A

гипотеза

3.

MP 2,1

4.

В

гипотеза

5.

С

MP 4,3

6.

пункты 1-5

7.

теорема дедукции

       Следствие доказано.
назад | оглавление | вперёд