DEDUCCION NATURAL

¿Que es?

es una aproximacion a la teoria a la demostracion  en la cual en vez de contar con unos pocos axiomas a los que se aplican unas pocas reglas de inferencia,la deduccion natural propone  vaciar la lista de axiomas y ampliar la de reglas de inferencia, introduciendo dos reglas para cada constante logica una para introducirla y otra para eliminarla,una demostracion se construye partiendo de supuestos y aplicando las reglas para llegar a la conclusion deseada

¿Para que sirve?

en la que se busca capturar la manera en que las personas razonan naturalmente al construir demostraciones matematicas.
La idea central de la deducción natural consiste en demostrar que una conclusión se deduce lógicamente de un conjunto de hipótesis, es decir, siguiendo una serie de pasos sucesivos, cada uno permitido por una regla; es posible alcanzar la conclusión deseada. Si es así, se ha demostrado que la conclusión es consecuencia lógica de las premisas dadas.

¿Como opera?

El primer paso de este proceso consiste en simbolizar nuestro enunciado e identificar nuestras hipótesis, así como la conclusión. Otra de las cosas que debemos recordar es que los puntos y seguidos dividen nuestras hipótesis y que el punto y aparte es el que divide a la conclusión de nuestras hipótesis, que además también puede estar señalada por signos de interrogación o por la frase “por tanto”. (El símbolo  representa la conclusión ya simbolizada).

EJERCICIOS

1.Ejercicio 1 Demostrar mediante deducción natural
 P(c),
 ∀x[P(x) → ¬Q(x)] `
 ¬Q(c)
 Solución:
1 P(c) Premisa
2 ∀x[P(x) → ¬Q(x)] Premisa
3 P(c) → Q(c)    E ∀ 2
4 Q(c)                E → 3, 1

2.Ejercicio 2 Demostrar mediante deducción natural
∀x[P(x) → ¬Q(x)],
∀xP(x) ` ∀x¬Q(x)
Solución:
1 ∀x[P(x) → ¬Q(x)] Premisa
2 ∀xP(x) Premisa
3 par´ametro x0    Supuesto
4 P(x0) → ¬Q(x0)     E ∀ 1, 3
5 P(x0)       E ∀ 2, 3
6 Q(x0)        E → 4, 5
7 ∀x¬Q(x)      I ∀ 3 − 6

3.Ejercicio 3 Demostrar mediante deducción natural
∀xP(x) `
∃xP(x)
Solución:
1 ∀xP(x) Premisa
2 P(x0)      E ∀ 1
3 ∃xP(x)    I ∃ 2

4.Ejercicio 4 Demostrar mediante deducción natural
∀x[P(x) → Q(x)],
∃xP(x) `
∃xQ(x)
Solución:
1 ∀x[P(x) → Q(x)] Premisa
2 ∃xP(x) Premisa
3 par´ametro x0, P(x0) Supuesto
4 P(x0) → Q(x0) E ∀ 1, 3
5 Q(x0) E → 4, 3
6 ∃xQ(x) I ∃ 5
7 ∃xQ(x) E ∃ 2, 3 − 6