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

У математичкој логици, теорема дедукције гласи да ако се формула -{F}- може дедуковати из -{E}-, онда се импликација -{E → F}- може показати (то јест дедуковати из празног скупа). Симболички написано, ако $E⊢F$, онда $⊢E\to F.$

Теорема дедукције се може уопштити на било који коначни низ формула-претпоставки тако што се од

$E_1,E_2,...,E_{n-1},E_n⊢F$, добије $E_1,E_2,...,E_{n-1}⊢E_n\to F$, и тако даље док се не добије

$⊢E_1\to (...(E_{n-1}\to (E_n\to F))...)$.

Теорема дедукције је метатеорема: користи се за дедуковање доказа у датој теорији мада сама није теорема те теорије.

Дедукциона мета-теорема је једна од најважнијих мета-теорема. У неким логичким системима, узима се као правило извођења, правило које уводи "→". У другим системима, доказивање ове теореме из аксиома је први велики задатак у доказивању да је логика комплетна. Обично је врло тешко да се докаже било шта у исказној логици без коришћења метатеореме дедукције, а то обично постане прилично лако ако ова метатеорема може да се користи.

Примери дедукције

Доказати аксиому 1:

• • -{P}- 1. хипотеза
    • -{Q}- 2. друга хипотеза
    • -{P}- 3. понављање 1
  • -{Q→P}- 4. дедукција из 2 у 3
• -{P→(Q→P)}- 5. дедукција из 1 у 4, -{Q. E. D.}-

Доказати аксиому 2:

• • -{P→(Q→R)}- 1. хипотеза
    • -{P→Q}- 2. хипотеза
      • -{P}- 3. хипотеза
      • -{Q}- 4. модус поненс 3,2
      • -{Q→R}- 5. модус поненс 3,1
      • -{R}- 6. модус поненс 4,5
    • -{P→R}- 7. дедукција из 3 у 6
  • -{(P→Q)→(P→R)}- 8. дедукција из 2 у 7
• -{(P→(Q→R))→((P→Q)→(P→R))}- 9. дедукција из 1 у 8, -{QED}-

Искористити аксиому 1 да се покаже -{((P→(Q→P))→R)→R}-:

• • -{(P→(Q→P))→R}- 1. хипотеза
  • -{P→(Q→P)}- 2. аксиома 1
  • -{R}- 3. модус поненс 2,1
• -{((P→(Q→P))→R)→R}- 4. дедукција из 1 у 3, -{QED}-

Види још

• Исказни рачун
• Пирсов закон

Литература

• Увод у математичку логику, Вилнис Детловс и Карлис Подниекс Подниекс је свеобухватно упутство. Видети одељак 1.5.