4. Теорема дедукции

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

Теорема дедукции. Пусть Г – множество формул, А и В – формулы. Если Г, A├ _L B, то Г├ _L А→В и обратно.

Доказательство.Докажем эту теорему конструктивно, т.е. предложим алгоритм построения выводаГ├ _L А→В из имеющегося выводаГ, A├ _L B. ПустьE₁, …, E_nвыводВизГ, А,причемE_n=В. Покажем индукцией поi (1≤i≤n), чтоГ├ _L А→E_i..

1⁰i=1Покажем, чтоГ├ _L А→E₁.Возможны три случая.

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

   1	E1	аксиома
   2	E1 →(A→E1)	A1
   3	A→E1	MP 1,2

2. E₁ Г Тогда рассмотрим вывод

   1	E1	гипотеза
   2	E1 →(A→E1)	A1
   3	A→E1	MP1,2

3. E₁=А Тогда по правилу введения импликации имеемГ├ _L Е₁→E₁ илиГ├ _L А→E₁

2⁰Пусть теперьГ├ _L А→E_iдля всехi<k . Покажем, чтоГ├ _L А→E_к.Возможны четыре случая.

1. E_к –аксиома.

2. E_к Г

3. E_к=А

4. E_к получена по правилуmodusponensиз формулE_i E_j, i,j<k иE_j= E_i E_k

Для первых трех случаев доказательство аналогично случаю i=1. Для четвертого случая по индукционному предположению имеется выводГ├ _L А→E_iдля всехi<kи выводГ├ _L А→(E_i E_k)Достроим вывод.

n	(A (Ei  Ek))((А→Ei)( А→Ek))	A2: B←Ei;C←Ek
n+1	(А→Ei)( А→Ek)	MP j,n
n+2	A→Ek	MP i,n+1

Таким образом, Г├ _L А→E_kдля всехk.Приk=nполучаемГ├ _L А→E_n илиГ├ _L А→B.

В обратную стороны доказательство также конструктивное. Пусть имеется вывод Г├ _L А→В, состоящий изnформул. Достроив его следующим образом, получим выводГ, A├ _L B.

n	А→В
n+1	А	гипотеза
n+2	В	MPn,n+1

Следствие 1. Если A├ _L B, то ├ _L А→В и обратно.

Доказательство.Положим в теореме дедукции Г=.

Следствие 2.(Правило транзитивности) AB, BC ├ _L А→C

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

1	AB	гипотеза
2	BC	гипотеза
3	A	гипотеза
4	В	MP 3,1
5	С	MP 4,2
6	AB, BC, А ├ L C	1-5
7	AB, BC ├ L А→C	Теорема дедукции

Следствие 3.(Правило сечения) A(BC), В ├ _L А→C

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

1	A(BC)	гипотеза
2	A	гипотеза
3	BC	MP 2,1
4	В	гипотеза
5	С	MP 4,3
6	A(BC), В, А├ L C	1-5
7	A(BC), В├ L А→C	Теорема дедукции