Lógica Matemática - Demostración en Lógica de Proposiciones

Una demostración de P es una secuencia de oraciones terminada con P.
Cada oración en la secuencia es o una hipótesis, o un axioma, o puede derivarse a partir de oraciones previas, vía una regla de inferencia.

Para entender en la teoria de demostracion de logica de proposiciones primero estudiamos el método indirecto de refutación (y los tableaux semánticos) y el método directo de la tablas de verdad como métodos semánticos para vericar la validez de fórmulas y deducciones. Sin embargo, si el número de proposiciones atómicas es elevado las tablas de verdad no son
un método eciente (para un signatura con n fórmulas atómicas, tenemos que construir una tablas de 2n las).

La teoría de la demostración o teoría de pruebas nos proporciona métodos alternativos a las tablas de verdad para averiguar
² la validez de una fórmula proposicional: si ' es una fórmula válida se dice que es demostrable y se escribe ` ':
² si una fórmula ' es consecuencia lógica de un conjunto de premisas ©: si ' es consecuencia lógica de © se dice que ' es
deducible en el sistema a partir de © y se escribe © ` ':

El objetivo principal de cualquier teoría de pruebas es demostrar la validez de fórmulas, independientemente del contexto particular que se estén considerando: la demostración de la validez de una fórmula o de una deducción en un sistema de demostración no se desarrolla teniendo en cuenta todas las posibles valoraciones, se obtiene utilizando una secuencia nita de pasos
y, en cada uno de ellos, se aplican las reglas de inferencia del sistema.

Ya comentamos que los sistemas de demostración se suelen dividir endos clases: sistemas directos y sistemas indirectos (o por refutación). Los primeros aplican una cadena nita de reglas de inferencia hasta llegar a la fórmula que se quiere demostrar. Los segundos aplican la técnica de reducción al absurdo.

Siendo sistemas clásicos, los sistemas de demostración directos tienen interés histórico y además son los más naturales ya que son los más cercanos a la forma de razonamiento habitual.
Los sistemas directos son adaptables a lógicas no clásicas, pero son de difícil automatización.
Lo sistemas de demostración indirectos son más modernos y adecuados para su automatización, pero no son aplicables a lógicas distintas de las lógicas clásicas.

En este capítulo estudiaremos un particular sistema de demostración axiomático, el sistema de deducción natural de Gentzen.
El método de los tableaux semánticos que estudiamos en la teoría interpretativa tiene, en realidad, una estructura completamente sintáctica y, por tanto, se puede considerar un ejemplo de sistemas de demostración axiomático indirecto.

Como veremos, es posible demostrar que estos sistemas axiomáticos son equivalentes a la teoría interpretativa. Es decir, se puede vericar que una fórmula proposicional es una tautología en la teoría interpretativa si y sólo si es una fórmula válida en la teoría de la demostración que vamos a estudiar.

Métodos de demostración.

Demostración por el método directo.

Supóngase que p → q es una tautología, en donde p y q pueden ser proposiciones compuestas, en las que intervengan cualquier número de variables propositvas, se dice que q se desprende lógicamente de p. Supóngase una implicación de la forma.

(p1 ∧ p2 ∧ …….∧ pn) ⇒ q
Es una tautología. Entonces está implicación es verdadera sin importar los valores de verdad de cualquiera de sus componentes. En este caso, se dice que q se desprende lógicamente de p1,p2,……,pn. Se escribe.
p1
p2
pn
_
∴ q
Realmente el camino que se debe seguir para llevar a cabo una demostración formal usando el método directo. Significa que sí se sabe que p1 es verdadera, p2 es verdadera,…… y pn también es verdadera, entonces se sabe que q es verdadera.
Prácticamente todos los teoremas matemáticos están compuestos por implicaciones de este tipo.
(p1 ∧ p2 ∧ …….∧ pn) ⇒ q
Donde la p1 son llamadas hipótesis o premisas, y q es llamada conclusión. “Demostrar el teorema”, es demostrar que la implicación es una tautología. Note que no estamos tratando de demostrar que q (la conclusión) es verdadera, sino solamente que q es verdadera si todas las p1 son verdaderas.
Toda demostración debe comenzar con las hipótesis, seguidas de las tautologías y reglas de inferencia necesarias, hasta llegar a la conclusión.
A continuación se prueba un enunciado en donde se puede apreciar el uso tanto de las tautologías como de las reglas de inferencia.
Sean
p: Trabajo.
q: Ahorro.
r: Compraré una casa.
s: Podré guardar el coche en mi casa.

Analizar el siguiente argumento:
“Si trabajo o ahorro, entonces compraré una casa. Si compro una casa, entonces podré guardar el coche en mi casa. Por consiguiente, si no puedo guardar el coche en mi casa, entonces no ahorro”.
El enunciado anterior se puede representar como:
p ∨ q → r; y r → s; entonces ¬s → ¬ q

Demostración por contradicción.

El procedimiento de la demostración por contradicción es semejante a la del método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.
Un ejemplo muy claro de este tipo de comprobación es el siguiente:



((p → q ) ∧ ¬q) → ¬p