Volver a LÓGICA Y ESTRUCTURAS DISCRETAS (INGENIERÍA EN IA)

LÓGICA Y ESTRUCTURAS DISCRETAS (INGENIERÍA EN IA)octubre de 202613 min de lectura

Tema 1–2 · Lógica Proposicional

LED logica proposicional tableaux formas-normales IA

Mapa del tema

Cubre los dos bloques del temario: (1) Lenguaje y semántica — fórmulas, conectivas, árboles sintácticos, formalización, tablas de verdad, equivalencias y formas normales — y (2) Razonamiento — satisfacibilidad, tautologías, tableaux semánticos y consecuencia lógica.

logica_prop_mapa

1. Conceptos Fundamentales (Explicación Clara)

1.1 ¿Qué es una proposición?

Una proposición es una afirmación que solo puede ser verdadera (1) o falsa (0), nunca ambas cosas a la vez. "Llueve" es una proposición; "¿Llueve?" o "¡Cierra la puerta!" no lo son.

Analogía

Piensa en cada proposición como un interruptor de la luz: solo tiene dos estados, encendido (1) o apagado (0). La lógica proposicional estudia cómo combinar interruptores con "cables" (las conectivas) para obtener circuitos más complejos.

1.2 El lenguaje: cómo se construyen las fórmulas

El lenguaje está formado por fórmulas, construidas con estas reglas (definición recursiva):

Las variables proposicionales $p, q, r, \dots$ son fórmulas (fórmulas atómicas).
Las constantes $\top$ (siempre verdadero) y $\bot$ (siempre falso) son fórmulas.
Si $\alpha$ y $\beta$ son fórmulas, también lo son $\neg\alpha$ , $\alpha\land\beta$ , $\alpha\lor\beta$ , $\alpha\to\beta$ , $\alpha\leftrightarrow\beta$ .

Conectiva	Símbolo	Nombre	Se lee
Negación	$\neg$	Monaria	"no"
Conjunción	$\land$	Binaria	"y"
Disyunción	$\lor$	Binaria	"o" (inclusivo)
Implicación	$\to$	Binaria	"si… entonces…"
Bicondicional	$\leftrightarrow$	Binaria	"si y sólo si"

Precedencia (de mayor a menor)

$\neg \;>\; \land \;>\; \lor \;>\; \to \;>\; \leftrightarrow$ Así, $\neg p \to q \lor r$ se lee como $(\neg p) \to (q \lor r)$ . Ante la duda, usa paréntesis.

1.3 Árboles sintácticos

Toda fórmula tiene una estructura de árbol: la raíz es la conectiva principal (la última que se aplica) y las hojas son las variables. Identificar la conectiva principal es la habilidad clave para tablas de verdad, formas normales y tableaux.

logica_prop_arboles_sintacticos

1.4 Formalización: del lenguaje natural a fórmulas

Es la parte donde más se falla en el examen. La trampa principal está en el condicional.

Conectiva	Expresiones en castellano
$\neg\alpha$	no $\alpha$ · no es el caso que $\alpha$ · no es cierto que $\alpha$
$\alpha\land\beta$	$\alpha$ y $\beta$ · $\alpha$ pero $\beta$ · $\alpha$ aunque $\beta$
$\alpha\lor\beta$	$\alpha$ o $\beta$ · bien $\alpha$ , bien $\beta$ · ya $\alpha$ , ya $\beta$
$\alpha\to\beta$	si $\alpha$ , (entonces) $\beta$ · $\beta$ , si $\alpha$ · $\alpha$ sólo si $\beta$ · sólo si $\beta$ , $\alpha$ · es suficiente $\alpha$ para $\beta$ · es necesario $\beta$ para $\alpha$
$\alpha\leftrightarrow\beta$	$\alpha$ si y sólo si $\beta$ · $\alpha$ es condición suficiente y necesaria de $\beta$

La regla de oro del condicional

Lo que va tras "si" (o lo suficiente) → antecedente (izquierda de $\to$ ).
Lo que va tras "sólo si" (o lo necesario) → consecuente (derecha de $\to$ ).

"Sólo si te entrenas ( $p$ ), puedes ganar ( $q$ )" → $q \to p$ (entrenar es necesario, no suficiente). "Es suficiente acertar los dígitos ( $p$ ) para tener premio ( $q$ )" → $p \to q$ .

Más ejemplos del temario:

"La lógica es fácil ( $p$ ), pero hay que estudiar ( $q$ )" → $p \land q$
"No es cierto que haya tomado vino ( $p$ ) o cerveza ( $q$ )" → $\neg(p \lor q)$
"Sólo si llueve ( $p$ ), tomo un taxi ( $q$ )" → $q \to p$

1.5 Semántica: interpretaciones y valores de verdad

Una interpretación $I$ asigna un valor (0 o 1) a cada variable. Con $n$ variables hay $2^n$ interpretaciones posibles: una por fila de la tabla de verdad.

La propagación funcional consiste en calcular el valor de la fórmula subiendo por el árbol sintáctico, desde las hojas hasta la raíz.

El condicional "raro"

$\alpha\to\beta$ solo es falso cuando $\alpha=1$ y $\beta=0$ . Si el antecedente es falso, el condicional es verdadero ("verdad vacía"). Analogía: "Si apruebas, te invito a cenar". Solo mientes si apruebas y no te invito. Si suspendes, hagas lo que hagas, no has incumplido la promesa.

1.6 Equivalencia lógica

Dos fórmulas son equivalentes ( $\alpha\equiv\beta$ ) cuando son verdaderas exactamente en las mismas interpretaciones (mismas columnas en la tabla de verdad). Es una relación reflexiva, simétrica y transitiva (de equivalencia).

Principio de reemplazo: si $\alpha\equiv\beta$ y $\alpha$ aparece dentro de una fórmula $\gamma$ , sustituir $\alpha$ por $\beta$ da una fórmula equivalente a $\gamma$ . Es lo que nos permite "operar" con fórmulas como con álgebra.

1.7 Formas normales

Literal: una variable o su negación ( $p$ , $\neg p$ ).
Conjunción elemental: conjunción de literales ( $p\land\neg q\land r$ ).
Disyunción elemental (o cláusula): disyunción de literales ( $\neg p\lor q$ ).
FNC (Forma Normal Conjuntiva): conjunción de disyunciones → $(\ldots\lor\ldots)\land(\ldots\lor\ldots)$
FND (Forma Normal Disyuntiva): disyunción de conjunciones → $(\ldots\land\ldots)\lor(\ldots\land\ldots)$

Para qué sirven

La FND dice de un vistazo cuándo es verdadera la fórmula: basta con que una conjunción lo sea.
La FNC dice de un vistazo cuándo es falsa: basta con que falle una cláusula (todos sus literales a 0).

Algoritmo (4 pasos, en este orden):

logica_prop_algoritmo

1.8 Satisfacibilidad, tautologías y contradicciones

logica_prop_satisfacibilidad

Satisfacible: existe al menos una interpretación que la hace verdadera.
Conjunto satisfacible: existe una interpretación que hace verdaderas todas sus fórmulas a la vez.
Tautología ( $\models A$ ): verdadera en todas las interpretaciones. Todas son equivalentes a $\top$ .
Contradicción: falsa en todas. Todas son equivalentes a $\bot$ .

Las preguntas trampa del temario (expansiones y reducciones)

Si el conjunto es…	¿y si añado fórmulas (expansión)?	¿y si quito fórmulas (reducción)?
Satisfacible	Puede dejar de serlo	Sigue siéndolo ✅
Insatisfacible	Sigue siéndolo ✅	Puede dejar de serlo

Intuición: añadir fórmulas = añadir restricciones. Más restricciones nunca "arreglan" algo imposible, y menos restricciones nunca "rompen" algo posible.

1.9 Tableaux semánticos

Un tableau es un método de árbol para decidir si un conjunto de fórmulas es satisfacible sin hacer la tabla de verdad completa (que con 5 variables ya tiene 32 filas).

Analogía: un detective que busca un mundo posible

El tableau intenta construir un mundo donde todas las fórmulas sean verdad. Cada rama es una "hipótesis de mundo". Cuando una rama contiene una contradicción ( $\lambda$ y $\neg\lambda$ ), esa hipótesis muere (rama cerrada ⊗). Si todas mueren, no existe ningún mundo posible: el conjunto es insatisfacible.

Fórmulas α (conjuntivas): verdaderas si ambas componentes lo son → se añaden en la misma rama (expansión lineal).
Fórmulas β (disyuntivas): verdaderas si al menos una componente lo es → la rama se bifurca.
σ (doble negación): de $\neg\neg\lambda$ se pasa a $\lambda$ .
Cierre ⊗: aparecen $\lambda$ y $\neg\lambda$ en la misma rama.

Estrategia

Aplica primero las reglas α (no ramifican) y después las β. El árbol queda mucho más pequeño.

1.10 Consecuencia lógica

$\alpha$ es consecuencia lógica de $\Gamma$ ( $\Gamma\models\alpha$ ) si toda interpretación que hace verdaderas las premisas de $\Gamma$ también hace verdadera $\alpha$ . Es la formalización de "razonamiento válido".

La falacia de la presentación de la asignatura

"Si es mamífero ( $A$ ), es animal ( $B$ ). No es mamífero ( $\neg A$ ). Luego no es animal ( $\neg B$ )." $\{A\to B,\ \neg A\}\not\models\neg B$ : la interpretación $A=0, B=1$ (un pez) hace verdaderas las premisas y falsa la conclusión. Es la falacia de negación del antecedente.

2. Fórmulas y Formalismo Matemático

2.1 Tablas de verdad de las conectivas

$\alpha$	$\beta$	$\neg\alpha$	$\alpha\land\beta$	$\alpha\lor\beta$	$\alpha\to\beta$	$\alpha\leftrightarrow\beta$
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

Truco para recordar

$\land$ : solo es 1 si todo es 1.
$\lor$ : solo es 0 si todo es 0.
$\to$ : solo es 0 en la fila $1\to0$ .
$\leftrightarrow$ : es 1 cuando ambos valores coinciden.

2.2 Tabla de verdad de una fórmula compuesta

Con $n$ variables: $2^n$ filas. Ejemplo del temario: $\neg(p\land q)\to r\lor p$ .

$p$	$q$	$r$	$p\land q$	$\neg(p\land q)$	$r\lor p$	$\neg(p\land q)\to r\lor p$
1	1	1	1	0	1	1
1	1	0	1	0	1	1
1	0	1	0	1	1	1
1	0	0	0	1	1	1
0	1	1	0	1	1	1
0	1	0	0	1	0	0
0	0	1	0	1	1	1
0	0	0	0	1	0	0

→ Fórmula contingente (satisfacible pero no tautología). Es falsa justo cuando $p=0$ y $r=0$ .

2.3 Esquemas de equivalencia (chuleta)

Doble negación y elementos neutros/absorbentes

$\neg\neg X\equiv X$

Con sí misma	Tercio excluso / no contradicción	Con $\bot$	Con $\top$
$X\lor X\equiv X$	$X\lor\neg X\equiv\top$	$X\lor\bot\equiv X$	$X\lor\top\equiv\top$
$X\land X\equiv X$	$X\land\neg X\equiv\bot$	$X\land\bot\equiv\bot$	$X\land\top\equiv X$

Conmutativa, asociativa, absorción, distributiva

\begin{aligned} X\lor Y &\equiv Y\lor X & X\lor(Y\lor Z)&\equiv(X\lor Y)\lor Z\\ X\land Y &\equiv Y\land X & X\land(Y\land Z)&\equiv(X\land Y)\land Z\\ X\lor(Y\land X) &\equiv X & X\lor(Y\land Z)&\equiv(X\lor Y)\land(X\lor Z)\\ X\land(Y\lor X) &\equiv X & X\land(Y\lor Z)&\equiv(X\land Y)\lor(X\land Z) \end{aligned}

De Morgan, condicional y bicondicional ⭐ (las más usadas)

\begin{aligned} \neg(X\land Y)&\equiv\neg X\lor\neg Y & \neg(X\lor Y)&\equiv\neg X\land\neg Y\\ X\to Y&\equiv\neg X\lor Y & X\to Y&\equiv\neg Y\to\neg X \quad\text{(contrarrecíproco)}\\ X\leftrightarrow Y&\equiv(X\to Y)\land(Y\to X) & X\leftrightarrow Y&\equiv(X\land Y)\lor(\neg X\land\neg Y) \end{aligned}

Derivadas útiles para el test

$\neg(X\to Y)\equiv X\land\neg Y \qquad \neg(X\leftrightarrow Y)\equiv(X\land\neg Y)\lor(\neg X\land Y)$ Ojo: $X\to Y\not\equiv Y\to X$ (recíproco) y $X\to Y\not\equiv\neg X\to\neg Y$ (contrario). Solo el contrarrecíproco es equivalente.

2.4 Propiedades formales de la satisfacibilidad

Si $A\equiv B$ , o ambas son satisfacibles o ninguna lo es.
$\{A,B,\dots,Z\}$ es satisfacible $\iff$ $A\land B\land\dots\land Z$ es satisfacible.
$A$ es satisfacible $\iff$ $FNC(A)$ lo es $\iff$ $FND(A)$ lo es.
Si $A\equiv B$ entonces $\models A\leftrightarrow B$ . Así, cada equivalencia se convierte en un bicondicional tautológico: $\models\neg(A\land B)\leftrightarrow(\neg A\lor\neg B)$ .

Relaciones clave entre conceptos (para preguntas de test):

\begin{aligned} A \text{ es tautología} &\iff \neg A \text{ es insatisfacible}\\ A \text{ es satisfacible} &\iff \neg A \text{ no es tautología}\\ \Gamma\models\alpha &\iff \Gamma\cup\{\neg\alpha\}\text{ es insatisfacible}\\ \{A_1,\dots,A_n\}\models B &\iff \models A_1\land\dots\land A_n\to B \end{aligned}

2.5 Tabla de reglas de tableaux

Tipo α (no ramifica)	$\alpha_1$	$\alpha_2$
$\varphi\land\psi$	$\varphi$	$\psi$
$\neg(\varphi\lor\psi)$	$\neg\varphi$	$\neg\psi$
$\neg(\varphi\to\psi)$	$\varphi$	$\neg\psi$

Tipo β (ramifica)	$\beta_1$	$\beta_2$
$\varphi\lor\psi$	$\varphi$	$\psi$
$\neg(\varphi\land\psi)$	$\neg\varphi$	$\neg\psi$
$\varphi\to\psi$	$\neg\varphi$	$\psi$
$\varphi\leftrightarrow\psi$	$\varphi\land\psi$	$\neg\varphi\land\neg\psi$
$\neg(\varphi\leftrightarrow\psi)$	$\varphi\land\neg\psi$	$\neg\varphi\land\psi$

Tipo σ	Resultado
$\neg\neg\lambda$	$\lambda$

logica_prop_tablas_tableaux

Teoremas fundamentales de tableaux

Corrección y completitud

$\Gamma$ es satisfacible $\iff$ el tableau de $\Gamma$ es abierto (queda alguna rama sin cerrar).
Si hay una rama completa y abierta, sus literales definen una interpretación que satisface $\Gamma$ (las variables que no aparezcan pueden tomar cualquier valor).

Usos del tableau según lo que preguntan:

Quiero saber si…	Hago el tableau de…	Respuesta
$\Gamma$ es satisfacible	$\Gamma$	Abierto → sí
$A$ es contradicción	$\{A\}$	Cerrado → sí
$A$ es tautología	$\{\neg A\}$	Cerrado → sí
$\Gamma\models\alpha$	$\Gamma\cup\{\neg\alpha\}$	Cerrado → sí

2.6 Propiedades de la consecuencia lógica

\begin{aligned} &\textbf{Reflexividad:} && \Gamma\cup\{\alpha\}\models\alpha\\ &\textbf{Monotonía:} && \Gamma\models\alpha \;\Rightarrow\; \Gamma\cup\Lambda\models\alpha\\ &\textbf{Transitividad:} && \Gamma\models\alpha \text{ y } \{\alpha\}\models\beta \;\Rightarrow\; \Gamma\models\beta \end{aligned}

Caso límite

Si $\Gamma$ es insatisfacible, entonces $\Gamma\models\alpha$ para cualquier $\alpha$ (no hay ninguna interpretación que satisfaga $\Gamma$ y "falle" en $\alpha$ ). De una contradicción se deduce cualquier cosa.

3. Ejemplos Aplicados a la Inteligencia Artificial (¡Crucial!)

3.1 Sistemas expertos y bases de conocimiento

Un sistema experto clásico guarda el conocimiento como una base de conocimiento (KB): un conjunto $\Gamma$ de fórmulas. Responder una pregunta $\alpha$ es comprobar si $KB\models\alpha$ .

text

KB (diagnóstico de red — muy en tu terreno de soporte IT):
  R1: sin_enlace → cable_suelto ∨ switch_caido
  R2: switch_caido → otros_equipos_sin_red
  R3: ¬otros_equipos_sin_red
  H1: sin_enlace
Pregunta: ¿KB ⊨ cable_suelto ?

Formalizado ( $e$ =sin_enlace, $c$ =cable_suelto, $s$ =switch_caido, $o$ =otros_sin_red):

$KB=\{e\to c\lor s,\ \ s\to o,\ \ \neg o,\ \ e\}\models c\,?$

Tableau de $KB\cup\{\neg c\}$ : de $s\to o$ y $\neg o$ se cierra la rama $s$ ; de $e\to c\lor s$ y $e$ solo queda $c\lor s$ , y ambas ramas se cierran ( $c$ con $\neg c$ ; $s$ con lo anterior). Tableau cerrado → el sistema concluye "cable suelto". Esto es exactamente lo que hace un motor de inferencia, aunque los reales usan resolución sobre la FNC (cláusulas).

3.2 Agentes lógicos (el "Mundo de Wumpus")

En el libro de referencia de IA (Russell & Norvig), un agente basado en conocimiento explora una cueva. Usa variables como $B_{1,1}$ ("hay brisa en la casilla 1,1") y $P_{1,2}$ ("hay pozo en 1,2"):

$B_{1,1}\leftrightarrow (P_{1,2}\lor P_{2,1})$

Si percibe $\neg B_{1,1}$ , por consecuencia lógica deduce $\neg P_{1,2}\land\neg P_{2,1}$ : las casillas vecinas son seguras. El agente decide moverse sin arriesgarse gracias a $KB\models\alpha$ .

3.3 SAT solvers: satisfacibilidad a escala industrial

El problema de decidir si una fórmula en FNC es satisfacible (SAT) fue el primer problema demostrado NP-completo (teorema de Cook, 1971). Aun así, los SAT solvers modernos (algoritmos DPLL/CDCL, primos sofisticados de los tableaux) resuelven fórmulas con millones de variables:

Planificación automática (SATPlan): "¿existe un plan de $k$ pasos?" se codifica como SAT.
Verificación de hardware y software: "¿puede el circuito llegar a un estado de error?" → si la fórmula es insatisfacible, el diseño es seguro.
Configuración de productos, horarios, Sudokus: restricciones = cláusulas.

Conexión directa con el temario

Toda la cadena fórmula → FNC → ¿satisfacible? que estudias aquí es literalmente la entrada estándar (formato DIMACS) de un SAT solver.

3.4 Puertas lógicas y neuronas

Las conectivas son funciones booleanas. Un perceptrón (la neurona artificial más simple) puede implementar $\land$ , $\lor$ y $\neg$ ajustando pesos y umbral:

Puerta	Pesos $(w_1,w_2)$	Umbral	Se activa si
AND ( $\land$ )	$(1,1)$	$1.5$	$x_1+x_2\geq1.5$
OR ( $\lor$ )	$(1,1)$	$0.5$	$x_1+x_2\geq0.5$

Pero no puede implementar XOR ( $\neg(p\leftrightarrow q)$ ), porque sus casos verdaderos no son separables por una recta. Este resultado (Minsky & Papert, 1969) frenó la investigación en redes neuronales y motivó las redes multicapa. Con la FND, $p\oplus q\equiv(p\land\neg q)\lor(\neg p\land q)$ : dos neuronas AND en una capa oculta + una OR en la salida.

3.5 Detección de falacias en lenguaje natural

Como se menciona en la presentación de la asignatura, un sistema de NLP puede formalizar un argumento y comprobar con tableaux si $\Gamma\models\alpha$ . Si el tableau de $\Gamma\cup\{\neg\alpha\}$ queda abierto, la rama abierta es literalmente el contraejemplo que demuestra la falacia.

David González Lombraña

Apuntes, laboratorio y proyectos de IA, Linux y redes.