Tema 2: Lógica de predicados (L1)

Diapositivas: 2. LógicaPredicados_2026-2027 · Tema anterior: Tema 1 - Lógica proposicional

Cómo leer esta nota

La lógica de predicados amplía la proposicional: todo lo del Tema 1 (conectivas, equivalencias, consecuencia lógica, resolución, deducción natural) sigue valiendo. Aquí están solo las novedades.

Por qué hace falta

La lógica proposicional se queda corta. "Todos los perros son buenos. Fido es un perro. Por tanto, Fido es bueno" es un razonamiento claramente correcto, pero en L0 serían tres proposiciones sin relación ( $p$ , $q$ y $r$ ), y $\{p, q\} \models r$ no se puede demostrar. Las proposiciones no permiten hablar de individuos ni de sus propiedades o relaciones.

La lógica de predicados mantiene las conectivas y añade constantes, variables, funciones, predicados y cuantificadores.

Sintaxis

Alfabeto

Elemento	Qué representa	Ejemplos
Constantes ( $a, b, c$ …)	Objetos concretos	Juan, Asturias, 2
Variables ( $X, Y$ …)	Objetos cualesquiera	$X$ , $Y$
Funciones ( $f, g$ …)	Referirse a un objeto a partir de otros	padreDe( $X$ ), sumaDe(2, 3)
Predicados ( $p, q, r$ …)	Propiedades y relaciones (dan V o F)	esBueno( $X$ ), viveEn( $X$ , $Y$ )
Conectivas	Como en L0	$\lnot, \land, \lor, \to, \leftrightarrow$
Cuantificadores	Cómo se interpretan las variables	$\forall$ (para todo), $\exists$ (existe)

La aridad es el número de argumentos de una función o de un predicado.

Términos y fórmulas

Término: una constante, una variable o una función aplicada a términos. Ejemplos: Juan, $X$ , sumaDe(3, sumaDe(2, 2)). Un término designa un objeto; no es ni verdadero ni falso.
Fórmula atómica: un predicado aplicado a términos. Ejemplos: $q(X, Y)$ , viveEn(Juan, $X$ ). Esto sí es verdadero o falso.
Literal: una fórmula atómica o su negación.
Fórmulas compuestas: con las conectivas, como en L0, y además, si $G$ es fórmula y $X$ una variable, $\forall X\, G$ y $\exists X\, G$ también lo son.

Prioridad: $\lnot$ , $\forall$ y $\exists$ tienen la máxima prioridad, al mismo nivel. Después $\land$ , $\lor$ , $\to$ y $\leftrightarrow$ , como en L0.

Variables libres y ligadas

En $\forall X\, F$ o $\exists X\, F$ , $F$ es el ámbito (alcance) del cuantificador.
Una aparición de una variable está ligada si está dentro del ámbito de un cuantificador sobre esa variable, y libre si no.
Si una variable está dentro de varios cuantificadores sobre ella, la liga el más cercano.
Fórmula cerrada (sentencia): no tiene ninguna variable libre.

Ejemplo: en $\forall X \forall Y\,(p(X,Y) \land q(X,Z) \to r(X))$ , $X$ e $Y$ están ligadas y $Z$ está libre, así que la fórmula no es cerrada.

Formalizar con cuantificadores

Elegir constantes, funciones y predicados (y escribir qué significan).
Traducir cada frase.

La regla de oro

$\forall$ va con $\to$ : "Todos los estudiantes son elegantes" es $\forall X\,(\text{est}(X) \to \text{eleg}(X))$ .
$\exists$ va con $\land$ : "Hay un estudiante elegante" es $\exists X\,(\text{est}(X) \land \text{eleg}(X))$ .

$\forall X\,(\text{est}(X) \land \text{eleg}(X))$ significaría "todo el mundo es estudiante y elegante", casi nunca lo que se quiere decir.

Frase	Fórmula
Todos los $p$ son $q$	$\forall X\,(p(X) \to q(X))$
Solo los $p$ son $q$	$\forall X\,(q(X) \to p(X))$
Algún $p$ es $q$	$\exists X\,(p(X) \land q(X))$
Ningún $p$ es $q$	$\forall X\,(p(X) \to \lnot q(X))$ , o bien $\lnot\exists X\,(p(X) \land q(X))$
Algún $p$ no es $q$	$\exists X\,(p(X) \land \lnot q(X))$ , o bien $\lnot\forall X\,(p(X) \to q(X))$

El orden de los cuantificadores importa… si son distintos

Dos del mismo tipo se pueden intercambiar: $\forall X \forall Y \equiv \forall Y \forall X$ y $\exists X \exists Y \equiv \exists Y \exists X$ .
Un $\forall$ y un $\exists$ no:
- $\forall X \exists Y\ \text{gustar}(X, Y)$ : "a todo el mundo le gusta alguien" (cada uno, el suyo).
- $\exists Y \forall X\ \text{gustar}(X, Y)$ : "hay alguien que le gusta a todo el mundo".

Ejemplos de las diapositivas

Con $D(X)$ : $X$ es un dragón, $P(X)$ : $X$ es un piojo, $A(X,Y)$ : $X$ acosa a $Y$ .

Todo piojo acosa a algún dragón: $\forall Y\,[P(Y) \to \exists X\,(D(X) \land A(Y,X))]$
Algunos piojos acosan a todos los dragones: $\exists Y\,[P(Y) \land \forall X\,(D(X) \to A(Y,X))]$
Todo dragón es acosado por algún piojo: $\forall X\,[D(X) \to \exists Y\,(P(Y) \land A(Y,X))]$

Con $P(X)$ : perro, $H(X)$ : humano, $A(X,Y)$ : $X$ es amigo de $Y$ .

Hay algún perro que no es amigo de ningún humano: $\exists X\,[P(X) \land \lnot\exists Y\,(H(Y) \land A(X,Y))]$
Los perros son amigos solo de los humanos: $\forall X\,[P(X) \to \forall Y\,(A(X,Y) \to H(Y))]$

Semántica

Una interpretación $I$ de una fórmula consiste en:

Un dominio $D$ : un conjunto no vacío de objetos.
Para cada constante $c$ , un objeto $c^I \in D$ .
Para cada función $f$ de aridad $n$ , una aplicación $f^I: D^n \to D$ .
Para cada predicado $P$ de aridad $n$ , una aplicación $P^I: D^n \to \{V, F\}$ .

La misma fórmula puede ser verdadera en una interpretación y falsa en otra. Por ejemplo, $\forall X\,(p(X) \land q(X) \to r(f(X))) \land q(a)$ puede hablar de jugadores de póker o de números impares.

Hay infinitas interpretaciones

Los dominios pueden ser cualquier conjunto, así que no se pueden usar tablas de verdad. Para probar la consecuencia lógica hacen falta métodos sintácticos: resolución y deducción natural.

Reglas semánticas de los cuantificadores (las conectivas funcionan igual que en L0):

$(\forall X\, G(X))^I = V$ si $G^I(d) = V$ para todo $d \in D$ .
$(\exists X\, G(X))^I = V$ si $G^I(d) = V$ para algún $d \in D$ .

💡 Evaluar en un dominio finito

En un dominio finito, $\forall$ es un "y" gigante y $\exists$ un "o" gigante. Con $D = \{1, 2, 3\}$ :

$\forall X\, G(X) \equiv G(1) \land G(2) \land G(3)$
$\exists X\, G(X) \equiv G(1) \lor G(2) \lor G(3)$

Con varios cuantificadores se desarrollan de fuera hacia dentro.

Clasificación y equivalencias

Las definiciones de fórmula válida, satisfacible e insatisfacible, equivalencia y consecuencia lógica son las mismas que en L0, cambiando "todas las filas de la tabla" por "todas las interpretaciones". También se mantienen todas las equivalencias de L0. Además:

Ley	Equivalencia
Gran De Morgan	$\lnot\forall X\, G(X) \equiv \exists X\, \lnot G(X)$ y $\lnot\exists X\, G(X) \equiv \forall X\, \lnot G(X)$
Mismo cuantificador	$\forall X \forall Y\, G \equiv \forall Y \forall X\, G$ y $\exists X \exists Y\, G \equiv \exists Y \exists X\, G$
Gran distributividad	$\forall X\,(G \land H) \equiv \forall X\, G \land \forall X\, H$ y $\exists X\,(G \lor H) \equiv \exists X\, G \lor \exists X\, H$
Distributividad restringida (si $X$ no aparece en $H$ )	$H \land \forall X\, G \equiv \forall X\,(H \land G)$ , y lo mismo con $\lor$ y con $\exists$

Lo que no se puede hacer

Solo vale en un sentido	Contraejemplo del otro sentido
$\forall X\, G \lor \forall X\, H \models \forall X\,(G \lor H)$	"Todos están felices o tristes" no implica "todos felices o todos tristes"
$\exists X\,(G \land H) \models \exists X\, G \land \exists X\, H$	"Existen perros y existen gatos" no implica "existe un perro que es gato"
$\exists X \forall Y\, G \models \forall Y \exists X\, G$	"Todos salen con alguien" no implica "alguien sale con todos"

Resolución general

Es la misma idea que en L0: se prueba $\Gamma \models G$ por refutación, viendo que $\Gamma \cup \{\lnot G\}$ es inconsistente. El método es correcto y completo. Se necesita pasar todo a forma clausal, y hay dos problemas nuevos: los cuantificadores (se resuelve con Skolem) y las variables (se resuelve con la unificación).

Forma normal de Skolem (FNS)

Una sentencia está en FNS si:

todos los cuantificadores están al principio;
no hay cuantificadores existenciales;
el núcleo está en FNC.

Toda sentencia $F$ se puede pasar a FNS. La fórmula obtenida no es equivalente, pero sí equisatisfacible: es satisfacible si y solo si lo era $F$ . Para la resolución basta, porque lo que interesa es si el conjunto es inconsistente.

Pasos:

Eliminar $\leftrightarrow$ y $\to$ (como en L0).
Meter las negaciones hasta los átomos (De Morgan, doble negación y Gran De Morgan).
Renombrar variables para que cada cuantificador tenga la suya: $\forall X\, p(X) \lor \forall X\, q(X) \equiv \forall X\, p(X) \lor \forall Y\, q(Y)$ .
Sacar todos los cuantificadores al principio, sin cambiar su orden (distributividad restringida).
Eliminar los $\exists$ (skolemización):
- Si un $\exists Y$ no tiene ningún $\forall$ delante, $Y$ se cambia por una constante de Skolem nueva: $\exists Y \forall X\, p(Y, X)$ pasa a $\forall X\, p(a, X)$ .
- Si tiene $\forall X_1, \dots, X_m$ delante, $Y$ se cambia por una función de Skolem nueva de esas variables: $\forall X \exists Y\, p(X, Y)$ pasa a $\forall X\, p(X, f(X))$ . El $Y$ depende de cuál sea el $X$ .
Pasar el núcleo a FNC (distributivas).

Forma clausal: se quitan los cuantificadores (todos son $\forall$ y se sobreentienden) y cada cláusula de la FNC se escribe por separado.

Ejemplo de las diapositivas

\exists X \forall Y\, \lnot(\forall Y\, p(X,Y) \to q(X,Y)) \lor \forall Z\, r(Z)

Quitar $\to$ y meter la $\lnot$ : $\;\exists X \forall Y\,(\forall Y\, p(X,Y) \land \lnot q(X,Y)) \lor \forall Z\, r(Z)$
Renombrar las dos $Y$ : $\;\exists X \forall Y_1\,(\forall Y_2\, p(X,Y_2) \land \lnot q(X,Y_1)) \lor \forall Z\, r(Z)$
Cuantificadores delante: $\;\exists X \forall Y_1 \forall Y_2 \forall Z\,[(p(X,Y_2) \land \lnot q(X,Y_1)) \lor r(Z)]$
Skolem ( $X$ sin $\forall$ delante → constante $a$ ): $\;\forall Y_1 \forall Y_2 \forall Z\,[(p(a,Y_2) \land \lnot q(a,Y_1)) \lor r(Z)]$
FNC: $\;(p(a,Y_2) \lor r(Z)) \land (\lnot q(a,Y_1) \lor r(Z))$

Forma clausal: $\{p(a,Y_2) \lor r(Z),\ \ \lnot q(a,Y_1) \lor r(Z)\}$

Las constantes de Skolem tienen que ser nuevas

Si la constante $a$ ya aparece en otra cláusula del problema, se usa otra ( $b$ , $c$ …). Si no, se estaría diciendo que ese "alguien" es precisamente $a$ .

Sustitución y unificación

¿Por qué no basta la resolución de L0? $\{\forall X\, p(X),\ \lnot p(a)\}$ es inconsistente, pero $p(X)$ y $\lnot p(a)$ no son literales complementarios "tal cual". Hay que particularizar $X$ en $a$ .

Una sustitución $\theta = \{V_1/t_1, \dots, V_n/t_n\}$ cambia cada variable $V_i$ por el término $t_i$ en toda la expresión. Ejemplo: con $\theta = \{X/g(Y)\}$ , $p(X, W, f(X))$ pasa a ser $p(g(Y), W, f(g(Y)))$ .
- Una variable no se puede sustituir por un término que la contenga: $X/f(X)$ no vale.
Composición $\theta_1\theta_2$ : se aplica $\theta_2$ a los términos de $\theta_1$ y se añaden los pares de $\theta_2$ cuyas variables no estén en $\theta_1$ .
Unificar es encontrar una sustitución que deje varias expresiones idénticas. El unificador más general (umg) es el que particulariza lo mínimo.
- $\text{umg}\{p(X, a),\ p(Y, a)\} = \{Y/X\}$ . $\{X/b, Y/b\}$ también unifica, pero particulariza de más.
- $\text{umg}\{p(X, f(b), a),\ p(a, f(Y), a)\} = \{X/a, Y/b\}$ .
- $\{p(X),\ q(a)\}$ : predicados distintos, no unifican.

Algoritmo de unificación:

Empezar con la sustitución vacía.
Recorrer las expresiones de izquierda a derecha hasta el primer desacuerdo (el primer símbolo distinto).
Si el desacuerdo es entre dos términos que no son variables con distinto símbolo de función, o entre una variable y un término que la contiene: no son unificables.
Si no, formar $\{X/t\}$ con la variable $X$ y el término $t$ del desacuerdo, componerlo con la sustitución que se lleva y aplicarlo.
Repetir hasta que las expresiones sean idénticas. La sustitución acumulada es el umg.

$p(X,\ a,\ f(g(Y)))$ y $p(f(Z),\ Z,\ f(U))$

Desacuerdo $\{X, f(Z)\}$ → $\{X/f(Z)\}$
Desacuerdo $\{a, Z\}$ → $\{Z/a\}$ ; acumulado: $\{X/f(a), Z/a\}$
Desacuerdo $\{g(Y), U\}$ → $\{U/g(Y)\}$
Quedan idénticas: $p(f(a), a, f(g(Y)))$ .

\text{umg} = \{X/f(a),\ Z/a,\ U/g(Y)\}

Renombrar variables antes de unificar

Las variables de cláusulas distintas son independientes. $p(X, Y)$ y $p(Y, f(X))$ no unifican tal cual, pero renombrando una, $p(X, Y)$ y $p(Y_1, f(X_1))$ , sí: $\{X/Y_1,\ Y/f(X_1)\}$ .

Regla de resolución general

De $C_1 = G \lor \lnot E_1$ y $C_2 = H \lor E_2$ , donde $E_1$ y $E_2$ son del mismo predicado y unificables con $\sigma = \text{umg}(E_1, E_2)$ :

\text{Res}(C_1, C_2) = G\sigma \lor H\sigma

Se unifican los dos literales, se tachan y se aplica $\sigma$ a lo que queda. También se pueden unificar varios literales de golpe ( $\sigma = \text{umg}(E_1 \cup E_2 \cup E_3)$ ).

Algoritmo: igual que en L0, pero renombrando las variables de una de las dos cláusulas antes de resolver (si las dos tienen variables) y aplicando el umg. Se para al obtener $\square$ (refutable: el razonamiento es correcto) o cuando no se puede seguir.

Todos los perros son animales, todos los animales mueren, Fido es un perro ⊨ Fido muere

Forma clausal de las premisas y de la conclusión negada:

\{\lnot\text{perro}(X) \lor \text{animal}(X),\ \ \lnot\text{animal}(Y) \lor \text{muere}(Y),\ \ \text{perro}(\text{fido}),\ \ \lnot\text{muere}(\text{fido})\}

Resolver las dos primeras con $\{X/Y\}$ ⟹ $\lnot\text{perro}(Y) \lor \text{muere}(Y)$
Con $\text{perro}(\text{fido})$ y $\{Y/\text{fido}\}$ ⟹ $\text{muere}(\text{fido})$
Con $\lnot\text{muere}(\text{fido})$ ⟹ $\square$

Conjunto inconsistente: el razonamiento es correcto.

Estrategias

El algoritmo es no determinista: su eficacia depende de qué par de cláusulas y qué literales se eligen en cada paso.

A lo ancho: calcular todas las resolventes de cada nivel. Es completo, pero muy costoso.
Conjunto soporte: resolver siempre usando al menos una cláusula que venga de la negación de la conclusión o de una resolvente suya. Su versión más importante es la resolución SLD, la que usa Prolog.

Deducción natural

Se usan las mismas reglas que en L0 y se añaden dos por cuantificador:

Cuantificador	Introducción	Eliminación
$\forall$	Si para un $t$ libre (arbitrario) se llega a $A(t)$ , se deduce $\forall x\, A(x)$	De $\forall x\, A(x)$ se deduce $A(a)$ para cualquier término $a$
$\exists$	De $A(a)$ se deduce $\exists x\, A(x)$	De $\exists x\, A(x)$ : se abre una caja suponiendo $A(t)$ con $t$ libre. Si dentro se llega a $B$ sin $t$ , se deduce $B$

Qué significa " $t$ libre"

El término $t$ no puede aparecer en ninguna caja anterior que siga abierta, ni en las premisas. Es un objeto "cualquiera" del que no se sabe nada más.

Error típico: de $\exists x\, P(x)$ y $\exists x\, Q(x)$ no se puede deducir $\exists x\,(P(x) \land Q(x))$ . Si se abre una caja con $P(a)$ , luego no se puede suponer $Q(a)$ con la misma $a$ , porque ya no es libre. Que exista algo con $P$ y algo con $Q$ no significa que sea lo mismo.

$\{\forall x\,(P(x) \to Q(x)),\ P(a)\} \vdash \exists x\, Q(x)$

$\forall x\,(P(x) \to Q(x))$ — premisa
$P(a)$ — premisa
$P(a) \to Q(a)$ — $\forall$ E 1
$Q(a)$ — $\to$ E 2, 3
$\exists x\, Q(x)$ — $\exists$ I 4