LMF2014: Sintaxis y semántica de la lógica proposicional
En la clase de hoy del curso Lógica matemática y fundamentos se ha estudiado 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.
En 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 contingentes), 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
- decidir si una fórmula es consecuencia lógica de un conjunto finito de fórmulas,
- decidir si una fórmula es una tautología,
- decidir si una fórmula es insatisfacible y
- 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 rompecabezas se ha explicado el uso del Gateway to Logic.
Las transparencias de estas clases son las del tema 1
Read More “LMF2014: Sintaxis y semántica de la lógica proposicional”