1º -- Grado en Ingeniería Informática – Facultad de Informática

Fundamentos Lógicos de la Informática

EJERCICIOS de TEORÍA

2. Lógica Proposicional
Ejercicios Propuestos

1. ¿Cuál de las siguientes equivalencias son correctas? Aplica las equivalencias lógicas para comprobarlo.
a. p  (p  q)  p
b. p → (q → r)  (p → q) → r
c. p  (q  r )  (p  q)  r
2. Dadas las siguientes fórmulas bien formadas (fbfs), realiza la tabla de verdad y clasifica cada fbf, en
satisfacible, contingente, falseable, tautología y/o contradicción.
a. p  q → (q  p)
b. p → q → (p → q)
c. (p → q) → (q  p)
d. (p  q) → (p  q)
e. (p  q) → (r  s)
f. p → (q  r)
g. (p → q)  (q → r)
3. Dado el siguiente conjunto de fbfs { ((p → q)  p) → q; ((p → q)  q) → p }, responde a las preguntas
y razona la respuesta.
a. ¿Es el conjunto satisfacible? ¿Cuál es el modelo o modelos que la hacen al conjunto satisfacible?
¿Es una tautología?
b. Si al conjunto le elimino la fbf ((p → q)  q) → p, ¿sigue siendo satisfacible? ¿y tautología?
c. Si al conjunto le añado la siguiente fbf p  q → (q  p), ¿sigue siendo satisfacible? ¿y tautología?
¿Y falseable?

1
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

4. Problema SAT en L0
Ejercicios Resueltos

1. Obtén la Forma Normal Conjuntiva de la siguiente fórmula bien formada:

ɸ = ((p → q) → p  r)  ((p  r) → (p → q))
Solución:
Aplicamos, en orden, las equivalencias para la transformación de una fbf a su FNC.
((p → q) → p  r)  ((p  r) → (p → q))  (Eliminación →)
 ( ( (p  q))  p  r)  (  (p  r)  ( p  q))  (Reducir alcance )
 ( (p  q)  p  r )  ( (p  r)  (p  q) )  (Eliminación doble negación)
 ( (p  q)  p  r )  ( (p  r)  (p  q) )  (Distributividad)
 ( (p  q)  p  r )  ( ( (p  r)  p )  ( (p  r) q ) ) 
 ( (p  q)  p  r )  ( ( (p  p)  (r p) )  ( (p q)  (rq) ) )  (Reducir paréntesis)
 ( p  q  p  r )  (p  p)  (r p)  (p q)  (rq))  (Eliminar literales opuestos)
 (V  q  r )  (V)  (r p)  (p q)  (rq))  (Eliminar constantes)
 (r p)  (p q)  (rq))
2. Aplica el Algoritmo DPLL para saber si el siguiente conjunto de cláusulas es satisfacible:
ɸ = { {p}; {p, q}; {p, q} }
Solución:
Siguiendo los pasos que no indica el algoritmo DPLL, obtenemos lo siguiente:
▪ No podemos aplicar la regla de la Tautología.
▪ Tenemos una cláusula unitaria p; por lo tanto, propagamos dicho literal: ɸ(p) = { {q}; {q} }
Continuamos teniendo cláusulas unitarias. Propagamos por una de ellas: ɸ(p, q) = {  }
El procedimiento DPLL acaba devolviendo la cláusula vacía, lo que nos indica que el conjunto clausal es
INSATISFACIBLE.
3. Aplica el Algoritmo DPLL para saber si el siguiente conjunto de cláusulas es satisfacible:
ξ = { {p, q, r}; {p, q, s}; {p, q, r}; {p, q, r}; {q, r, s} }
Solución:
Siguiendo los pasos que no indica el algoritmo DPLL, obtenemos lo siguiente:
▪ Tenemos cinco cláusulas cada una con tres literales. No se puede aplicar la tautología (no hay
ninguna cláusula en la que aparece un literal y su negado). Tampoco tenemos cláusulas unitarias,
ni literales puros, ni podemos aplicar la regla de inclusión (subsumidas). Aplicamos la Regla de
Ramificación (ojo, debemos hacer backtraking, si llega el caso). Por ejemplo, seleccionamos p.
ξ’ = ξ{p} y ξ’’ = ξ {p}
▪ Seguimos por ξ’= { {p, q, r}; {p, q, s}; {p, q, r}; {p, q, r}; {q, r, s}; {p} } y se comienza de
nuevo con las reglas.
▪ No podemos aplicar la regla de la Tautología. Tenemos la cláusula unitaria p, por lo tanto,
propagamos dicho literal:
ξ’(p) = { {q, s}; {q, r}; {q, r}; {q, r, s} }
▪ No hay más literales unitarios, no hay literales puros y no se puede aplicar la regla de inclusión.
De nuevo, aplicamos la Regla de Ramificación. Por ejemplo, con q,
ξ’’’=ξ’{q} y ξ’’’’=ξ’ {q}
▪ Seguimos por ξ’’’= { {q, s}; {q, r}; {q, r}; {q, r, s}; {q} } y se comienza de nuevo con las reglas.
▪ No podemos aplicar la regla de Tautología. Tenemos la cláusula unitaria q. Propagamos:
ξ’’’(q) = { {r}; {r, s} }

2
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

▪ Seguimos propagando por la cláusula unitaria r.

ξ’’’ (q,r) = {  }
Podemos observar que por esta rama no hemos obtenido ninguna interpretación que haga
satisfacible al conjunto de cláusulas. Debes explorar las otras ramas abiertas.
▪ Seguimos por ξ’’’’ = { {q, s}; {q, r}; {q, r}; {q, r, s}; {q} } y se comienza de nuevo.
▪ No podemos aplicar la regla de Tautología. Tenemos la cláusula unitaria q. Propagamos:
ξ’’’’(q) = { {s}; {r, s} }
▪ Seguimos propagando por cláusula unitaria, s.
ξ’’’’ (q,s) = { r }
▪ Seguimos propagando por cláusula unitaria, r.
ξ’’’’ (q,s,r) = { Ø }
▪ El procedimiento DPLL acaba, devolviendo el conjunto vacío de cláusulas, lo que nos indica que el
conjunto clausal es SATISFACIBLE.
El conjunto clausulado ξ = { {p, q, r}; {p, q, s}; {p, q, r}; {p, q, r}; {q, r, s} } es por tanto
SATISFACIBLE para el modelo v(p) = V, v(q) = F, v(s) = V, v(r) = V.
La resolución en forma de árbol:

4. Aplica el Algoritmo de Resolución para saber si el siguiente conjunto de cláusulas es satisfacible:

ξ={ {p, q}; {p}; {p, q,s} }
Solución:
Cuando apliquemos la regla de resolución aplicaremos las reglas de eliminación. Para comprobar la
satisfacibilidad, utilizaremos la estrategia de saturación por niveles.
1. {p,q} Premisa
2. {p} Premisa
3. {p,q,s} Premisa
4. {q} Rp(1,2), Subsumida (1), Subsumida (3) , Puro(2)
5. Puro (4)
No llegamos a la cláusula vacía y hemos analizado todas las sentencias por lo cual el conjunto de
cláusulas es satisfacible.

3
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

5. Aplica el Algoritmo de Resolución para saber si el siguiente conjunto de cláusulas es satisfacible:

ξ= { {q, p}; {q}; {p,r}; {p, s}; {r}; {s} }
Solución:
Cuando apliquemos la regla de resolución aplicaremos las reglas de eliminación. Para comprobar la
satisfacibilidad, utilizaremos la estrategia de saturación por niveles.
1. {q, p} Premisa
2. {q} Premisa
3. {p, r} Premisa
4. {p, s} Premisa
5. {r} Premisa
6. {s} Premisa
7. {p} Rq (1,2), Subsumida(1), Puroq (2)
8. {p} Rr (3,5), Subsumida(3), Subsumida(4), Puror (5), Puros (6)
9. {} Rp (7,8)
Llegamos a la cláusula vacía entonces el conjunto ξ es no satisfacible.
El grafo de resolución con simplificación (por niveles):

6. Aplica el Algoritmo de Resolución con conjunto soporte para averiguar si el siguiente razonamiento es
válido. Utiliza refutación.
{ p → q, q → r, p } ⊨ r
Solución:
SI utilizamos refutación, un razonamiento {α1, α2, α3, …, αn} ⊨  es VÁLIDO sii {α1  α2  α3  …  αn 
} es una contradicción.
• Primero se pasan las premisas a FNC: { p  q, q  r, p }
• Después aplicamos refutación, negando la conclusión y convirtiendo a FNC: r
• Tenemos el conjunto de cláusulas ξ = { pq, qr, p, r } (de la fbf (pq)  (qr)  p  r)
y comenzamos el método de resolución con conjunto soporte. Recordad que cuando aplicamos
la regla de resolución aplicaremos también las reglas de eliminación.
1. {p, q} Premisa
2. {q, r} Premisa
3. {p} Premisa
4. {r} Conjunto Soporte (CS)
5. {q} Rr (2,4) CS, Subsumida (2), Puror (4)
6. {p} Rq (1,5) CS, Subsumida (1) , Puroq (5)
7. {} Rp (3,6) CS
Como hemos llegado a la cláusula vacía y hemos utilizado el planteamiento por refutación, entonces el
razonamiento es válido.

4
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

7. Aplica la técnica de Arboles semánticos para saber si la siguiente fórmula bien formada es satisfacible:
(p→s)(p→t)(s→t)
Solución:
(p→s)(p→t)(s→t)

p p
v(V→s) =? v(F→s) =V
v(V→t) = ? v(F→t) = V
v (?  (s→t)) = ? (V→s)(V→t)(s→t) (F→s)(F→t)(s→t)
v (V  (s→t)) = V
s s NODO ÉXITO

v(V→V) =V v(V→F) =F
v(F→t) = ? (V→V)(V→t)(V→t) (V→F)(V→t)(F→t) v(F→t) = ?
v((V→t) = ? (V→t) v((F→t) = V En este nodo ya
NODO ÉXITO
t t v (F  V) = V podríamos parar e
indicar que la fórmula
es satisfacible (es un
(V→V)(V→V)(V→V) (V→V)(V→F)(V→F)
nodo éxito), es decir,
(V→t)
NODO ÉXITO (V→t)
NODO FALLO con v(p)=F la fórmula es
satisfacible sin importar
Continuamos con el resto del árbol para ver si es una el resto de variables.
tautología. En este caso, vemos que hay un nodo
fallo, por lo cual la fórmula no es una tautología.

8. ¿Es satisfacible la oración: ɸ = (p → (q  r) → (p → q))? Aplica la técnica de Tableaux semánticos
para comprobarlo.
Solución:

La expresión ɸ es la negación de una

(p→(q¬r)→(p→q)) La expresión ɸ conforma
el nodo raíz del Tableau.
implicación que constituye una α- α-fórmula
fórmula. Se construye un nodo
(p→(q¬r))
desdoblando en serie las dos partes. La expresión (p→ q) es la negación
(p→q)
de una implicación que constituye
α-fórmula una α-fórmula. Se construye un nodo
La expresión (p→(qr)) es una
(p→(q¬r)) desdoblando en serie las dos partes.
implicación que constituye una β-
p
fórmula. Se abren dos ramas con q
nuevos nodos, colocando en cada uno
de ellos una de las partes disyuntadas. β -fórmula
p (q¬r)
p p La expresión (qr) es una
q q conjunción que constituye una

α-fórmula α-fórmula por lo que se
construye un nodo desdoblando
q en serie las dos partes.
r
p
q 

Los nodos hoja del Tableau Semántico Completado quedan CERRADOS (contienen un literal y su negado).
Por tanto, ɸ es INSATISFACIBLE (CONTRADICCIÓN). No hemos obtenido interpretaciones!!!!!

5
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

Ejercicios Propuestos

1. Obtén la Forma Normal Conjuntiva de las siguientes fórmulas bien formadas e indica si son o no una
tautología.
a. ((p  q)  (p q)) → ((p → (q  r)) → (p → r))
b. (p  (q → p)) →p
c. (p → q) →(p  q)  r)
d. (p → q)  p  q
e. ((p → q) → r ) → s
2. Con la forma normal conjuntiva de los apartados anteriores aplica el Método de Resolución, el algoritmo
de DPLL, la técnica de árboles semánticos y la técnica de Tableax semánticos para saber si las fórmulas
son satisfacibles.
3. Aplica el Algoritmo DPLL y el Método de resolución para saber si los siguientes conjuntos de cláusulas es
satisfacible:
a. ξ={ {p, q, r}; {p, q}; {p, q, r} }
b. ξ= { {p, q, t}; {p, q, t}; {q, t}; {q, t}; {q, t} }
c. ξ= { {p, q, s}; {p, q, s}; {p, q}; {p, s}; {p, q, s}; {q, q, s}; {p, q, s} }
4. Aplica el Método de Resolución por conjunto soporte, el algoritmo DPLL , la técnica de los árboles
semánticos y la técnica de Tableaux semánticos a los siguientes razonamientos para saber si son válidos
o no. Utiliza refutación. En caso de no ser válidos indica un contraejemplo.
a. { p → (q  (r  s)), p, s } ⊨ q
b. { p → q, q → r, r → s, (p → s) → (q → p), p } ⊨ q
c. { p, q → p, r→q } ⊨ (s → r) → s
d. { p → (q → r), r → s, p } ⊨ (qr) → s
e. { p → q, p → q, p  p } ⊨ q
f. { p  p, (p → q)  (q → r),(p → s)  (s → r) } ⊨ r

6
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

5. Lógica Categórica y de Relaciones

Ejercicios Propuestos

1. Para las siguientes relaciones, expresadas en forma de conjuntos, indica si son o no funciones. Justifica
tus respuestas.
a. R1={ {a,b}, {a,c}, {b,a}, {c,a} }
b. R2={ {a,b}, {b,c}, {b,a}, {c,a} }
c. R3={ {a,b,2}, {b,c,1}, {b,a,1}, {c,a,1} }
d. R3={ {1,b,2}, {2,c,1}, {3,a,1}, {1,a,1} }
2. Para las siguientes relaciones, expresadas en forma tabular, indica si son o no funciones. Justifica tus
respuestas.
R1 a b c R2 1 2 3 R3 1 2 3 R4 a b c
1 1 0 0 1 1 0 0 1 0 0 1 a 0 0 1
2 1 1 0 2 0 1 0 2 0 1 0 b 0 1 0
3 1 0 0 3 1 0 0 3 0 0 1 c 1 0 1
4 1 0 0 4 1 0 0 4 0 1 0 d 0 1 0

R5 a b c R6 a b c R7 1 2 3 R8 a b c
1 1 0 0 a 1 0 1 1 0 0 1 1 1 0 0
2 0 1 0 b 0 1 0 2 1 1 0 2 1 0 0
3. Para las siguientes oraciones, indica con que forma normal categórica se identifican y representa el
diagrama de Euler correspondiente.
a. Todos los alumnos llegan puntuales.
b. Algún alumno no trae mochila
c. Ningún alumno está matriculado
d. Todos los alumnos no estudian suficiente.
4. Para el conjunto A, indica si es verdadero o falso las siguientes expresiones y justifica la respuesta:
a. A={ 2, {3}, 3, {5} }
i. 2 ∈ A
ii. {2} ⊆ A
iii. {2} ∈ A
iv. {{5}} ⊆ A
v. {5} ∈ A

7
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

6. Lógica de Predicados
Ejercicios Resueltos

1. Identifica en la siguiente fbf de lógica de predicados, si hay variables libres o todas son ligadas.
∀𝑥 ( (𝑃(𝑥)  𝑄(𝑥)) → ∀𝑦 (𝑀(𝑦)  𝐺(𝑥, 𝑦)) ) → 𝑅(𝑥, 𝑦)  𝑇(𝑧)
Solución:
Marquemos en la fbf el alcance de los distintos cuantificadores.
∀𝑥 ( (𝑃(𝑥)  𝑄(𝑥)) → ∀𝑦 (𝑀(𝑦)  𝐺(𝑥, 𝑦)) ) → 𝑅(𝑥, 𝑦)  𝑇(𝑧)
alcance de ∀𝑦
alcance de ∀x

Las variables libres son aquellas que no están sujetas a un cuantificador, si analizamos la fbf, tenemos
que 𝑃(𝑥)  𝑄(𝑥) están bajo el cuantificador ∀𝑥. Por lo tanto, “x” sería una variable ligada. Para las
variables de los predicados 𝑀(𝑦)  𝐺(𝑥, 𝑦), tenemos “y” bajo el cuantificador ∀𝑦 y “x” que se quedaría
bajo el cuantificador primero de ∀𝑥, ya que después de 𝐺(𝑥, 𝑦)), es cuando se cierra el paréntesis del
∀𝑥 de la primera parte de la fórmula. La segunda parte de la fbf tenemos 𝑅(𝑥, 𝑦)  𝑇(𝑧) donde las
variables “x” e “y” del predicado R serían variables libres, y lo mismo para la variable z, del predicado
𝑇(𝑧), ya que en ese caso no se encuentran recogidas bajo ningún cuantificador

Ejercicios Propuestos

1. Identifica en las siguientes fbfs de lógica de predicados, si hay variables libres o todas son ligadas
a. ∀𝑥 (𝑃(𝑥)  𝑄(𝑥)) → ∃𝑥 (𝑄(𝑦)  𝑃(𝑥, 𝑦)) → 𝑅(𝑥, 𝑦)
b. ∀𝑥 𝑄(𝑥)  𝑀(𝑥, 𝑦, 𝑧) → ∀𝑥(𝑄(𝑥)  𝑅(𝑥, 𝑦))
c. ∀𝑥 𝑄(𝑥)  ∀𝑥 𝑀(𝑥, 𝑦, 𝑧) → ∃𝑥(𝑄(𝑥)  𝑅(𝑥, 𝑥))
d. ∃𝑦 (𝑄(𝑦)  ∀𝑥 𝑀(𝑥, 𝑦)) → ∀𝑥(𝑄(𝑥)  𝑃(𝑥))

8
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

7. Razonamientos Extensión a L1
Ejercicios Resueltos

1. Realiza la composición de sustituciones de los siguientes ejemplos, y la aplicas a la fbf 𝛽.

a. s1·s2 con s1 = {f(y)/x} y s2 = {a/y}. 𝛽 = P(x, y).
b. s2·s1 con s1 = {f(y)/x} y s2 = {a/y}. 𝛽 = P(x, y).
c. s1·s2 con s1 = {f(y)/x, z/y} y s2 = {a/x, b/z}. 𝛽 = P(x, y, g(z)).
d. s1·s2 con s1 = {a/x, f(x,c)/y} y s2 = {b/x}. 𝛽 = P(x, y).
e. s2·s1 con s1 = {a/x, f(x,c)/y} y s2 = {b/x}. 𝛽 = P(x, y).
Solución:
a. s1 = {f(y)/x) y s2 = (a/y}.
• Composición s1·s2 = { f(a)/x, a/y }.
• Aplicamos a 𝛽, s1 y s2 secuencialmente. Primero 𝛽s1 = P(f(y),y), y segundo (𝛽s1)·s2 = P(f(a),a).
• Aplicamos a 𝛽 la composición s1·s2 y nos queda: 𝛽(s1·s2) = P(f(a),a).
b. s1 = {f(y)/x} y s2 = (a/y}.
• Composición s2·s1 = { a/y, f(y)/x }.
• Aplicamos a 𝛽, s2 y s1 secuencialmente. Primero 𝛽s2 = P(x,a), y segundo (𝛽s2)·s1 = P(f(y),a).
• Aplicamos a 𝛽 la composición s2·s1 y nos queda: 𝛽(s2·s1) = P(f(y),a).
Como se puede observar no se obtiene el mismo resultado que en el apartado anterior, por lo que
es un ejemplo de que las sustituciones no cumplen la propiedad conmutativa.
c. s1 = {f(y)/x, z/y} y s2 = {a/x, b/z}.
• Composición s1·s2 = { f(y)/x, b/y, b/z }.
• Aplicamos a 𝛽, s1 y s2 secuencialmente. 𝛽s1 = P(f(z),z,g(z)), y (𝛽s1)·s2 = P(f(b),b,g(b)).
• Aplicamos a 𝛽 la composición s1·s2 y nos queda: 𝛽(s1·s2) = P(f(b),b,g(b)).
d. s1 = {a/x, f(x,c)/y} y s2 = {b/x}.
• Composición s1·s2 = { a/x, f(b,c)/y }.
• Aplicamos a 𝛽, s1 y s2 secuencialmente. 𝛽s1 = P(a,f(x,c)), y (𝛽s1)·s2 = P(a,f(b,c)).
• Aplicamos a 𝛽 la composición s1·s2 y nos queda: 𝛽(s1·s2) = P(a,f(b,c)).
e. s1 = {a/x, f(x,c)/y} y s2 = {b/x}
• Composición s2·s1 = { b/x, f(x,c)/y }.
• Aplicamos a 𝛽, s2 y s1 secuencialmente. 𝛽s2 = P(b,y), y (𝛽s2)·s1 = P(b,f(x,c)).
• Aplicamos a 𝛽 la composición s2·s1 y nos queda: 𝛽(s2·s1) = P(b,f(x,c)).
2. Comprueba si es correcta la siguiente equivalencia:
∀x ¬ (P(x) →Q(x)) ≡ ¬ (∀x P(x) → ∃x Q(x))
Solución:
Partimos de la fórmula de la izquierda, y como sabemos que ¬(P(x) → Q(x)) ≡ (P(x)  ¬Q(x)), la fórmula
es equivalente a
∀x ¬(P(x) → Q(x)) ≡ ∀x (P(x)  ¬Q(x))
Por la equivalencia citada del cuantificador universal y la conectiva conjunción:
∀x (P(x)  ¬Q(x)) ≡ ∀x P(x)  ∀x ¬Q(x)
Aplicando la equivalencia lógica de D’Morgan: (A  B) ≡ ¬ (¬A  ¬B),
∀x P(x)  ∀x ¬Q(x) ≡ ¬ (¬ ∀x P(x)  ¬ ∀x ¬Q(x))
Aplicando la equivalencia de interdefinición:
¬ (¬ ∀x P(x)  ¬ ∀x ¬Q(x)) ≡ ¬ (∀x P(x) → ¬ ∀x ¬Q(x))
Aplicando en el consecuente de la implicación la equivalencia de la negación del universal con el
existencial de la negación y la idempotencia (¬¬A≡A) llegamos a la parte derecha de la equivalencia:
¬ (∀x P(x) → ¬∀x ¬Q(x)) ≡ ¬ (∀x P(x) → ∃x Q(x))

9
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

Ejercicios Propuestos

1. Realiza la composición de sustituciones de s1·s2, para los siguientes ejemplos y la aplicas a la fbf 𝛽.
a. s1 = {g(y)/x) y s2 = (a/y}, 𝛽 = P(x, y)  Q(x).
b. s1 = {g(y)/x) y s2 = (a/y} , 𝛽 = P(f(x), y)  Q(x).
c. s1 = {g(y)/x,b/z) y s2 = (a/y}, 𝛽 = P(x, y,z)  Q(y).
d. s1 = {g(y)/x,f(y)/z) y s2 = (a/y}, 𝛽 = P(x, y)  Q(y,z).
2. Realiza la composición de sustituciones de s2·s1, para los siguientes ejemplos y la aplicas a la fbf 𝛽
a. s1 = {g(y)/x) y s2 = (a/y}, 𝛽 = P(x, y)  Q(x).
b. s1 = {g(y)/x) y s2 = (a/y}, 𝛽 = P(f(x), y)  Q(x).
c. s1 = {g(y)/x,b/z) y s2 = (a/y}, 𝛽 = P(x, y,z)  Q(y).
d. s1 = {g(y)/x,f(y)/z) y s2 = (a/y}, 𝛽 = P(x, y)  Q(y,z).
3. Una vez realizado el ejercicio 1 y 2, responde a la siguiente pregunta. ¿La composición de sustituciones
cumple la propiedad conmutativa?
4. Comprueba si las siguientes equivalencias son ciertas:
a. ¬∃x (¬P(x) → 𝑄(𝑥))≡ ∀x (¬P(x)  ¬𝑄(𝑥))
b. ¬∃x (P(x) → 𝑄(𝑥))≡ ∀x(¬P(x)  ¬𝑄(𝑥))
c. ∃x ¬(P(x)  𝑄(𝑥))≡ ¬∀x (P(x)  𝑄(𝑥))
d. ¬∀x (P(x) → 𝑄(𝑥)) ≡ ∀x (P(x)  ¬𝑄(𝑥)
e. ¬∀x (P(x) → 𝑄(𝑥)) ≡ ∃x (P(x)  ¬𝑄(𝑥)

10
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

8. Problema SAT en L1
Ejercicios Resueltos

1. Comprobar la validez de la siguiente Consecuencia Lógica (razonamiento) utilizando la técnica de

Tableaux.
P(a) → ∀x Q(x) ⊨ ∃x (P(a) → Q(x))
Solución:
Hagamos un planteamiento por Refutación y comprobemos que la expresión ɸ = (P(a) → ∀x Q(x))  ∃x
(P(a) → Q(x)) es insatisfacible (contradicción). Por tanto, si ɸ es insatisfacible, P(a) → ∀x Q(x) ⊨ ∃x (P(a)
→ Q(x)) es un razonamiento válido.

(P(a) → ∀x Q(x))  ∃ x (P(a) → Q(x)) La expresión ɸ es una conjunción que

constituye una α-fórmula. Se
-fórmula
construye un nodo nuevo desdoblando
La expresión (P(a) → ∀x P(a) → ∀x Q(x) en serie las dos partes conjuntadas.
Q(x)) es una implicación que ∃x (P(a) → Q(x))
constituye una β-fórmula.
-fórmula
Se abren dos ramas con
nuevos nodos, colocando en P(a) ∀x Q(x) Las expresiones ∀x Q(x) y ¬∃x (P(a) →
cada uno de ellos una de las ∃x (P(a) → Q(x)) ∃x (P(a) → Q(x)) Q(x)) son dos ϒ-fórmulas por lo que
componemos un nuevo nodo
partes disyuntadas. -fórmula -fórmula
manteniendo las expresiones
P(a) ∀x Q(x) cuantificadas universalmente y
∃x (P(a) → Q(x)) ∃x (P(a) → Q(x)) agregando expresiones particularizadas a
 (P(a) → Q(a)) Q(a) una constante. Como ya existe una
-fórmula -fórmula constante en el nodo de partida, la
constante a, particularizamos la variable.
P(a) ∀x Q(x) x por esa constante.
∃x (P(a) → Q(x)) ∃x (P(a) → Q(x))
P(a) Q(a) La expresión ¬(P(a) → Q(a)) es una
 Q(a)  (P(a) → Q(a)) α-fórmula por lo que se construye
un nuevo nodo desdoblando en
-fórmula
serie las dos partes conjuntadas.
∀x Q(x)
∃x (P(a) → Q(x))
Q(a)
P(a)
Q(a) 
Los dos nodos hoja quedan cerrados al existir en ellos literales complementarios, resaltados en rojo en
ambos casos. Por tanto, el Tableau Semántico queda completado y cerrado, lo que la fórmula ɸ es
INSATISFACIBLE y la Consecuencia Lógica que queríamos comprobar es VALIDA.

11
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

2. Comprobar la validez de la siguiente Consecuencia Lógica (razonamiento) utilizando la técnica de

Tableaux.
∃x (P(a) → Q(x)) ⊨ P(a) → ∀x Q(x).
Solución:
Hagamos un planteamiento por Refutación y comprobemos que la expresión ɸ = ∃x (P(a) → Q(x)) 
(P(a) → ∀x Q(x)) es insatisfacible. En el caso que lo sea, el razonamiento será válido.

La expresión ɸ es una ∃x (P(a) → Q(x))  (P(a) → ∀x Q(x))

conjunción que constituye una
-fórmula
α-fórmula. Se construye un
nodo nuevo desdoblando en (P(a) → ∀x Q(x)) La expresión (P(a) → ∀x Q(x))
serie las dos partes conjuntadas. ∃x (P(a) → Q(x)) es la negación de una
implicación lo que constituye
-fórmula
una α-fórmula. Se construye un
Las expresiones ∀x Q(x) y ∃x (P(a) P(a) nodo nuevo desdoblando en
→ Q(x)) son dos δ-fórmulas por lo  ∀x Q(x)) serie las dos partes conjuntadas.
∃x (P(a) → Q(x))
que componemos nuevos nodos, por
separado para sendas fórmulas, δ-fórmula
particularizando la variable x por
constantes que no se encuentren en
P(a)
Q(c)
el nodo inicial. Como ya se encuentra ∃x (P(a) → Q(x))
la constante a, no podremos utilizarla
con lo que para la primera δ-fórmula δ-fórmula
utilizaremos la particularización a la La expresión (P(a) → Q(d)) es una
P(a)
constante c. Para la segunda δ- Q(c) β-fórmula por lo que se abren dos
fórmula, dado que hemos utilizado la P(a) → Q(d) ramas con nuevos nodos,
constante c para la anterior, debemos colocando en cada uno de ellos
utilizar otra nueva constante, por -fórmula
P(a) P(a) una de las partes disyuntadas.
ejemplo, la constante d.
Q(c) Q(c)
P(a) Q(d)
 

Ahora, una vez completado el Tableau Semántico, no queda CERRADO, con lo que la expresión ɸ NO es
INSATISFACIBLE, y por tanto, no podemos decir que la Consecuencia Lógica sea VÁLIDA. Ahora bien, para
concluir que NO sea VÁLIDA, debemos fijarnos en el nodo hoja abierto: Si P(a) y Q(d) son Verdaderos, la
premisa es Verdadero. Pero si Q(c) es Falso, entonces el consecuente es Falso, haciendo NO VÁLIDA la
consecuencia.

12
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

3. Comprobar la validez de la siguiente Consecuencia Lógica (razonamiento) utilizando la técnica de

Tableaux.
∃y ∀x M(x, y) ⊨ ∀x ∃y M(x, y)
Solución:
Hagamos un planteamiento por Refutación y comprobemos que la expresión ɸ = ∃y ∀x M(x, y)  ∀x
∃y M(x, y) es insatisfacible.

∃y ∀x M(x, y)  ∀x ∃y M(x, y) La expresión ɸ es una

-fórmula conjunción que constituye una
α-fórmula. Se construye un
Las expresiones ∃y∀x M(x,y) y ∀x∃y ∃y ∀x M(x, y) nodo nuevo desdoblando en
M(x,y) son dos δ-fórmulas por lo que ∀x ∃y M(x, y) serie las dos partes conjuntadas.
componemos nuevos nodos, por separado
para sendas fórmulas. Particularizando la δ-fórmula
variable y de la primera por constantes que ∀x M(x, b)
no se encuentren en el nodo inicial, por ∀x ∃y M(x, y)
ejemplo, por la constante b. En el caso de
la segunda, particularizamos la variable x δ-fórmula
por la constante a. ∀x M(x, b) Nos encontramos ahora con dos
∃y M(a, y) ϒ-fórmulas. Una cuantificada para
-fórmula la variable x y la otra para la
variable y. Ahora particularizamos
∀x M(x, b) dichas variables por constantes
M(a, b) que se hayan utilizado antes: La
∃y M(a, y) variable x por la constante a, y la
variable y por la constante b.
-fórmula

∀x M(x, b)
M(a, b)
∃y M(a, y)
M(a, b) 
Ahora, una vez completado el Tableau Semántico, su único nodo hoja queda CERRADO, lo que la fórmula ɸ
es INSATISFACIBLE y la Consecuencia Lógica que queríamos comprobar es VÁLIDA.
Si el predicado M(x, y) es “x amigo de y”, la consecuencia lógica planteada es “si uno es amigo de todos,
todos tienen un amigo”.

4. Transformar en Forma Normal Prenexa la siguiente fórmula bien formada:

∀x ∀y [ ∃z P(x,y,z)  ( ∃y Q(x,y) → ∃w Q(y,w) ) ]
Solución:
i. Primero pasamos a forma normal Rectificada
∀x ∀y [ ∃z P(x,y,z)  ( ∃u Q(x,u) → ∃w Q(y,w) ) ]
ii. Paso 1: Eliminar las implicaciones y coimplicaciones (doble implicaciones) A → B ≡ A ∨ B
∀x ∀y [ ∃z P(x,y,z)  (  ∃u Q(x,u) v ∃w Q(y,w) ) ]
iii. Paso 2: Interiorizar las negaciones ∃x P(x) ≡ ∀x P(x)
∀x ∀y [ ∃z P(x,y,z)  ( ∀u Q(x,u) v ∃w Q(y,w) ) ]
iv. Paso 3: Desplazar los cuantificadores al prefijo A  ∃x P(x) ≡ ∃x (A  P(x))
∀x ∀y ∃z ∃w ∀u [ P(x,y,z)  ( Q(x,u) v Q(y,w) ) ]

13
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

5. Transformar en Forma Normal Prenexa la siguiente fórmula bien formada:

∀x ∀y (∃z (P(x, z)  Q(y, z)) → ∃u R(x, y, u))
Solución:
i. Paso 1: Eliminar las implicaciones y coimplicaciones (doble implicaciones) A → B ≡ A ∨ B
∀x ∀y (∃z (P(x, z)  Q(y, z))  ∃u R(x, y, u))
ii. Paso 2: Interiorizar las negaciones
∀x ∀y (∀z  (P(x, z)  Q(y, z))  ∃u R(x, y, u)) ∃x P(x) ≡ ∀x P(x)
∀x ∀y (∀z (P(x, z)  Q(y, z))  ∃u R(x, y, u)) (A  B) ≡ A ∨ B
iii. Paso 3: Desplazar los cuantificadores al prefijo A  ∃x P(x) ≡ ∃x (A  P(x))
∀x ∀y ∃u (∀z (P(x, z)  Q(y, z))  R(x, y, u))
∀x ∀y ∃u ∀z (P(x, z)  Q(y, z)  R(x, y, u))

6. Transforma la siguiente fórmula bien formada en forma Normal de Skolem:

∀x ∃y (P(x, y)  Q(y))
Solución:
i. Averiguamos los ámbitos de los cuantificadores universales
∀x ∃y (P(x, y)  Q(y))
Sólo hay un cuantificador universal que afecta a toda la formula
ii. Averiguamos los ámbitos de los cuantificadores universales
∀x ∃y (P(x, y)  Q(y))
El existencial ∃y está en el ámbito de ∀
iii. Entonces, la variable y cambia por f(x)
Original: ∀x ∃y (P(x, y)  Q(y))
Transformada: ∀x (P(x, f(x))  Q(f(x)))

7. Transforma la siguiente fbf en forma Normal de Skolem

∃x ∀y ( P(x, y)  ∃x ∀z ∃y (Q(y, z)  R(x, y)) )
Solución:
i. Averiguamos los ámbitos de los cuantificadores universales
∃x ∀y ( P(x, y)  ∃x ∀z ∃y ( Q(y, z)  R(x, y) ) )
El ∀y afecta a toda la oración y el ∀z afecta a la parte de la oración ∃y (Q(y, z)  R(x, y)).
ii. Averiguamos los ámbitos de los cuantificadores universales
∃x ∀y (P(x, y)  ∃x ∀z ∃y (Q(y, z)  R(x, y)))
El primer ∃x, no está afectado por ningún ∀, el segundo ∃x está afectado por el ∀y y el ∃y
está efectado por el ∀y y por el ∀z.
iii. Entonces:
La primera variable x cambia por la constante a
La segunda variable x se renombra y cambia por la función f(y)
La segunda variable y se renombra y cambia por la función g(y, z)
Original: ∃x ∀y (P(x, y)  ∃x ∀z ∃y (Q(y, z)  R(x, y)))
Transformada: ∀y (P(a, y)  ∀z (Q(g(y, z), z)  R(f(y), g(y, z))))

14
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

8. Encuentra el unificador más general UMG para el siguiente conjunto:

C = { P(f(a), g(x)), P(y, y) }
Solución:
• La primera discrepancia d1 la encontramos en el primer término {f(a), y}.
• Entonces, intentamos eliminar la discrepancia mediante la sustitución s1 = {f(a)/y} ya que y es una
variable y no está en f(a).
• Al aplicar la sustitución s1 a C unificamos ambos términos obteniendo C1={P(f(a),g(x)), P(f(a),f(a))}.
C1 tiene dos elementos porque no se han unificado el resto de términos.
• La siguiente discrepancia d2 la encontramos en el segundo término {g(x), f(a)}.
• No podemos eliminar la discrepancia porque ambos términos son funciones.
• Por tanto, C no es unificable.

9. Comprobar si el razonamiento es válido por el método de resolución, utilizando la estrategia de conjunto

soporte.
(P(x)  Q(c,x)  S(y,x))  (P(a)  R(z)  S(b,a))  (Q(z,a)  V(a))  (R(x)  V(y))  (P(y)  Q(x,y)) ⊨ V(z)
Solución:
Convertimos las fbf a cláusulas, y como paso final normalizamos las variables por separado (estandarizar).
1. P(x1)  Q(c,x1)  S(y1,x1) Cláusula inicial
2. P(a)  R(z1)  S(b,a) Cláusula inicial
3. Q(z2, a)  V(a) Cláusula inicial
4. R(x2)  V(y2) Cláusula inicial
5. P(y3)  Q(x3,y3) Cláusula inicial
6. V(z3) Conjunto Soporte (CS)
7. R(x2) R(4,6), V(), {y2/z3} (CS) *1

8. Q(x2,a) R(3,6), V(), {a/z3} (CS) *2

9. P(a) R(5,8), Q(), {x2/x3,a/y3} (CS) *3
10. Q(c,a)  S(y1,a) R(1,9), P(),{a/x1} (CS) *4
11. R(z1)  S(b,a) R(2,9), P() (CS) *5
12. S(b,a) R(7,11), R(),{x2/z1} (CS) *6
13. V(a)  S(y1,a) R(3,10), Q(), {c/z2} (CS) *7
14. V(a) R(12,13), S(), {b/y1} (CS) *8
15. □ R(6,14), V(), {a/z3} (CS) *9

Al utilizar reducción al absurdo y llegar a la cláusula vacía el razonamiento es válido

*1
C6 {y2/z3} = V(y2) --- R(4,6) = R(x2)  V(y2)  V(y2) = R(x2)
*2
C6 {a/z3} = V(a) ---- R(3,6) = Q(z2,a)  V(a)  V(a) = Q(z2,a)
*3
C5 {x2/x3,a/y3} = P(a)  Q(x2,a) ---- R(5,8) = P(a)  Q(x2,a)  Q(x2,a) = P(a)
*4
C1 {a/x1} = P(a)  Q(c,a)  S(y1,a) ---- R(1,9) = P(a)  Q(c,a)  S(y1,a)  P(a) = Q(c,a)  S(y1,a)
*5
R(2,9)= P(a)  R(z1)  S(b,a)  P(a) = R(z1)  S(b,a)
*6
C11 {x2/z1} = R(x2)  S(b,a) ---- R(7,11) = R(x2)  R(x2)  S(b,a) = S(b,a)
*7
C3 {c/z2}= Q(c,a)  V(a) ---- R(3,10) = Q(c,a)  V(a)  Q(c,a)  S(y1,a) = V(a)  S(y1,a)
*8
C13 {b/y1}= V(a)  S(b,a) ---- R(12,13) = S(b,a)  V(a)  S(b,a) = V(a)
*9
C6 {a/z3}= V(a) --- R(6,14) = □

15
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

10. Comprobar si el razonamiento es válido por el método de resolución:

(P(x)  Q(c,x)  S(y,x))  (P(a)  R(z)  S(b,a))  (Q(z,a)  V(a))  (R(x)  V(y))  (P(y)  Q(x,y)) ⊨ V(z)
Solución:
1. P(x1)  Q(c,x1)  S(y1,x1) Cláusula inicial
2. P(a)  R(z1)  S(b,a) Cláusula inicial
3. Q(z2,a)  V(a) Cláusula inicial
4. R(x2)  V(y2) Cláusula inicial
5. P(y3)  Q(x3,y3) Cláusula inicial
6. V(z3) Conclusión Negada
7. P(a)  Q(c,a)  R(z1) R(1,2), S(), {b/y1,a/x1}, RF – P *1
8. Q(c,a)  R(z1) R(5,7), P(), {a/y3,c/x3}, RF – Q *2
9. V(a)  R(z1) R(3,8), Q(), {c/z2} *3
10. V(a) R(4,9), Q(), {x2/z1,a/y2}, RF – V *4
11. □ R(6,10), V(), {a/z3} *5
Al utilizar reducción al absurdo y llegar a la cláusula vacía el razonamiento es válido
*1
C1 {b/y1,a/x1} = P(a)Q(c,a)S(b,a) ---- R(1,2) = P(a)Q(c,a)S(b,a)P(a)¬R(z1)S(b,a) = P(a)Q(c,a)R(z1)
*2
C5 {a/y3c/x3}= P(a)  Q(c,a) ---- R(5,7)= P(a)  Q(c,a)  P(a)  Q(c,a)  R(z1) = Q(c,a)  R(z1)
*3
C3 {c/z2}= Q(c,a)  V(a) ---- R(3,8) = Q(c,a)  V(a)  Q(c,a)  R(z1) = V(a)  R(z1)
*4
C4 {x2/z1,a/y2} =R(x2)  V(a), C9 {x2/z1,a/y2} =V(a)  R(x2) ---- R(4,9) = R(x2)  V(a)  V(a)  R(x2) = V(a)
*5
C6 {a/z3} = V(a) ---- R(6,10) = □
11. Validar el siguiente razonamiento utilizando el método de resolución por conjunto Soporte:
∀x (∀y P(y,x) → ∃z Q(z,x)) ⊨ ∀x ∃y (P(y,x) → Q(y,x))
Solución:
Convertimos a Forma Normal de Skolem
• ∀x (∀y P(y,x) → ∃z Q(z,x)) Premisa
∀x (∀y P(y,x)  ∃z Q(z,x)) A → B ≡ A  B, 1
∀x (∃y P(y,x)  ∃z Q(z,x)) ∀x P(x) ≡ ∃x P(x), 2
∀x (P(f(x),x)  Q(g(x),x)) Eliminación de los existenciales
• ∀x ∃y (P(y,x) → Q(y,x)) Negación de la conclusión
∀x ∃y (P(y,x)  Q(y,x)) A → B ≡ A  B, 5
∃x ∃y (P(y,x)  Q(y,x)) ∀x P(x) ≡ ∃x P(x), 6
∃x ∀y (P(y,x)  Q(y,x))  (A  B) ≡ A  B, 7
∃x ∀y (P(y,x)  Q(y,x)) A ≡ A, 8
∀y (P(y,a)  Q(y,a)) Eliminación de los existenciales
Convertimos a cláusulas, normalizamos las variables por separado.
{P(f(x1),x1)  Q(g(x1),x1), P(y1,a), Q(y2,a)}
Aplicamos el Método de Resolución por conjunto Soporte:
1. P(f(x1), x1)  Q(g(x1), x1) Cláusula Inicial
2. P(y1, a) Conjunto Soporte (CS)
3. Q(y2, a) Conjunto Soporte (CS)
4. Q(g(a), a)) R(1,2), P() {f(x1)/y1, a/x1} (CS) *1
5. □ R(3,4), Q() {g(a)/y2} (CS) *2
Al utilizar reducción al absurdo, el razonamiento inicial es válido.
*1
C1 {f(x1)/y1, a/x1)=P(f(a),a)Q(g(a),a), C2 {f(x1)/y1, a/x1)=P(f(a),a) ---- R(1,2)=P(f(a),a)Q(g(a),a))P(f(a),a)=Q(g(a),a))
*2
C3 {g(a)/y2} = Q(g(a),a) ---- R(3,4) = □

16
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

Aplicamos el Método de Resolución por conjunto Soporte mediante grafo:

Cláusula Inicial Cláusulas de la conclusión refutada

P(f(x1)x1)  Q(g(x1) x1) P(y1a) Q(y2a)

{f(x1)/y1,a/x1}

Q(g(a),a)
{g(a)/y2} Conjunto soporte
Resolventes

□
12. Validar el razonamiento y a contestar a la pregunta existencial. El razonamiento es el siguiente:
a. Todo el que ama a los animales es amado por alguien.
b. Cualquiera que mate a un animal no es amado por nadie.
c. Juan ama a todos los animales.
d. Todos los perros son animales.
e. Juan o Luisa mataron al perro, que se llama Coco
f. ¿Alguien mató a Coco?
Solución:
Formalización:
Signatura ={Am/2, An/1, Ma/2, Pe/1}, Constantes: c:”Coco”, j:”Juan”, l:”Luisa”
Am(x,y): “x ama a y”; An(x): “x es un animal”; Ma(x,y): “x mata a y”; Pe(x): “x es perro”
Las expresiones:
a. ∀x ( ∀y (An(y) → Am(x,y)) → ∃z Am(z,x) ) Premisa
b. ∀x ( ∃y (An(y)  Ma(x,y)) →  (∃z Am(z,x)) ) Premisa
c. ∀x (An(x) → Am(j, x)) Premisa
d. ∀x (Pe(x) → An(x)) Premisa
e. Pe(c) Premisa
Ma(j,c)  Ma(l,c) Premisa
f.  ∃x Ma(x, c) Conclusión negada
Convertimos a Forma Normal de Skolem
• ∀x ( ∀y (An(y) → Am(x,y)) → ∃z Am(z,x) ) Premisa
∀x ( ∀y (An(y) → Am(x,y))  ∃z Am(z,x) ) A → B ≡ A  B
∀x ( ∀y (An(y)  Am(x,y))  ∃z Am(z,x) ) A → B ≡ A  B
∀x ( ∃y  (An(y)  Am(x,y))  ∃z Am(z,x) )  ∀x P(x) ≡ ∃x P(x)
∀x ( ∃y (An(y)  Am(x,y))  ∃z Am(z,x) )  (A  B) ≡ A B
∀x ( (An(f(x))  Am(x,f(x)))  Am(g(x),x) ) Eliminar ∃
∀x ( An(f(x))  Am(g(x),x))  (Am(x,f(x))  Am(g(x),x)) ) (B  C)  A ≡ (A  B)  (A  C)
• ∀x (∃y ( An(y)  Ma(x,y) ) →  (∃z Am(z,x)) ) Premisa
∀x ((∃y ( An(y)  Ma(x,y) ) )   (∃z Am(z,x)) ) A → B ≡ A  B
∀x ( (∀y  ( An(y)  Ma(x,y) ) )  ∀z  Am(z,x) )  ∃x P(x) ≡ ∀x P(x)
∀x ( (∀y (An(y)  Ma(x,y))  ∀z  Am(z,x) )  (A  B) ≡ A  B
∀x∀y∀z ( An(y)  Ma(x,y)  Am(z,x) ) Pasar cuantificadores al prefijo
• ∀x (An(x) → Am(j, x)) Premisa
∀x (An(x)  Am(j, x)) A → B ≡ A  B

17
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA
• ∀x (Pe(x) → An(x)) Premisa
∀x (Pe(x) ∨ An(x)) A → B ≡ A  B
• Pe(c) Premisa
• Ma(j, c)  Ma(l, c) Premisa
• ∃x Ma(x, c) Conclusión negada
∀x  Ma(x, c)  ∃x P(x) ≡ ∀x P(x)
Convertimos a cláusulas (normalizamos variables por separado) y aplicamos método de resolución:
1. An(f(x1))  Am(g(x1), x1) Cláusula Inicial
2. Am(x2,f(x2))  Am(g(x2), x2) Cláusula Inicial
3. An(y)  Ma(x3,y)  Am(z, x3) Cláusula Inicial
4. An(x4)  Am(j,x4) Cláusula Inicial
5. Pe(x5)  An(x5) Cláusula Inicial
6. Pe(c) Cláusula Inicial
7. Ma(j,c)  Ma(l,c) Cláusula Inicial
8. Ma(x6,c) Conclusión negada
9. Ma(j,c) R(7,8) M() {l/x6} *1
10. An(c) R(5,6) - Pe() {c/x5} *2
11. Ma(x3,c)  Am(z,x3) R(3,10) - An() {c/y} *3
12. Am(z,j) R(9,11) - Ma() {j/x3} *4
13. Am(g(j),j)  An(f(j)) R(2,4) - Am() {j/x2, f(j)/x4} *5
14. Am(g(j),j) R(1,13) - An(f()) {j/x1} *6
15. □ R(12,14) - An() {g(j)/z} *7
Al utilizar reducción al absurdo y llegar a la cláusula vacía el razonamiento es válido
*1
C8 {l/x6} = Ma(l,c) ---- R(7,8) = Ma(j,c)  Ma(l,c)  Ma(l,c) = Ma(j,c)
*2
C5 {c/x5} = Pe(c)  An(c) ---- R(5,6) = Pe(c)  An(c)  Pe(c) = An(c)
*3
C3 {c/y} =An(c)Ma(x3,c)Am(z, x3) ---- R(3,10)=An(c)Ma(x3,c)Am(z, x3)An(c) = Ma(x3,c)Am(z,x3)
*4
C11 {j/x3} = Ma(j,c)Am(z,j) --- R(9,11) = Ma(j,c)Ma(j,c)Am(z,j) = Am(z,j)
*5
C2 {j/x2} = Am(j, f(j)) ∨ Am(g(j), j); C4 {f(j)/x4} = An(f(j))  Am(j,f(j)) ---- R(2,4) = Am(j,f(j))  Am(g(j),j)
 An(f(j))  Am(j,f(j)) = Am(g(j), j)  An(f(j))
*6
C1 {j/x1} = An(f(j))Am(g(j),j) --- R(1,13) = An(f(j))Am(g(j),j)Am(g(j),j)An(f(j)) = Am(g(j),j)
*7
C12 {g(j)/z} = Am(g(j),j) --- R(12,14)= □
Buscamos la respuesta a la pregunta de ¿Alguien mato a coco?:
1. An(f(x1))  Am(g(x1), x1) Cláusula Inicial
2. Am(x2,f(x2))  Am(g(x2), x2) Cláusula Inicial
3. An(y)  Ma(x3,y)  Am(z, x3) Cláusula Inicial
4. An(x4)  Am(j,x4) Cláusula Inicial
5. Pe(x5)  An(x5) Cláusula Inicial
6. Pe(c) Cláusula Inicial
7. Ma(j,c)  Ma(l,c) Cláusula Inicial
8. Ma(x6,c)  ans(x6) Conclusión negada
9. Ma(j,c)  ans(l) R(7,8) M() {l/x6}
10. An(c) R(5,6) - Pe() {c/x4}
11. ¬Ma(x3,c)  ¬Am(z,x3) R(3,10) - An() {c/y}
12. ¬Am(z,j)  ans(l) R(9,11) - Ma() {j/x3}
13. Am(g(j),j)  ¬An(f(j)) R(2,4) - Am() {j/x2, f(j)/x4}
14. Am(g(j),j) R(1,13) - An(f()) {j/x1}
15. ans(l) R(12,14) - An() {g(j)/z}
Como en ans() nos ha quedado la constante l, Luisa fue quien mató a Coco.

18
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

Construimos su grafo de resolución o refutación

Ma(j,c)Ma(l,c) An(x4)Am(j,x4) An(y)Ma(x3,y)Am(z,x3) Pe(c)

Ma(x6,c) Am(x2,f(x2)Am(g(x2)x2) An(f(x1))Am(g(x1), x1) Pe(x5)An(x5)

{l/x6} {j/x2,f(j)/x4} {c/x5}

Ma(j,c) Am(g(j),j)An(f(j)) An(c)

{j/x1} {c/y}

Am(g(j),j) Ma(x3,c)Am(z,x3)
{j/x3}

Am(z,j)

{g(j)/z}

Construimos su grafo de derivación

Ma(j,c)Ma(l,c) An(x4)Am(j,x4) An(y)Ma(x3,y)Am(z,x3) Pe(c)

Ma(x6,c)ans(x6) Am(x2,f(x2)Am(g(x2)x2) An(f(x1))Am(g(x1), x1) Pe(x5)An(x5)

{l/x6} {j/x2,f(j)/x4}
{c/x5}

Ma(j,c)ans(l) Am(g(j),j)An(f(j)) An(c)

{j/x1} {c/y}

Am(g(j),j) Ma(x3,c)Am(z,x3)
{j/x3}

Am(z,j)ans(l)

{g(j)/z}

ans(l)

19
 1º -- Grado en Ingeniería Informática – Facultad de Informática
Fundamentos Lógicos de la Informática
EJERCICIOS de TEORÍA

Ejercicios Propuestos

1. Utilizando la técnica de los Tableaux semánticos, demostrar si los siguientes conjuntos de fórmulas bien
formadas son satisfacibles.
a) { ∃x Q(x), ∀x (Q(x) → R(x)), ∀x R(x) }
b) { ∃y ∀x P(x, y), ∀x P(x, x) }
c) { ∀x ∀y (P(x, y) → P(y, x)), ∀x P(x, x), ∃x ∃y P(x, y) }
d) { ∀x ∃y P(x, y), ∀x ¬P(x, x)}
2. Utilizando la técnica de Tableaux semánticos, demostrar la validez de los siguientes razonamientos.
a) { ∀x (P(x) → Q(x))  ¬∃x (R(x)  ¬Q(x))} ⊨ ∀x (R(x)→P(x))
b) { ∃x (P(x)  Q(x)) } ⊨ ( ∃x P(x)  ∃x Q(x) )
c) ⊨ ∃x P(x) → ¬∀x ¬P(x)
d) { ∀x (P(x) → Q(x)), ∀x (R(x) → Q(x)), ∀x (P(x)  𝑅(𝑥)) } ⊨ ∀x Q(x)
e) { ∀x (P(x) → Q(x)), P(a)} ⊨ ∃x (Q(x)  𝑅(𝑥))
3. Calcula la forma Normal Prenexa de las siguientes fórmulas bien formadas:
a) ∀x ∀y [ ∃z P(x, y, z)  (∃u Q(x, u) → ∃v Q(x, v)) ]
b) ¬[ ∃x (A(x) → ∀y B(x, y))]
c) ∀x ∀y [ ∃z (A(x, z)  B(y, z)) → ∃u C(x, y, u)]
d) ∀x A(x) → ¬∃u [B(w, z) → C(w, y)]
4. Calcula la forma Normal de Skolem de las siguientes fórmulas bien formadas:
a) ∀x ∃y ∃z [ ( ¬P(x, y)  Q(x, z) )  R(x, y, z) ]
b) ∀x [ (A(x, y) → ∃y P(x, y, z) → ¬∀z Q(x, z) ]
c) ∀x ∃y ∃z [ ( ¬P(x, y)  Q(x, z) )  R(x, y, w) ]
d) ∀x [ ¬P(x, a) → ∃y ( P(y, g(x))  ∀z (P(z, g(x)) →P(y, z))) ]
5. Utiliza la técnica del método de resolución sin conjunto soporte y después realiza la misma técnica pero
con estrategia conjunto soporte e indica si los siguientes razonamientos son válidos. Nota: Observa las
fórmulas para establecerlas si es necesario en forma Normal Prenexa o forma Normal de Skolem.
a) {∀x ∀y ( P(x, y) → Q(y) ), ∀y (¬ Q(y) → R(y)), ∀y ∀x (¬Q(x) → P(x, y))} ⊨ ∃𝑥 𝑅(𝑥)
b) {∀x ( P(x)  ¬R(x)), ∀y (¬ Q(𝑦) → ¬R(y)), ∀y (R(y) → ¬P(y))} ⊨ ∃𝑥 𝑄(𝑥)
c) {∀x ( P(x) → Q(x)), ∀x (R(x)→ Q(x)), ∀x (P(x)  𝑅(𝑥))} ⊨ ∀x Q(x)
d) {∀x ( P(x) → Q(x)), P(a)} ⊨ ∃x (Q(x)  𝑅(𝑥))
6. Partiendo de la formalización dada, resolver cada uno de los siguientes apartados.
“Algunos adultos y todos los niños adoran la navidad. A todos los niños le gustan todos los juguetes. A
María no le gustan los juguetes. Luis no adora la Navidad, Luego, alguien no es un niño. ¿Quién no es un
niño?”
Signatura: ∑ = { A/1,N/1,F/2,J/1,G/2, m,n,l constantes } donde A(x): ‘x es adulto’, N(x): ’x es niño’,
J(x): ’x es juguete’, G(x,y): ’a x le gusta y’, F(x,y): ’x adora y’, m: ‘María’, l: ’Luis’, n: ’Navidad’.
ϕ=∃x∀y ((A(x)→F(x, n))(N(y)→F(y, n))) , ∀x(N(x)→∀y(J(y)→G(x, y)),
∀x, (J(x)→¬G(m, x)), F(l, n)} ⊨ ∃x¬N(x){
a) Realiza la forma normal Prenexa del razonamiento ϕ, incluyendo a la conclusión correctamente
representada para validar el razonamiento.
b) Realiza la forma normal de Skolem del razonamiento obtenido en el apartado anterior.
c) Aplica el Método de Resolución por conjunto soporte para demostrar si el razonamiento
planteado es correcto. Recuerda detallar todos los pasos correctamente.
d) Responde a la pregunta aplicando la técnica de resolución de preguntas del método de resolución,
¿Quién no es niño?

20