La lógica proposicional (también llamada cálculo proposicional o lógica de enunciados) constituye el nivel fundamental de la lógica matemática y proporciona el aparato formal necesario para el análisis riguroso del razonamiento deductivo. Estudia las proposiciones, esto es, los enunciados declarativos a los que se puede asociar de manera unívoca un valor de verdad, así como sus combinaciones mediante conectivas lógicas.
En esta exposición se ofrece un tratamiento sistemático y completo: lenguaje formal, sintaxis, semántica veritativo-funcional, equivalencias y leyes fundamentales, tautologías y consecuencia lógica, formas normales, sistemas deductivos y los teoremas metalógicos de corrección y completitud.
Índice
- Proposiciones y lenguaje formal
- Sintaxis de las fórmulas bien formadas
- Semántica e interpretaciones
- Conectivas lógicas y completitud funcional
- Tablas de verdad
- Equivalencias lógicas
- Leyes fundamentales
- Tautologías, satisfacibilidad y consecuencia lógica
- Formas normales (FNC y FND)
- Sistemas deductivos
- Corrección y completitud
- Ejemplos avanzados
Proposiciones y lenguaje formal
Una proposición (o enunciado) es una oración declarativa con sentido completo que, en virtud del principio de bivalencia, toma de manera unívoca uno y solo uno de los dos valores de verdad: verdadero (\(V\) o \(1\)) o falso (\(F\) o \(0\)).
Una proposición se dice atómica (o enunciado simple) si no contiene en su interior otras proposiciones conectadas mediante operadores lógicos. Las proposiciones obtenidas combinando proposiciones atómicas mediante conectivas lógicas se denominan compuestas (o moleculares).
Se fija un conjunto numerable de variables proposicionales, denotadas habitualmente con letras latinas minúsculas:
\[ \mathcal{P} = \{p_1, p_2, p_3, \dots\} = \{p, q, r, \dots\} \]
El lenguaje de la lógica proposicional \(\mathcal{L}\) consta de los siguientes símbolos:
- las variables proposicionales de \(\mathcal{P}\);
- las conectivas lógicas: \(\neg,\ \land,\ \lor,\ \rightarrow,\ \leftrightarrow\);
- los símbolos auxiliares: paréntesis \((,\ )\).
Sintaxis de las fórmulas bien formadas
El conjunto \(\mathcal{F}\) de las fórmulas bien formadas (fbf) es el menor conjunto de cadenas sobre el alfabeto de \(\mathcal{L}\) definido inductivamente mediante las siguientes cláusulas:
- Cláusula base: toda variable proposicional \(p \in \mathcal{P}\) es una fbf;
- Cláusulas inductivas:
- si \(A \in \mathcal{F}\), entonces \((\neg A) \in \mathcal{F}\);
- si \(A, B \in \mathcal{F}\), entonces \((A \land B),\ (A \lor B),\ (A \rightarrow B),\ (A \leftrightarrow B) \in \mathcal{F}\);
- Cláusula de cierre: ninguna otra cadena es una fbf.
En notación BNF, la gramática del lenguaje se escribe:
\[ A ::= p \mid (\neg A) \mid (A \land A) \mid (A \lor A) \mid (A \rightarrow A) \mid (A \leftrightarrow A) \]
Por convención de precedencia, se atribuye a las conectivas el siguiente orden decreciente de fuerza de ligadura, lo que permite omitir paréntesis sin ambigüedad:
\[ \neg \;>\; \land \;>\; \lor \;>\; \rightarrow \;>\; \leftrightarrow \]
Advertencia. Si bien la precedencia de \(\neg\) sobre todas las demás conectivas, así como la menor precedencia de \(\rightarrow\) y \(\leftrightarrow\), gozan de aceptación universal, el orden relativo de \(\land\) y \(\lor\) no es uniforme en la literatura: algunos autores (por analogía con \(\cdot\) y \(+\) en el álgebra de Boole) atribuyen a \(\land\) mayor precedencia que a \(\lor\), mientras que otros (por ejemplo, Mendelson) los sitúan en el mismo nivel y exigen paréntesis explícitos. Es por tanto buena práctica, ante cualquier posible ambigüedad, explicitar los paréntesis entre \(\land\) y \(\lor\): se escribirá, por ejemplo, \( (A \land B) \lor C \) en lugar de \( A \land B \lor C \).
El principio de inducción estructural sobre las fbf afirma que, para demostrar una propiedad \(P\) para toda \(A \in \mathcal{F}\), basta con probar:
- (caso base) \(P\) se cumple para toda proposición atómica;
- (paso inductivo) \(P\) se preserva bajo la aplicación de cada conectiva.
Semántica e interpretaciones
La semántica de la lógica proposicional es veritativo-funcional: el valor de verdad de una fórmula compuesta queda unívocamente determinado por los valores de verdad de sus subfórmulas.
Una interpretación (o valuación, o asignación de valores de verdad) es una función:
\[ v : \mathcal{P} \to \{V, F\} \]
que se extiende de manera única a una función \(\hat{v} : \mathcal{F} \to \{V, F\}\) mediante las siguientes cláusulas recursivas:
- \( \hat{v}(\neg A) = V \iff \hat{v}(A) = F \);
- \( \hat{v}(A \land B) = V \iff \hat{v}(A) = V \text{ y } \hat{v}(B) = V \);
- \( \hat{v}(A \lor B) = V \iff \hat{v}(A) = V \text{ o } \hat{v}(B) = V \) (eventualmente ambos);
- \( \hat{v}(A \rightarrow B) = F \iff \hat{v}(A) = V \text{ y } \hat{v}(B) = F \);
- \( \hat{v}(A \leftrightarrow B) = V \iff \hat{v}(A) = \hat{v}(B) \).
Si una fórmula contiene \(n\) variables proposicionales distintas, el número de interpretaciones posibles (restringidas a dichas variables) es \(2^n\).
Observación importante. La conectiva \(\lor\) representa la disyunción inclusiva (correspondiente al vel latino): \(A \lor B\) es verdadera siempre que al menos una de las dos proposiciones lo sea, incluido el caso en que ambas sean verdaderas. Debe distinguirse de la disyunción exclusiva (correspondiente al aut latino, denotada \(\oplus\) o XOR), donde \(A \oplus B\) es verdadera si y solo si \(A\) y \(B\) tienen valores de verdad diferentes. En símbolos:
\[ A \oplus B \;\equiv\; (A \lor B) \land \neg(A \land B) \;\equiv\; \neg(A \leftrightarrow B) \]
En el lenguaje natural castellano la conjunción «o» resulta ambigua entre ambos significados; la lógica formal elimina dicha ambigüedad adoptando por defecto la lectura inclusiva.
Conectivas lógicas y completitud funcional
Las conectivas lógicas son operadores veritativo-funcionales, es decir, funciones \(\{V,F\}^n \to \{V,F\}\):
- la negación \(\neg\) es un operador unario;
- la conjunción \(\land\), la disyunción \(\lor\), el condicional (o implicación) \(\rightarrow\) y el bicondicional \(\leftrightarrow\) son operadores binarios.
Un conjunto de conectivas se dice funcionalmente completo (o adecuado) si toda función de verdad \(\{V,F\}^n \to \{V,F\}\) puede expresarse mediante combinaciones de tales conectivas. Son funcionalmente completos, por ejemplo:
\[ \{\neg, \land, \lor\}, \quad \{\neg, \land\}, \quad \{\neg, \lor\}, \quad \{\neg, \rightarrow\} \]
Existen, además, conectivas binarias funcionalmente completas por sí solas: la barra de Sheffer (NAND), denotada \(\uparrow\), y la flecha de Peirce (NOR), denotada \(\downarrow\).
Las definiciones semánticas justifican las siguientes reducciones, que muestran que \(\rightarrow\) y \(\leftrightarrow\) son definibles a partir de \(\{\neg, \land, \lor\}\):
\[ A \rightarrow B \equiv \neg A \lor B \]
\[ A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A) \equiv (A \land B) \lor (\neg A \land \neg B) \]
Tablas de verdad
Una tabla de verdad es la representación tabular de la función veritativo-funcional asociada a una fórmula. Para una fórmula con \(n\) variables distintas, la tabla consta de \(2^n\) filas, una para cada interpretación posible.
Las tablas de verdad de las conectivas fundamentales son:
| \(A\) | \(B\) | \(\neg A\) | \(A \land B\) | \(A \lor B\) | \(A \rightarrow B\) | \(A \leftrightarrow B\) |
|---|---|---|---|---|---|---|
| V | V | F | V | V | V | V |
| V | F | F | F | V | F | F |
| F | V | V | F | V | V | F |
| F | F | V | F | F | V | V |
Obsérvese que el condicional \(A \rightarrow B\) resulta falso únicamente cuando el antecedente \(A\) es verdadero y el consecuente \(B\) falso: esa es la única fila en que adopta el valor \(F\).
Equivalencias lógicas
Dos fórmulas \(A\) y \(B\) se dicen lógicamente equivalentes, lo que se denota \(A \equiv B\), si toman el mismo valor de verdad en toda interpretación:
\[ A \equiv B \iff \forall v,\ \hat{v}(A) = \hat{v}(B) \]
La relación \(\equiv\) es una relación de equivalencia sobre \(\mathcal{F}\) (reflexiva, simétrica, transitiva) y, además, una congruencia: el teorema de sustitución establece que si \(A \equiv B\) y \(C[A]\) es una fórmula que contiene a \(A\) como subfórmula, entonces \(C[A] \equiv C[B]\), donde \(C[B]\) se obtiene reemplazando (una ocurrencia de) \(A\) por \(B\) en \(C\).
Resulta esencial distinguir \(\equiv\) (relación metalingüística entre fórmulas) de \(\leftrightarrow\) (conectiva del lenguaje objeto); en efecto,
\[ A \equiv B \iff \models A \leftrightarrow B \]
es decir, \(A\) y \(B\) son lógicamente equivalentes si y solo si \(A \leftrightarrow B\) es una tautología.
Leyes fundamentales
Las siguientes equivalencias, todas demostrables mediante tablas de verdad, constituyen las leyes fundamentales del cálculo proposicional (donde \(\top\) denota una tautología cualquiera y \(\bot\) una contradicción):
- Idempotencia: \(A \land A \equiv A\), \(\quad A \lor A \equiv A\)
- Conmutatividad: \(A \land B \equiv B \land A\), \(\quad A \lor B \equiv B \lor A\)
- Asociatividad: \((A \land B) \land C \equiv A \land (B \land C)\), y análogamente para \(\lor\)
- Distributividad: \(A \land (B \lor C) \equiv (A \land B) \lor (A \land C)\), \(\quad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)
- Doble negación: \(\neg \neg A \equiv A\)
- Leyes de De Morgan: \(\neg(A \land B) \equiv \neg A \lor \neg B\), \(\quad \neg(A \lor B) \equiv \neg A \land \neg B\)
- Absorción: \(A \land (A \lor B) \equiv A\), \(\quad A \lor (A \land B) \equiv A\)
- Elemento neutro: \(A \land \top \equiv A\), \(\quad A \lor \bot \equiv A\)
- Elemento absorbente: \(A \lor \top \equiv \top\), \(\quad A \land \bot \equiv \bot\)
- Tercero excluido: \(A \lor \neg A \equiv \top\)
- No contradicción: \(A \land \neg A \equiv \bot\)
- Contraposición (contrarrecíproca): \(A \rightarrow B \equiv \neg B \rightarrow \neg A\)
- Exportación: \((A \land B) \rightarrow C \equiv A \rightarrow (B \rightarrow C)\)
Tautologías, satisfacibilidad y consecuencia lógica
Sea \(A \in \mathcal{F}\). Se dice que:
- \(A\) es una tautología (o fórmula lógicamente válida), lo cual se denota \(\models A\), si \(\hat{v}(A) = V\) en toda interpretación \(v\);
- \(A\) es una contradicción (o fórmula insatisfacible) si \(\hat{v}(A) = F\) en toda \(v\);
- \(A\) es satisfacible si existe al menos una interpretación \(v\) tal que \(\hat{v}(A) = V\);
- \(A\) es contingente si es satisfacible pero no es una tautología.
Las cuatro categorías están vinculadas por la dualidad:
\[ A \text{ es tautología} \iff \neg A \text{ es contradicción} \]
Sean \(\Gamma \subseteq \mathcal{F}\) un conjunto (eventualmente infinito) de fórmulas y \(B \in \mathcal{F}\). Se dice que \(B\) es consecuencia lógica (semántica) de \(\Gamma\), lo cual se escribe
\[ \Gamma \models B \]
si para toda interpretación \(v\) tal que \(\hat{v}(A) = V\) para todo \(A \in \Gamma\), se cumple \(\hat{v}(B) = V\). Equivalentemente: todo modelo de \(\Gamma\) es modelo de \(B\).
Teorema de la deducción semántica:
\[ \Gamma \cup \{A\} \models B \iff \Gamma \models A \rightarrow B \]
En particular, tomando \(\Gamma = \emptyset\), se obtiene \(A \models B\) si y solo si \(\models A \rightarrow B\).
Formas normales (FNC y FND)
Se denomina literal a una variable proposicional o a su negación: \(p\) o \(\neg p\). En consecuencia:
- una cláusula disyuntiva es una disyunción de literales: \(\ell_1 \lor \ell_2 \lor \dots \lor \ell_k\);
- una cláusula conjuntiva es una conjunción de literales: \(\ell_1 \land \ell_2 \land \dots \land \ell_k\).
Una fórmula está en:
- Forma Normal Conjuntiva (FNC) si es una conjunción de cláusulas disyuntivas;
- Forma Normal Disyuntiva (FND) si es una disyunción de cláusulas conjuntivas.
Teorema (existencia de las formas normales). Toda fórmula \(A \in \mathcal{F}\) es lógicamente equivalente a una fórmula en FNC y a una fórmula en FND.
Procedimiento de reducción:
- eliminar el bicondicional: \(A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)\);
- eliminar el condicional: \(A \rightarrow B \equiv \neg A \lor B\);
- desplazar las negaciones hasta dejarlas únicamente delante de variables (leyes de De Morgan y doble negación), obteniendo así la forma normal negativa (FNN);
- aplicar la distributividad para alcanzar la forma deseada: \(\lor\) sobre \(\land\) para la FND, \(\land\) sobre \(\lor\) para la FNC.
Ejemplo:
\[ A \rightarrow (B \lor C) \;\equiv\; \neg A \lor (B \lor C) \;\equiv\; \neg A \lor B \lor C \]
que se halla simultáneamente en FNC (una única cláusula disyuntiva) y en FND (disyunción de cláusulas conjuntivas reducidas a literales individuales).
Sistemas deductivos
Un sistema deductivo (o cálculo lógico) es un dispositivo puramente sintáctico, constituido por axiomas y reglas de inferencia, que permite derivar fórmulas a partir de premisas sin recurrir a la semántica. La noción central es la de derivabilidad: se escribe
\[ \Gamma \vdash A \]
para indicar que existe una derivación de la fórmula \(A\) a partir de las premisas \(\Gamma\) en el sistema considerado.
Los sistemas deductivos más extendidos para la lógica proposicional son:
- Sistemas axiomáticos (al estilo Hilbert-Frege): pocos esquemas axiomáticos y una sola regla de inferencia (el modus ponens);
- Deducción natural (Gentzen, Prawitz): reglas de introducción y eliminación para cada conectiva;
- Cálculo de secuentes (Gentzen): reglas que actúan sobre secuentes \(\Gamma \Rightarrow \Delta\);
- Tableaux semánticos (Beth, Smullyan): método de refutación basado en árboles.
Las reglas de inferencia más importantes son:
Modus Ponens (eliminación de \(\rightarrow\)):
\[ \dfrac{A \qquad A \rightarrow B}{B} \]
Modus Tollens (regla de la contrarrecíproca):
\[ \dfrac{A \rightarrow B \qquad \neg B}{\neg A} \]
Silogismo hipotético (transitividad del condicional):
\[ \dfrac{A \rightarrow B \qquad B \rightarrow C}{A \rightarrow C} \]
Silogismo disyuntivo:
\[ \dfrac{A \lor B \qquad \neg A}{B} \]
Introducción y eliminación de la conjunción:
\[ \dfrac{A \qquad B}{A \land B} \qquad\qquad \dfrac{A \land B}{A} \qquad\qquad \dfrac{A \land B}{B} \]
Reducción al absurdo (demostración por contradicción):
\[ \dfrac{\Gamma, \neg A \vdash \bot}{\Gamma \vdash A} \]
Corrección y completitud
La relación entre la derivabilidad sintáctica \(\vdash\) y la consecuencia semántica \(\models\) viene dada por los dos teoremas metalógicos fundamentales de la lógica proposicional.
Teorema de corrección. Para todo \(\Gamma \subseteq \mathcal{F}\) y todo \(A \in \mathcal{F}\):
\[ \Gamma \vdash A \;\Longrightarrow\; \Gamma \models A \]
Todo lo que es derivable sintácticamente es, efectivamente, consecuencia semántica de las premisas.
Teorema de completitud (Post, 1921). Para todo \(\Gamma \subseteq \mathcal{F}\) y todo \(A \in \mathcal{F}\):
\[ \Gamma \models A \;\Longrightarrow\; \Gamma \vdash A \]
Toda consecuencia semántica puede efectivamente derivarse en el cálculo.
Combinando ambos resultados se obtiene la equivalencia entre sintaxis y semántica:
\[ \Gamma \vdash A \iff \Gamma \models A \]
A estos teoremas se añaden otros dos resultados metalógicos de relieve:
- Teorema de compacidad: \(\Gamma\) es satisfacible si y solo si todo subconjunto finito de \(\Gamma\) lo es;
- Decidibilidad: existe un algoritmo (por ejemplo, el método de las tablas de verdad) que, en un número finito de pasos, determina si una fórmula dada es o no una tautología.
Ejemplos avanzados
Ejemplo 1 — Reducción a forma normal
Reducir \( (A \rightarrow B) \land \neg B \) a FNC y FND.
Resultado
FNC: \( (\neg A \lor B) \land \neg B \) — FND: \( \neg A \land \neg B \)
Resolución
Eliminamos el condicional mediante \( A \rightarrow B \equiv \neg A \lor B \):
\[ (A \rightarrow B) \land \neg B \;\equiv\; (\neg A \lor B) \land \neg B \]
que ya está en FNC (conjunción de dos cláusulas disyuntivas). Para obtener la FND, distribuimos \(\land\) sobre \(\lor\):
\[ (\neg A \lor B) \land \neg B \;\equiv\; (\neg A \land \neg B) \lor (B \land \neg B) \;\equiv\; \neg A \land \neg B \]
puesto que \( B \land \neg B \equiv \bot \) por la ley de no contradicción. El resultado \( \neg A \land \neg B \) es una FND degenerada: se trata, en efecto, de una única cláusula conjuntiva, que cabe interpretar como una disyunción reducida a un solo término. Por convención, una cláusula conjuntiva aislada se considera en FND (al igual que una cláusula disyuntiva aislada está en FNC), pese a no aparecer explícitamente ningún \(\lor\).
Ejemplo 2 — Verificación de una tautología (silogismo hipotético)
Demostrar que \( ((A \rightarrow B) \land (B \rightarrow C)) \rightarrow (A \rightarrow C) \) es una tautología.
Resolución
Razonamos por reducción al absurdo: supongamos que existe una interpretación \(v\) bajo la cual la fórmula es falsa. Para que un condicional sea falso, su antecedente ha de ser verdadero y su consecuente falso; de ahí:
- \( \hat{v}((A \rightarrow B) \land (B \rightarrow C)) = V \), por lo que \( \hat{v}(A \rightarrow B) = V \) y \( \hat{v}(B \rightarrow C) = V \);
- \( \hat{v}(A \rightarrow C) = F \), de donde \( \hat{v}(A) = V \) y \( \hat{v}(C) = F \).
De \( \hat{v}(A) = V \) y \( \hat{v}(A \rightarrow B) = V \) se sigue \( \hat{v}(B) = V \) (en caso contrario, el condicional sería falso). De \( \hat{v}(B) = V \) y \( \hat{v}(B \rightarrow C) = V \) se obtiene \( \hat{v}(C) = V \), en contradicción con \( \hat{v}(C) = F \). Por consiguiente, la fórmula es una tautología.
Ejemplo 3 — Consecuencia lógica y regla de resolución
Verificar que \( \{A \lor B,\ \neg A \lor C\} \models B \lor C \).
Resolución
Sea \(v\) una interpretación que satisface ambas premisas. Distinguimos dos casos según el valor de \( \hat{v}(A) \):
- si \( \hat{v}(A) = V \), de \( \hat{v}(\neg A \lor C) = V \) se sigue necesariamente \( \hat{v}(C) = V \), de donde \( \hat{v}(B \lor C) = V \);
- si \( \hat{v}(A) = F \), de \( \hat{v}(A \lor B) = V \) se sigue \( \hat{v}(B) = V \), de donde \( \hat{v}(B \lor C) = V \).
En ambos casos \( \hat{v}(B \lor C) = V \), lo cual prueba la consecuencia lógica. Este principio constituye la regla de resolución, piedra angular de los métodos de demostración automática: a partir de las cláusulas \( A \lor B \) y \( \neg A \lor C \) se infiere el resolvente \( B \lor C \).
La lógica proposicional representa el primer nivel de formalización del razonamiento matemático. A pesar de su poder expresivo limitado —incapaz de describir la estructura interna de las proposiciones—, proporciona los instrumentos conceptuales fundamentales para abordar la lógica de primer orden, las teorías axiomáticas, la metalógica y las estructuras algebraicas asociadas (álgebras de Boole, retículos). Su dominio constituye un requisito imprescindible para cualquier estudio riguroso de las matemáticas y de la informática teórica.