Completitud y solvencia en la lógica proposicional
RESUMEN
En esta clase se aborda la relación entre la completitud y la solvencia en la lógica proposicional. A pesar de que se han discutido ampliamente las técnicas de deducción y la semántica en la lógica proposicional, se ha prestado poca atención a la relación entre ambas facetas. La solvencia se refiere a la propiedad de un sistema lógico de inferir una expresión G a partir de un conjunto de expresiones Γ. Por otro lado, la completitud se refiere a la propiedad de un sistema lógico en el que, si G es consecuencia semántica de un conjunto de expresiones Γ, entonces existe una prueba formal con premisas Γ a partir de la cual se puede inferir G. Se demuestra que la lógica proposicional es solvente y completa, y se presenta una explicación detallada de cada propiedad. En particular, se muestra cómo la solvencia se deriva de la constitución del sistema deductivo de la lógica proposicional, y cómo la completitud se infiere de forma sencilla. Este análisis resulta de gran importancia para entender cómo funciona la lógica proposicional y para aplicarla de manera efectiva en diversos campos del conocimiento.
OBJETIVOS DE APRENDIZAJE:
Al finalizar esta clase, el estudiante será capaz de:
- Distinguir entre solvencia y completitud en un sistema lógico.
- Aplicar la tabla de verdad para los axiomas de Łukasiewicz para demostrar la solvencia de la lógica proposicional.
- Explicar la forma en que el modus ponens puede ser reescrito usando la versión semántica del teorema de deducción.
- Entender que la solvencia y la completitud están relacionadas y que se pueden inferir una de la otra.
- Analizar el concepto de tautología y su relación con los teoremas en la lógica proposicional.
ÍNDICE
COMPLETITUD Y SOLVENCIA EN LA LÓGICA PROPOSICIONAL
LA LÓGICA PROPOSICIONAL ES SOLVENTE
LA LÓGICA PROPOSICIONAL ES COMPLETA
Completitud y solvencia en la lógica proposicional
Llegados a este punto toca hablar de la completitud y la solvencia de la lógica proposicional. Ocurre que hasta ahora se ha hablado bastante sobre las técnicas de deducción y de la semántica de la lógica proposicional, pero todo se ha hecho de un modo en que pareciera que estas son dos facetas completamente independientes sin ninguna relación entre sí. La realidad es completamente opuesta.
SOLVENCIA: Por un lado se dice que un sistema lógico es solvente cuando, siempre que una expresión G se pueda inferir a partir de un conjunto de expresiones \Gamma, se tendrá que por lo tanto G es consecuencia (semántica) de \Gamma |
COMPLETITUD: Por otro lado, se dirá que es completo cuando, si G es consecuencia semántica un conjunto de expresiones \Gamma, entonces existe una prueba formal con premisas \Gamma a partir de la cual se puede inferir G. |
Revisando estas ideas veremos que la completitud y la solvencia se satisfacen para la lógica proposicional.
La lógica proposicional es solvente
Es sencillo obtener la solvencia de la lógica proposicional observando la constitución de su sistema deductivo. Si hacemos la tabla de verdad para los axiomas de Łukasiewicz veremos que estos tienen una estructura tal que siempre dan verdadero como valor de verdad, es decir:
| \models (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| \models ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))) |
| \models ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha \rightarrow \beta)) |
De forma similar, el modus ponens se puede reescribir de la forma \{\alpha,(\alpha\rightarrow \beta)\}\models \beta. lo que se puede obtener usando la versión semántica del teorema de deducción. De hecho, por éste medio tendremos que \{(\alpha\rightarrow \beta)\}\models (\alpha\rightarrow \beta), y luego \models ((\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \beta)), que por supuesto es una tautología más que evidente.
La lógica proposicional es completa
La completitud de la lógica proposicional nos dice que, si B es consecuencia semántica A, entonces a partir de A se infiere B. En otras palabras: todas las expresiones verdaderas tienen una demostración. Esto es lo que llamamos completitud. Esto se puede inferir de un modo sencillo.
Esto se puede inferir de un modo sencillo. Supongamos que a partir de A no se puede inferir B, o mejor dicho \neg(A\vdash B), por el teorema de deducción esto es equivalente a decir que: \neg (\vdash A\rightarrow B); ahora, si recurrimos a la solvencia, esto nos conduce a que \neg(\models A \rightarrow B), que por el reciproco del teorema de deducción (versión semántica) es equivalente a \neg(A\models B). En síntesis, lo que tenemos es que
\neg(A\vdash B) \Rightarrow \neg(A\models B)
Que es equivalente a decir
(A\models B) \Rightarrow (A\vdash B)
Esto quiere decir que, si A modela a B, entonces a partir de A se infiere B. Y si utilizamos los respectivos teoremas de deducción podemos obtener
(\models A\rightarrow B) \Rightarrow (\vdash A \rightarrow B)
Es decir: si una expresión es tautología, entonces es un teorema; y como hemos visto, los teoremas son el resultado de una demostración.