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

Из Википедије, слободне енциклопедије

У математичкој логици, теорема дедукције гласи да ако се формула 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]

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

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

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

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

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

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

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

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

Види још[уреди]

Референце[уреди]

  1. ^ Види Detlovs and Podnieks 1964

Литература[уреди]