Teorema dedukcije

U matematičkoj logici, teorema dedukcije glasi da ako se formula F može dedukovati iz E, onda se implikacija E → F može pokazati (to jest dedukovati iz praznog skupa). Simbolički napisano, ako $E\vdash F$, onda $\vdash E\rightarrow F.$

Teorema dedukcije se može uopštiti na bilo koji konačni niz formula-pretpostavki tako što se od

$E_{1},E_{2},...,E_{n-1},E_{n}\vdash F$, dobije $E_{1},E_{2},...,E_{n-1}\vdash E_{n}\rightarrow F$, i tako dalje dok se ne dobije

$\vdash E_{1}\rightarrow (...(E_{n-1}\rightarrow (E_{n}\rightarrow F))...)$.

Teorema dedukcije je metateorema: koristi se za dedukovanje dokaza u datoj teoriji mada sama nije teorema te teorije.

Dedukciona meta-teorema je jedna od najvažnijih meta-teorema. U nekim logičkim sistemima, uzima se kao pravilo izvođenja, pravilo koje uvodi "→". U drugim sistemima, dokazivanje ove teoreme iz aksioma je prvi veliki zadatak u dokazivanju da je logika kompletna. Obično je vrlo teško da se dokaže bilo šta u iskaznoj logici bez korišćenja metateoreme dedukcije, a to obično postane prilično lako ako ova metateorema može da se koristi.

Primeri dedukcije

Dokazati aksiomu 1:

• • P 1. hipoteza
    • Q 2. druga hipoteza
    • P 3. ponavljanje 1
  • Q→P 4. dedukcija iz 2 u 3
• P→(Q→P) 5. dedukcija iz 1 u 4, Q. E. D.

Dokazati aksiomu 2:

• • P→(Q→R) 1. hipoteza
    • P→Q 2. hipoteza
      • P 3. hipoteza
      • Q 4. modus ponens 3,2
      • Q→R 5. modus ponens 3,1
      • R 6. modus ponens 4,5
    • P→R 7. dedukcija iz 3 u 6
  • (P→Q)→(P→R) 8. dedukcija iz 2 u 7
• (P→(Q→R))→((P→Q)→(P→R)) 9. dedukcija iz 1 u 8, QED

Iskoristiti aksiomu 1 da se pokaže ((P→(Q→P))→R)→R:

• • (P→(Q→P))→R 1. hipoteza
  • P→(Q→P) 2. aksioma 1
  • R 3. modus ponens 2,1
• ((P→(Q→P))→R)→R 4. dedukcija iz 1 u 3, QED

Vidi još

• Iskazni račun
• Pirsov zakon

Literatura

• Uvod u matematičku logiku, Vilnis Detlovs i Karlis Podnieks Podnieks je sveobuhvatno uputstvo. Videti odeljak 1.5.