Empecemos por el principio. La lógica proposicional es la más sencilla. El lenguaje está basado en proposiciones o enunciados declarativos que son enunciados que pueden evaluarse como ciertos o falsos. Normalmente, se emplean símbolos distintos p, q, r,… para cada enunciado y a partir de ellos se pueden generar expresiones más complejas con operadores lógicos de la forma habitual, usando \(\land, \lor, \neg, \to\). Por ejemplo, \((p \land q) \to (\neg r \lor q)\). Una fórmula bien formada (f.b.f.) se construye empleando exclusivamente las reglas siguientes:
- cualquier átomo \(p, q, r, \ldots\) es una f.b.f.
- si \(\phi\) es una f.b.f., también lo es \((\neg\phi)\)
- si \(\phi, \psi\) son f.b.f., también lo es \((\phi \land \psi )\)
- si \(\phi, \psi\) son f.b.f., también lo es \((\phi \lor \psi )\)
- si \(\phi, \psi\) son f.b.f., también lo es \((\phi \to \psi )\)
Otra forma de indicar estas reglas de construcción es usar una gramática BNF, de la forma
\(\phi ::= p \mid (\neg \phi) \mid (\phi \land \phi) \mid (\phi \lor \phi)\mid (\phi \to \phi)\)
La semántica de las expresiones anteriores viene dada por la tabla de verdad correspondiente, que examina el valor de verdad de la expresión \(\phi\) a partir de todas las combinaciones posibles de los valores de verdad de las proposiciones atómicas. Por ejemplo, para la expresión anterior \((p \land q) \to (\neg r \lor q)\), la tabla de verdad equivalente sería [table id=1 /]
Las reglas de deducción nos permiten construir sistemas de argumentación basados en la lógica, de modo que podemos llegar a una conclusión \(\psi\) (podemos deducir \(\psi\)) a partir de una serie de proposiones \(\phi_1, \phi_2,\ldots,\phi_n \). Lo representaremos como
\(\phi_1, \phi_2,\ldots,\phi_n \vdash \psi\)
Por otro lado, si además para todas las valuaciones en las que las proposiciones \(\phi_1, \phi_2,\ldots,\phi_n \) se evalúan a T, \(\psi\) también se evalúa a T, entonces se cumple
\(\phi_1, \phi_2,\ldots,\phi_n \models \psi\)
donde \(\models \) es la relación de equivalencia semántica. A partir de estos dos conceptos, deducción y equivalencia semántica, puede estudiarse la corrección (soundness) y la completitud (completeness) de la lógica proposicional. Suelen definirse a partir de estos teoremas
Teorema 1 (corrección). Sean \(\phi_1, \phi_2,\ldots,\phi_n\) y \(\psi \) fórmulas proposicionales. Si \(\phi_1, \phi_2,\ldots,\phi_n \vdash \psi\) es válido entonces se cumple \(\phi_1, \phi_2,\ldots,\phi_n \models \psi\).
Básicamente, el Teorema 1 quiere decir que todo aquello que se puede deducir a partir de las proposiciones utilizando las reglas de inferencia mantiene el valor de verdad de las proposiciones. O dicho de otra manera, todo lo que se puede deducir es cierto.
Teorema 2 (completitud). Sean \(\phi_1, \phi_2,\ldots,\phi_n\) y \(\psi \) fórmulas proposicionales. Si se cumple \(\phi_1, \phi_2,\ldots,\phi_n \models \psi\) entonces existe una prueba que permite deducir \(\phi_1, \phi_2,\ldots,\phi_n \vdash \psi\).
De la misma forma, el Teorema 2 quiere decir que si dos expresiones tienen el mismo valor de verdad, podríamos encontrar una argumentación que nos permita deducir una de la otra. O dicho de otra forma, todo lo que es cierto puede deducirse.