30
§7 Dos metateoremas
Existen varios resultados potentes que permiten simplificar mucho las prue-
bas de la logica proposicional. En el sentido estricto no son teoremas del
CPC sino teorema sobre deducciones, o en particular, teoremas sobre teo-
remas (con precision, teoremas matematicos sobre teoremas del CPC). El
primer resultado de esta seccion codifica la practica matematica de “suponer
el antecedente y deducir el consecuente” cuando se quiere demostrar una
implicacion.
Teorema 7.1 (Teorema de la Deduccion). Sea Σ ⊆ F(L) un conjunto de
formulas, posiblemente vacıo, y sean α, β ∈ F(L) formulas.
Si Σ, α ` β entonces Σ ` α→ β.
Las referencias al teorema de la deduccion se abrevian TD. En realidad se
trata de una equivalencia, la otra implicacion es inmediata por MP.
Demostracion. Si β1, β2, β3, . . . , βn = β es una deduccion de β a partir de
Σ∪{α}, se demuestra por induccion (matematica completa) que Σ ` α→ βi
para cada i (1 ≤ i ≤ n). En particular, para i = n resulta Σ ` α→ β.
Paso inicial. La formula β1 no puede deducirse de formulas anteriores luego
es un axioma o una premisa. En el primer caso se tiene lo siguiente.
1. β1 Ax
2. β1 → (α→ β1) Ax 1
3. α→ β1 MP/1, 2
Ası α→ β1 es un teorema del CPC, luego tambien Σ ` α→ β1.
En el caso en que β1 es una premisa, de nuevo hay dos posibilidades. Si
β1 ∈ Σ entonces basta sustituir Ax por P en la deduccion anterior, y se
31
obtiene Σ ` α→ β1 de manera directa. Si β1 = α entonces α→ β1 = α→ α
que es un teorema por el ejemplo 5.5, de manera que de nuevo Σ ` α→ β1.
Paso inductivo. Sea k > 1 y supongase que Σ ` α → βi para cada i con
1 ≤ i < k. Si βk es un axioma o una premisa entonces Σ ` α → βk como
en el paso inicial. Si se obtiene por MP entonces existen formulas anteriores
de la forma βj, βj → βk y por hipotesis de induccion se tiene Σ ` α → βj,
Σ ` α → (βj → βk). Supongase que la primera deduccion requiere M pasos
y la segunda N −M pasos, entonces a la yuxtaposicion de las dos sucesiones
se anaden las lıneas siguientes.
N + 1. (α→ (βj → βk))→ ((α→ βj)→ (α→ βk)) Ax 2
N + 2. (α→ βj)→ (α→ βk) MP/N,N + 1
N + 3. α→ βk MP/M,N + 2
De esta manera Σ ` α→ βk.
La prueba anterior es constructiva porque dada una deduccion de β, siguien-
do en cada renglon los pasos de la demostracion es posible elaborar una
deduccion de α→ β.
El teorema de la deduccion, aplicado de manera reiterada, permite ver cual-
quier deduccion con finitas premisas como un teorema del CPC.
Corolario 7.2. Sean α1, α2, . . . , αn, β ∈ F(L) formulas.
α1, . . . , αn ` β si y solo si ` α1 → (α2 → · · · (αn → β) · · · ).
Ejemplo 7.3. ` (α→ β)→ ((β → γ)→ (α→ γ))
Demostracion. Por TD, basta probar α → β ` (β → γ) → (α → γ) y, de
nuevo por TD, basta probar α → β, β → γ ` α → γ. Este es el ejemplo
6.4, sin embargo ahora la prueba puede simplificarse porque, por TD, basta
probar α → β, β → γ, α ` γ. Esta deduccion se prueba de manera sencilla
con dos aplicaciones de MP.
32
Ejemplo 7.4. ` ¬¬α→ α
Demostracion. Se obtiene por TD del ejemplo 6.9.
Ejemplo 7.5. ` α→ ¬¬α
Demostracion.
1. (¬¬¬α→ ¬α)→ (α→ ¬¬α) Ax 3
2. ¬¬¬α→ ¬α Teo 7.4
3. α→ ¬¬α MP/1, 2
Ejemplo 7.6 (Doble Negacion II). α ` ¬¬α
Demostracion. Se obtiene por MP del ejemplo anterior (7.5).
Otro importante metateorema codifica el metodo de reduccion al absurdo
(RA), tan querido en la practica matematica.
Teorema 7.7 (Reduccion al Absurdo). Sea Σ ⊆ F(L) un conjunto de for-
mulas, posiblemente vacıo, y sea ϕ ∈ F(L) una formula.
Si Σ,¬ϕ ` α y Σ,¬ϕ ` ¬α para alguna α ∈ F(L), entonces Σ ` ϕ.
Demostracion. Si τ es cualquier teorema (o axioma) entonces por las dedu-
cciones 6.5 y 6.10 se tiene α,¬α ` ¬τ luego por hipotesis Σ,¬ϕ ` ¬τ y por
TD resulta Σ ` ¬ϕ→ ¬τ . Supongase que esta deduccion requiere N pasos,
entonces a ella se anaden las lıneas siguientes.
N + 1. (¬ϕ→ ¬τ)→ (τ → ϕ) Ax 3
N + 2. τ → ϕ MP/N,N + 1
N + 3. τ Teo
N + 4. ϕ MP/N + 2, N + 3
De esta manera Σ ` ϕ.
33
Corolario 7.8. Sea Σ ⊆ F(L) un conjunto de formulas y sean ϕ, α ∈ F(L)
formulas.
1. Si Σ, ϕ ` α,¬α entonces Σ ` ¬ϕ
2. Si Σ,¬ϕ ` ϕ entonces Σ ` ϕ
Ejemplo 7.9 (No Contradiccion). ` ¬(α ∧ ¬α)
Demostracion. Por RA (caso (1 ) del corolario 7.8) basta probar α ∧ ¬α `α,¬α, lo cual es consecuencia inmediata de los axiomas 4 y 5.
Ejemplo 7.10 (Modus Tollendo Tollens). α→ β,¬β ` ¬α
Demostracion. Por RA ((1 ) del corolario 7.8) basta probar α → β,¬β, α `β,¬β. La primera deduccion es inmediata por MP ; la segunda es mas in-
mediata aun porque la conclusion esta entre las premisas.
El ejemplo siguiente se obtiene aplicando dos veces TD a Tollendo Tollens,
y en cierto modo es un “complemento” del axioma 3.
Ejemplo 7.11. ` (α→ β)→ (¬β → ¬α)
Ejemplo 7.12. α→ β,¬α→ β ` β
Demostracion. Por RA ((2 ) del corolario 7.8) basta ver α→ β,¬α→ β,¬β `β.
1. α→ β P
2. ¬β P
3. ¬α Ded 7.10/1, 2
4. ¬α→ β P
4. β MP/3, 4
34
En esta presentacion, el camino para llegar al proximo teorema es bastante
dispendioso.
Ejemplo 7.13 (Tercero Excluıdo). ` α ∨ ¬α
Demostracion. Resulta de inmediato aplicando el ejemplo 7.12 a los axiomas
α→ (α ∨ ¬α) y ¬α→ (α ∨ ¬α).
Ejercicios.
7.1. Demuestre el siguiente teorema del CPC.
(α→ β) ∨ (β → γ)
[Sugerencia: Use el resultado 7.12.]
7.2. Demuestre:
a) ¬(α ∧ β) ` ¬α ∨ ¬β
b) ¬(α ∨ β) ` ¬α ∧ ¬β
c) ¬(α→ β) ` α ∧ ¬β
d) ¬α ∨ ¬β ` ¬(α ∧ β)
e) ¬α ∧ ¬β ` ¬(α ∨ β)
f) α ∧ ¬β ` ¬(α→ β)
7.3. A partir del ejercicio anterior concluya:
a) ¬α ∨ β ` α→ β b) α→ β ` ¬α ∨ β
7.4. Demuestre el razonamiento presentado como ejemplo en el §1 y al
comienzo de la seccion 1.2.
7.5. Demuestre:
a) α ∨ β ` (α→ β)→ β
b) α→ (β → γ) ` (α ∧ β)→ γ
c) (α→ β)→ β ` α ∨ β
d) (α ∧ β)→ γ ` α→ (β → γ)
35
7.6. Demuestre:
a) α→ β, γ → δ ` (β → γ)→ (α→ δ)
b) α→ β, γ → δ ` (α ∧ γ)→ (β ∧ δ)
7.7. Demuestre:
a) (α→ β) ∧ ¬γ ` α→ ¬(β → γ) b) ¬α, γ → ¬β ` γ → ¬(α ∨ β)
7.8. Demuestre que si α ` β entonces ¬β ` ¬α.
Recommended