LMF2012: Sintaxis y semántica de la lógica proposicional

En las dos últimas clases del curso Lógica matemática y fundamentos se ha completado el estudio de la sintaxis y la semántica de la lógica proposicional.

Se ha presentado la sintaxis de la lógica proposicional. Concretamente,

  • el lenguaje de la lógica proposicional,
  • la definición recursiva de las fórmulas proposicionales,
  • árboles de análisis de fórmulas,
  • definiciones por recursión sobre fórmulas y
  • demostraciones por inducción sobre fórmulas.

LEn la semántica, los conceptos definidos son los valores de verdad, las funciones de verdad, las interpretaciones, el valor de verdad de las fórmulas respectos de las interpretaciones, los modelos de fórmulas, la clasificación semántica de fórmulas (satisfacibles, insatisfacibles, tautologías, contradictorias y contigentes), los problemas SAT y TAUT. Finalmente, se han visto dos algoritmos para la solución de los problemas SAT y TAUT: tablas de verdad y método de Quine.

Otros conceptos definidos son equivalencia de fórmulas, modelos de conjuntos de fórmulas, conjuntos consistentes e inconsistentes y consecuencia lógica.

Se ha demostrado la equivalencia de los siguientes problemas

  1. decidir si una fórmula es consecuencia lógica de un conjunto finito de fórmulas,
  2. decidir si una fórmula es una tautología,
  3. decidir si una fórmula es insatisfacible y
  4. decidir si un conjunto de fórmulas es inconsistente.

Como aplicación se ha visto la decisión de la corrección de un argumento y la resolución de rompecabezas lógicos. En la solución del rompecabeza se ha explicado el uso del Gateway to Logic.

Las transparencias de estas clases son las del tema 1