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

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

Определение 1:

Формула β выводима из формул α₁, α₂,..., α_n, если формулу β можно вывести путем правила заключения, приняв за исходные формулы α₁, α₂,..., α_n и все истинные в исчислении высказываний формулы.

Определение 2:

β выводима из формул α₁, α₂,..., α_n если:

1) каждая формула α_i(1≤i≤n) выводима из формул α₁, α₂,..., α_n;

2) каждая выводимая в исчислении высказываний формула выводима из формул α₁, α₂,..., α_n;

3) если формула α и α→β выводима из формул α₁, α₂,..., α_n, то формула β также выводима из α₁, α₂,..., α_n.

β выводима из α₁, α₂,..., α_n будем обозначать α₁, α₂,..., α_n├β, если α_i нет, то ├β (просто выводимая формула).

Замечание:

Если α₁, α₂,..., α_n является аксиомами или другими выводимыми формулами, то класс выводимых формул совпадает с классом всех выводимых в исчислении высказываний формул, так как всякая выводимая формула считается выводимой из любой системы формул.

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

Если формула β выводима из формул α₁, α₂,..., α_n, то α₁→(α₂→(...(α_n→β)...)) – выводимая формула.

.

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

Сначала докажем, что если α₁, α₂,..., α_n├β, то α₁, α₂,..., α_n-1├α_n→β.

Доказательство этого утверждения проведем по индукции следующим образом. Сначала докажем, что оно верно, если β является одной из формул α_i. Затем покажем, что если утверждение верно для формул β′ и β′→β″, то оно верно и для β″.

Итак, если β одна из формул α_i, то либо i=n, либо i<n. В первом случае α_n→α_n – выводимая формула; она получается подстановкой в теорему 2.

Поэтому α₁, α₂,..., α_n-1├α_n→α_n.

Во втором случае α_n→α_i – выводимая формула:

1. - подстановка в аксиому А1;

2. ├α_i – по определению;

3. ├α_n→α_i – по правилу заключения к шагам 1 и 2.

Поэтому α₁, α₂,..., α_n-1├α_n→α_i.

Допустим теперь, что формулы α_n→β′ и α_n→(β′→β″) выводимы из α₁, α₂,..., α_n-1.

1. (A→(B→C))→((A→B)→(A→C))≡(α_n→(β′→β″))→((α_n→β′)→(α_n→β′′));

2. ├α_n→(β′→β″) и ├α_n→β′ по условию;

3. ├ α_n→β′′ - по правилу заключения к шагам 1 и 2.

Поэтому α₁, α₂,..., α_n-1├α_n→β′′.

Таким образом мы доказали, что если

α₁, α₂,..., α_n├β,

то

α₁, α₂,..., α_n-1├α_n→β.

Теперь установим справедливость теоремы дедукции. Допустим, что имеет место

1. α₁, α₂,..., α_n├β.

В таком случае будем иметь

2. α₁, α₂,..., α_n-1├ α_n→β.

Применив то же самое вторично, получим

3. α₁, α₂,..., α_n-2├ α_n-1→ (α_n→β).

Рассуждая так же и далее, наконец, получим

n-1. α₁ ├ α₂→(α₃→(...(α_n→β)...)).

Применив то же рассуждение еще раз, получим

n. ├ (α₁→(α₂→(α₃→(...(α_n→β)...)),

чем и доказана теорема дедукции.