DEDUCCIÓN NATURAL
La deducción natural es una aproximación a la teoría de la demostración en la que se busca capturar la manera en que las personas razonan naturalmente al construir demostraciones matemáticas. En vez de contar con unos pocos axiomas a los que se aplican unas pocas reglas de inferencia, la deducción natural propone vaciar la lista de axiomas y ampliar la de reglas de inferencia, introduciendo dos reglas para cada constante lógica: una para introducirla y otra para eliminarla. Una demostración se construye partiendo de supuestos y aplicando las reglas para llegar a la conclusión deseada
¿PARA QUE SIRVE?
La deducción natural sirve para intentar demostrar que un razonamiento es correcto (``para comprobar la validez de un secuente'', dice la teoría). Ejemplo:
Yo te digo: ``En verano hace calor, y ahora estamos en verano, por eso hace calor''. Tú te pones a hacer cálculos, y respondes ``Vale, puedo demostrar que el razonamiento que has hecho es correcto''. Para eso sirve la deducción natural.
No siempre es tan fácil: ``si suspendes una asignatura, la tienes que repetir. Si no estudias, la suspendes. Supongamos que no la repites. Entonces, o la estudias, o la suspendes, o las dos cosas a la vez''. Este razonamiento es válido y se puede demostrar con la deducción natural.
Fíjate que no tienes que creerte ni entender lo que te cuente. Por ejemplo, yo te digo: ``Los tiristores son pequeños y divertidos; un garbanzo no es pequeño, así que no es un tiristor''. Aunque no sepas de qué hablo o te parezca que es mentira o es una idiotez (que lo es), tienes que estar totalmente seguro de que el razonamiento es correcto.
O sea, que, dada una suposición ``si pasa esto entonces pasa esto otro'', la deducción natural permite decir ``sí, así es''. En lenguaje lógico: si te dan un secuente ATB puedes acabar concluyendo que es l= (válido). Entonces se escribe Al=B (A tiene como consecuencia a B).
¿COMO OPERA?
Se pide demostrar la validez de T l- S donde T (se lee gamma) es un grupo de fórmulas separadas por comas, y S es una sola fórmula.
Partimos de que todas las fórmulas de T son ciertas, y, mediante 9 reglas concretas, podemos ir descubriendo qué más cosas son ciertas. Nuestra intención es ver que S es cierta; una vez conseguido ya podemos acabar.
A veces no podremos sacar verdades de ningún lado, y habrá que hacer suposiciones: ``bueno, no estoy seguro de que A ∧B sea cierto siempre, pero si se cumple C, seguro que lo es''. Entonces ya hemos descubierto otra cosa cierta: que C ⇒A ∧B.
Como ves, siempre hay que pensar hacia dónde queremos llegar, porque de otra forma podríamos adivinar un montón de cosas que son ciertas pero que no nos están pidiendo. Por ejemplo, con A ∨B, ¬Al- B tenemos que llegar a que es cierto B. Podemos descubrir que
¬(A ∧ B), A ∨ B ∨ C, (A ∨ B) ⇒¬A, y muchas más cosas, pero lo que nos interesa es B y ya está. O sea, que si no vas por el camino correcto, te puedes hacer un lío.
EJEMPLOS:
Ejemplo 1
Demostrar mediante deducción natural
P(c),
∀x[P(x) → ¬Q(x)]
l- ¬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
Ejemplo 2
Demostrar mediante deducción natural
∀x[P(x) → ¬Q(x)],
∀xP(x)
l-∀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
Ejemplo 3
Demostrar mediante deducción natural
∀xP(x)
l-∃xP(x)
Solución:
1 ∀xP(x) Premisa
2 P(x0) E ∀ 1
3 ∃xP(x) I ∃ 2
o 
o dentro del dominio de un 
o 
. Cualquier otro tipo de ocurrencia de una variable es una ocurrencia libre.
es una proposición; sino es una forma proposicional.
En los enteros para todo x existe algún y talque x+y=5. Verdadero.
Existe algún y talque para cualquier x x+y=5. Falso 
