Lógica Informática.

(Tecnologı́as Informáticas)
Relación 5: Resolución.

Ejercicio 76.– Indica en cuáles de los siguientes ejemplos se ha aplicado correctamente la

regla de resolución proposicional y en cuáles no. En este último caso, escribe las resolventes
correctas.

1. {p, q, r} Hipótesis 1. {p, ¬q} Hipótesis

2. {p, q, s} Hipótesis 2. {¬q} Hipótesis
3. {p, q, r, s} Resolvente de 1 y 2 3. {p} Resolvente de 1 y 2

1. {p, ¬q, ¬r} Hipótesis 1. {r, ¬r} Hipótesis

2. {¬p, q, r} Hipótesis 2. {r, ¬r} Resolvente de 1 y 1
3. 2 Resolvente de 1 y 2

Ejercicio 77.– Usando resolución por saturación y regular (y pasando previamente las fórmulas
a forma clausal), demuestra que:

1. (p ↔ q → r) ∧ (p ↔ q) ∧ (p → ¬r) es una contradicción.

2. {p → q, q → p ∧ r} |= p → (p → q) → r.

Ejercicio 78.– Usando resolución regular, determina la consistencia de los conjuntos de cláusu-
las:
(1) {p ∨ ¬q, p ∨ q, ¬p ∨ ¬q, ¬p ∨ q} (2) {¬r, q, p ∨ ¬q, ¬p ∨ r}
(3) {p ∨ q ∨ r, ¬p ∨ q, ¬q ∨ r, ¬r, p ∨ r} (4) {p, ¬p ∨ q, r}

Ejercicio 79.– Demuestra, utilizando resolución por entradas, la inconsistencia del conjunto
de cláusulas {¬p ∨ ¬q ∨ r, ¬s ∨ t, ¬t ∨ p, s, ¬s ∨ u, ¬u ∨ q, ¬r}.
Ejercicio 80.– Determina la inconsistencia del conjunto

{p ∨ q, q ∨ r, r ∨ w, ¬r ∨ ¬p, ¬w ∨ ¬q, ¬q ∨ ¬r}

mediante (1) resolución lineal, (2) resolución positiva, y (3) resolución negativa.
Ejercicio 81.– Determina la inconsistencia del conjunto

{¬A ∨ ¬B ∨ C, ¬A ∨ ¬G ∨ H, ¬A ∨ ¬H ∨ F, ¬G ∨ B, G, A, ¬F }

mediante (1) resolución lineal, (2) resolución positiva, (3) resolución negativa, (4) resolución
por entradas, y (5) resolución unidad.
Ejercicio 82.– Decide por el método de resolución la verdad o falsedad de las siguientes
afirmaciones:

21
 1. {p → (q → r), r → q} |= r ↔ q

2. {p → q, q → (p ∧ q), p → r} |= q → r

Ejercicio 83.– Sea A la fórmula proposicional

(p ∨ q ↔ ¬r) ∧ (¬p → s) ∧ (¬t → q) ∧ (s ∧ t → u)

1. Prueba que A es satisfactible.

2. Prueba por resolución proposicional que

{p ∨ q ↔ ¬r, ¬p → s, ¬t → q, s ∧ t → u} |= r → u

Ejercicio 84.– Ash, Misty y Brock han organizado una batalla entre sus Pokemon. Se conocen
los siguientes datos al respecto:

a) Uno, y sólo uno, de los siguientes Pokemon fue el vencedor: Pikachu, Bulbasaur,
Togepi, Starmie, Vulpix y Onix.
b) Ash ganó la batalla si el Pokemon vencedor fue Pikachu o Bulbasaur.
c) Si o bien Togepi o bien Starmie fue el vencedor, Misty ganó la batalla.
d ) Brock ganó la batalla si el vencedor fue Onix o Vulpix.
e) Si Onix fue derrotado, Starmie también.
f ) Bulbasaur fue derrotado.
g) Si Pikachu fue derrotado, entonces Ash no ganó la batalla.
h) Brock no ganó la batalla si Bulbasaur fue derrotado.
i ) Si Vulpix fue derrotado, Togepi y Onix también corrieron la misma suerte.

1. Formaliza los datos anteriores en el lenguaje de la lógica proposicional.

2. Para cada fórmula obtenida, escribe un conjunto de cláusulas equivalente.

3. Usando resolución proposicional, demuestra que Ash fue el ganador.

Ejercicio 85.– Sea Σ el conjunto de fórmulas (donde a y b son sı́mbolos de constante):

{∀x (P (x, f (x)) → ¬P (x, b)), ∀x (P (x, a) → P (x, b)), ∀x (¬∃z P (x, z) ∨ P (x, f (x)))}

Decide, mediante resolución, si:

1. Σ |= ¬∃x ∃z (P (x, z) ∧ P (x, a))

2. Σ |= P (x, z) ∧ P (x, a)

22
Ejercicio 86.– Determina si existe una refutación a partir de los siguientes conjuntos de
cláusulas, y si no es posible, justifı́calo:
(a) {p(x, x), ¬p(x, f (x)), p(x, f (x)) ∨ ¬p(f (x), y), p(x, y) ∨ ¬p(x, z) ∨ ¬p(y, z)}
(b) {p(x, x), ¬p(x, f (x)), p(x, f (x)) ∨ ¬p(f (x), y), ¬p(x, y) ∨ p(x, z) ∨ p(y, z)}
Ejercicio 87.– Sea Γ = {p(x, 0, x), p(x, y, z) → p(x, s(y), s(z))}. Utilizando resolución, prueba
que:

1. Γ |= p(s(s(0)), s(0), s(s(s(0)))).

2. Γ ̸|= p(0, x, x).

Ejercicio 88.– Sea Σ el conjunto formado por las siguientes fórmulas:

(1) P (a) ∧ ∀x (P (x) → Q(f (x), x)) (3) ∀x (P (x) ∨ R(x))

(2) Q(x, y) → [R(f (x)) ∧ ¬R(f (f (x)))] (4) ∀x¬(P (x) ∧ R(x))

Se pide:

1. Prueba mediante resolución que Σ |= P (f (f (f (a)))).

2. Prueba, utilizando el teorema de Herbrand, que Σ ̸|= Q(f (x), x) → P (x).

3. Prueba, por inducción en n, que para todo n ∈ N, Σ |= R(f 3n+2 (a)) ∧ P (f 3n (a)).

Ejercicio 89.– Aplica el algoritmo de unificación a los siguientes conjuntos:

(1) {p(x, y), p(y, f (z))} (4) {p(x, g(x), y), p(z, u, g(u))}
(2) {p(c, y, f (y)), p(z, z, u)} (5) {p(g(x), y), p(y, y), p(u, f (w))}
(3) {p(x, g(x)), p(y, y)} (6) {p(x, f (y), z), p(g(w), u, g(w)), p(v, v, g(w)}
Ejercicio 90.– Encuentra, si existe, un unificador para cada conjunto de expresiones (como
siempre, las últimas letras del alfabeto son sı́mbolos de variables y las primeras, de constantes):

(1) {P (x, z, y), P (w, u, w), P (a, u, u)} (5) {P (f (x, x), a), P (f (y, f (y, a)), a)}
(2) {¬P (a), P (x)} (6) {P (f (a), x), P (x, a)}
(3) {P (f (f (x)), z), P (f (u), f (v))} (7) {P (f (x), x), P (u, f (u))}
(4) {Q(f (x), a, y), Q(u, f (v), b)} (8) {Q(f (x), y, z), Q(f (u), a, f (a))}

Ejercicio 91.– Sean t1 y t2 dos términos. Diremos que t1 es más general que t2 si existe una
sustitución θ tal que t2 = t1 θ. Decide, en los siguientes casos, si el primer término es más general
que el segundo:
(1) x, f (x, y) (2) h(h(x, y), x), h(z, x) (3) f (g(y), y), f (g(x), a).
(4) h(x, y), h(g(y), y) (5) f (x, x), f (x, y).
Ejercicio 92.– Determina, por resolución, la validez de las fórmulas:

23
 1. ∃x [[P (x) → P (a)] ∧ [P (x) → P (b)]]

2. ∀z [Q(z) → P (z)] → [∃x [Q(x) → P (a)] ∧ [Q(x) → P (b)]]

3. ∃x ∃y [[P (f (x)) ∧ Q(f (b))] → [P (f (a)) ∧ P (y) ∧ Q(y)]]

4. ∃x ∀y P (x, y) → ∀y ∃x P (x, y)

5. ∀x [P (x) ∧ [Q(a) ∨ Q(b)]] → ∃x [P (x) ∧ Q(x)]

Ejercicio 93.– Determina la consistencia de los conjuntos de cláusulas:

1. {Q(u) ∨ P (a), ¬Q(w) ∨ P (w), ¬Q(x) ∨ ¬P (x)}

2. {Q(u) ∨ P (a), ¬Q(w) ∨ P (w), ¬Q(x) ∨ ¬P (x), Q(y) ∨ ¬P (y)}

3. {I(a), ¬R(x) ∨ L(x), ¬D(y) ∨ ¬L(y), D(a)}

4. {I(a), ¬R(x) ∨ L(x), ¬D(y) ∨ ¬L(y), D(a), ¬I(z) ∨ R(z)}

5. {¬P (x, y) ∨ ¬P (y, z) ∨ P (x, z), P (a, x), P (x, b), P (x, f (x)}

6. {M (a, s(c), s(b)), P (a), M (x, x, s(x)), ¬M (x, y, z) ∨ D(x, z),

¬P (x) ∨ ¬M (y, z, u) ∨ ¬D(x, u) ∨ D(x, y), ¬D(a, b)}

Ejercicio 94.– Determina los problemas de deducción:

1. {∀x[P (x) → ∃y[R(y) ∧ Q(x, y)]], ∃x[P (x)]} |= ∃x ∃y Q(x, y)

2. {¬A(x) ∨ F (x) ∨ G(f (x)), ¬F (x) ∨ B(x), ¬F (x) ∨ C(x), ¬G(x) ∨ B(x),
¬G(x) ∨ D(x), A(g(x)) ∨ F (h(x))} |= ∃x ∃y [[B(x) ∧ C(x)] ∨ [D(y) ∧ B(y)]]

3. {∃x ∀y ¬P (y, x), ∀z ∃y ∀x [P (x, y) ↔ [P (x, z) ∧ ¬P (x, y)]]} |= ∀x ∀y ¬P (y, x)

4. {∃x ∀y P (x, y), ∀x ∀y [P (x, y) → ¬P (y, x)]} |= ∀x ∃y P (x, y)

5. {∀x∀y∀z∀u∀v∀w [P (x, y, u) ∧ P (y, z, v) ∧ P (x, v, w) → P (u, z, w)],

∀x∀y∃z P (z, x, y), ∀x∀y∃z P (x, z, y)} |= ∃x∀y P (y, x, y)

Ejercicio 95.– Sabemos que:

1. Pepe tiene dinero: DI(P epe).

2. La librerı́a Lib tiene el libro Sistemas Expertos: T L(Lib, SE).

3. Pepe quiere ese libro: Q(P epe, SE).

24
 4. Si una librerı́a L envı́a el libro l a un cliente c, EN V (L, l, c), entonces el cliente recibe el
libro: R(c, l).

5. Si una librerı́a L tiene un libro l, y un cliente c le envı́a un cheque, CH(c, L), entonces la
librerı́a L envı́a el libro l al cliente c.

6. Si un cliente quiere un libro, y tiene dinero, entonces puede enviar un cheque a una
librerı́a.

Expresa estos conocimientos en forma de cláusulas y, por resolución, determinar si Pepe recibirá
el libro Sistemas Expertos.
Ejercicio 96.– Sabemos que

1. Existen pacientes a quienes les gustan todos los médicos.

2. A ningún paciente le gusta ningún curandero

Con los predicados P (x) = “x es un paciente”, M (x) = “x es un médico”, C(x) = “x es un

curandero”, y G(x, y) = “a x le gusta y”, expresar los conocimientos anteriores en forma de
cláusulas y, por resolución, demostrar que ningún médico es curandero.
Ejercicio 97.– Sabemos que:

1. Los aficionados a la música son cultos.

2. A algunos cultos les gusta el fútbol.

3. Los aficionados a todo no son cultos.

4. Los aficionados al fútbol, pero no a la música, no son cultos.

Con los predicados AF (x, y) = “x es aficionado a y” y CU (x) = “x es culto”, prueba por

resolución que hay a quien le gusta la música y el fútbol.
Ejercicio 98.– Sabemos que

1. Marco era pompeyano.

2. Todos los pompeyanos eran romanos.

3. Cada romano, o era leal a César, o le odiaba.

4. Todo el mundo es leal a alguien.

5. La gente sólo intenta asesinar a quienes no es leal.

6. Marco intentó asesinar a César.

25
Con los predicados P (x) = “x es pompeyano”, R(x) = “x es romano”, L(x, y) = “x es leal a
y”, O(x, y) = “x odia a y”, y IA(x, y) = “x intentó asesinar a y”, formaliza los conocimientos
anteriores y, por resolución, responde a las preguntas: ¿Era leal Marco a César? ¿Odiaba Marco
a César?
Ejercicio 99.– Sabemos que

1. Todos los pasajeros que no eran VIP’s fueron registrados por algún aduanero.

2. Algunos pasajeros eran narcotraficantes, y fueron registrados sólo por narcotraficantes.

3. Ningún narcotraficante era VIP.

Con los predicados P (x) = “x es pasajero”, V (x) = “x es VIP”, A(x) = “x es aduanero”, N (x) =
“x es narcotraficante”, y R(x, y) = “x es registrado por y”, expresa los conocimientos anteriores
en forma de cláusulas y, por resolución, demuestra que algún aduanero es narcotraficante.
Ejercicio 100.– Se conocen los siguientes hechos acerca de las preferencias de dos famosos
personajes:

1. Silvestre y Garfield son gatos.

2. A todos los gatos les gusta el queso o los ratones.

3. A nadie a quien le guste el queso, le gusta el vino.

4. A quienes les gustan los ratones, les gusta la cerveza.

5. A Garfield no le gusta lo que le gusta a Silvestre.

6. A Silvestre le gusta el vino y la cerveza.

Se pide:

(a) Formaliza los enunciados anteriores en lenguaje de primer orden utilizando:

a, b, c, d, como constantes para queso, ratones, vino y cerveza, respectivamente.

SIL y GAR como constantes para Silvestre y Garfield, respectivamente.
Los predicados: G(x): “x es un gato”, GU (x, y): “a x le gusta y”.

(b) Obtén una forma clausal para el conjunto de fórmulas obtenido en el apartado anterior.

(c) Prueba mediante resolución que a Garfield le gusta el queso y no le gusta el vino.

Ejercicio 101.– Las relaciones de parentesco verifican la siguientes propiedades generales:

Si x es hermano de y, entonces y es hermano de x.

26
 Todo el mundo es hijo de alguien.

Nadie es hijo del hermano de su padre.

Cualquier padre de una persona es también padre de todos los hermanos de esa persona.

Nadie es hijo ni hermano de sı́ mismo.

Tenemos los siguientes miembros de la familia Peláez: D. Antonio, D. Luis, Antoñito y Manolito,
y sabemos que D. Antonio y D. Luis son hermanos, Antoñito y Manolito son hermanos, y
Antoñito es hijo de D. Antonio. Se pide:

1. Formaliza los conocimientos anteriores en un lenguaje de primer orden usando tan solo:

A, L, a, m como constantes para D. Antonio, D. Luis, Antoñito y Manolito, resp.

Los predicados: Her(x, y) = x es hermano de y, Hijo(x, y) = x es hijo de y

2. Obtén una forma clausal para el conjunto de fórmulas obtenido en el apartado 1.

3. Decide mediante resolución no restringida si D. Luis es el padre de Manolito o no.

Ejercicio 102.– Se conocen los siguientes hechos:

1. Todos los ordenadores son máquinas.

2. El TX-150 es un ordenador.

3. Félix puede arreglar, o bien estropear, cualquier máquina.

4. Cada cosa puede ser arreglada por alguien.

5. Las cosas solamente desesperan a quienes no son capaces de arreglarlas.

6. El TX-150 desespera a Félix.

7. Ninguna máquina puede ser arreglada por sı́ misma.

Se pide:

(a) Formaliza los hechos anteriores utilizando los siguientes sı́mbolos de predicado:
O(x): “x es un ordenador”, M (x): “x es una máquina”, A(x, y): “x puede arreglar y”,
E(x, y): “x estropea y” y D(x, y): “x desespera a y”.
Y a, b como constantes para TX-150 y Félix, respectivamente.

(b) Utilizando resolución no restringida responder a las siguientes preguntas: ¿Puede arreglar
Félix el TX-150? ¿Estropea Félix el TX-150?

27