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

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

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

$E_{1},E_{2},...,E_{n-1},E_{n}\vdash F$, добије $E_{1},E_{2},...,E_{n-1}\vdash E_{n}\rightarrow F$, и тако даље док се не добије

$\vdash E_{1}\rightarrow (...(E_{n-1}\rightarrow (E_{n}\rightarrow 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.