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
0 comentarios:
Publicar un comentario