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.^[1]

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š

Reference

^ Vidi Detlovs and Podnieks 1964

Literatura

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

[1] Vidi Detlovs and Podnieks 1964

[1]