Математическая логика и теория алгоритмов
|
1.4 Теорема дедукции |
назад | оглавление | вперёд |
       Дедукция
– это процесс логического вывода, представляющий собой переход
от посылок к заключениям, следствиям на основе применения правил
логики. Основная теорема устанавливающая связь между импликацией и
логическим выводом носит название теоремы дедукции. Ее суть состоит в
следующем: если из посылок А выводимо по правилам логики
некоторое заключение В, то импликация доказуема, т.е. выводима уже без всяких посылок (гипотез) из
одних аксиом, которые являются логически истинными предложениями. Эта
теорема имеет большое познавательное значение, поскольку в процессе
дедукции позволяет вводить вспомогательные допущения (гипотезы), а
затем освобождаться от них.
Теорема
дедукции. Пусть Г – множество формул, А и В –
формулы. Если , то
и обратно.
Доказательство. Докажем эту
теорему конструктивно, т.е. предложим алгоритм построения вывода
из имеющегося вывода
.
Пусть
вывод В из Г, А, причем En = В.
Покажем индукцией по
,
что
.
        10. i =1
Покажем, что .
Возможны три случая:
1. |
E1 |
|
2. |
![]() |
|
3. |
![]() |
MP 1,2 |
1. |
E 1 |
|
2. |
![]() |
A 1 |
3. |
![]() |
MP 1,2 |
1. |
|
гипотеза |
2. |
|
гипотеза |
3. |
A |
гипотеза |
4. |
В |
MP 3,1 |
5. |
С |
MP 4,2 |
6. |
|
пункты 1-5 |
7. |
|
теорема дедукции |
1. |
|
гипотеза |
2. |
A |
гипотеза |
3. |
|
MP 2,1 |
4. |
В |
гипотеза |
5. |
С |
MP 4,3 |
6. |
|
пункты 1-5 |
7. |
|
теорема дедукции |