Saltar al contenido
Topos Uranos
Español

Semántica de la lógica proposicional

Resumen

Hasta aquí las fórmulas han sido cadenas de círculos y discos, y las deducciones, manipulaciones de cadenas: nada se ha dicho de su verdad. Esta clase les da significado. Una valoración asigna a cada variable uno de los dos valores de verdad, 11 (verdadero) y 00 (falso), y se extiende a todas las fórmulas de un único modo, por recursión sobre su complejidad, con una sola cláusula: (φ↓ψ)(\varphi \downarrow \psi) vale 11 exactamente cuando φ\varphi y ψ\psi valen 00. De esa cláusula y de las abreviaturas oficiales se calculan, sin estipular nada más, los valores de la negación, la disyunción, la conjunción, la implicación, la doble implicación y la disyunción exclusiva. El lema de coincidencia, demostrado por inducción sobre la complejidad, asegura que el valor de una fórmula depende solo de los valores de sus variables; de él se sigue que la tabla de verdad, con 2n2^n filas para nn variables, contiene todo lo que las infinitas valoraciones pueden decir de la fórmula. Con ello se definen la satisfacción, la validez, la satisfacibilidad, la contradicción y la contingencia, se fijan las fórmulas ⊤\top y ⊥\bot, y se plantea el problema de decidir la validez, que las tablas resuelven a un costo que crece exponencialmente con el número de variables.

Objetivos de aprendizaje

  1. Calcular el valor de verdad de una fórmula bajo una valoración mediante su extensión recursiva, y deducir de las abreviaturas oficiales el valor de cada conector derivado.
  2. Demostrar por inducción sobre la complejidad el lema de coincidencia, y explicar con él por qué una tabla de verdad de 2n2^n filas basta para estudiar una fórmula con nn variables.
  3. Construir tablas de verdad columna por columna y clasificar fórmulas como válidas, contingentes o contradicciones, y conjuntos de fórmulas como satisfacibles o insatisfacibles, sin confundir ⊭φ\not\models \varphi con la contradicción.
  4. Decidir la validez de una fórmula buscando una valoración que la refute, y estimar el costo del método de las tablas en función del número de variables.

El significado de las fórmulas

La unidad sobre el lenguaje construyó, en la clase sobre el lenguaje de la lógica proposicional, un conjunto de cadenas de dos signos, y la unidad sobre la deducción enseñó a obtener unas cadenas de otras con axiomas y reglas. Ninguna de las dos habló de verdad: el sistema deductivo transforma signos según su forma, como una máquina que no entiende lo que escribe. Ahora bien, el lenguaje se construyó para representar enunciados, y la clase sobre la formalización del lenguaje natural les atribuyó lecturas informales: (φ↓ψ)(\varphi \downarrow \psi) es verdadera cuando φ\varphi y ψ\psi son ambas falsas, y las lecturas de los demás conectores se dedujeron de esta. La semántica convierte esas lecturas en definiciones matemáticas.

Dos decisiones la fundan. La primera es la bivalencia: hay exactamente dos valores de verdad, que se escriben 11 (verdadero) y 00 (falso), y cada fórmula, en cada situación, tiene uno de ellos. La segunda es la veritativo-funcionalidad: el valor de una fórmula compuesta depende solo de los valores de sus componentes, no de su asunto, de modo que la verdad de las variables decide la de todas las fórmulas. La clase sobre la formalización mostró el precio de esta segunda decisión (la causalidad, la modalidad y el tiempo quedan fuera); su recompensa es que la semántica de todo el lenguaje se obtiene de una sola cláusula, la del conector primitivo.

Conviene advertir, además, que esta unidad trabaja enteramente en el metalenguaje. Las afirmaciones «φ\varphi es verdadera bajo tal asignación» o «φ\varphi es una tautología» no son fórmulas, sino enunciados matemáticos sobre fórmulas, y se demuestran por razonamiento ordinario, a menudo por inducción sobre la complejidad; no son deducciones en el sistema del curso. La relación entre ambos mundos, que todo lo deducible es verdadero y que todo lo verdadero en el sentido preciso de esta unidad es deducible, es el asunto de la unidad de metateoría.