Lógica – G‐II, G‐MI, G‐II+ADE

Examen Final, 29 de Junio de 2018

Tiempo para el examen: 2 horas y 30 minutos

1. LP – Formalización / Teoría (1,2 puntos)

1.1 ‐ Formalizar en el lenguaje de la lógica proposicional esta argumentación:

 No sé chino si no voy a la escuela de idiomas o trabajo en China una temporada. No
tengo contactos con la Universidad de Pekín a menos que sepa chino y tenga el
doctorado. Tengo contactos (con la Universidad de Pekín), aunque no tengo el
doctorado. Por consiguiente, voy a la escuela de idiomas.
o p: Sé chino
o q: Voy a la escuela de idiomas
o r: Trabajo en China una temporada
o s: Tengo contactos con la Universidad de Pekín
o t: Tengo el doctorado
o No sé chino si no voy a la escuela de idiomas o trabajo en China una
temporada.

¬ q ∨ r ⟹ ¬ p
o No tendré contactos con la Universidad de Pekín a menos que sepa chino y
tenga el doctorado.
 Saber chino y tener el doctorado, es condición necesaria para tener
contactos con la Universidad de Pekín: s ⟹ p ∧ t
 O, si no sé chino o no tengo el doctorado, entonces no tengo contactos
con la Universidad de Pekín: ¬ p ∨ ¬ t ⟹ ¬ s
o Tengo contactos (con la Universidad de Pekín), aunque no tengo el doctorado.

 s∧¬t
o Por consiguiente, voy a la escuela de idiomas.
 q

{ ¬ q ∨ r ⟹ ¬ p, s ⟹ p ∧ t, s ∧ ¬ t } ⊨ q
1.2 ‐ Decir si la siguiente afirmación es verdadera o falsa, justificando brevemente
la respuesta.
Dos fórmulas A y B son (lógicamente) equivalentes (A ⟺ B, A ≡ B) sii para todo contramodelo
de A i se cumple que i(A) = i(B)
 Falsa: dos fórmulas A y B son (lógicamente) equivalentes (A ⟺ B, A ≡ B) sii para
toda interpretación (sea modelo o contramodelo de A o de B) i se cumple que i(A) =
i(B)

2. LP ‐ Semántica (1,2 puntos)

Demostrar con análisis semántico que NO se cumple la siguiente relación de
consecuencia lógica. Indicar de forma explícita y completa: (1) los pasos
principales del procedimiento y (2) el resultado final obtenido.

{ p ⟹ ¬t, q ∧ s ⟹ r, ¬(q ∧ r) } ⊨ q ∧ t ⟹ ¬p ∧ s
(Nota: no pueden utilizarse ni las tablas de verdad, ni la deducción natural, ni el método de
resolución)

Para demostrar que no se cumple la relación de consecuencia lógica es necesario encontrar al

menos una interpretación de las proposiciones que haciendo verdaderas a las premisas, haga
falsa la conclusión.

1) i(p ⟹ ¬t) = V sii (1.1) i(p) = F o bien (1.2) i(¬t) = V

2) i(q ∧ s ⟹ r) = V sii (2.1) i(q ∧ s) = F o bien (2.2) i(r) = V
3) i(¬(q ∧ r)) = V sii (3.1) i(q) = F o bien (3.2) i(r) = F
4) i(q ∧ t ⟹ ¬p ∧ s) = F sii (4.1) i(q ∧ t) = V y (4.2) i(¬p ∧ s) = F

Por la condición necesaria (4.1) quedan fijados los valores de verdad i(q) = i(t) = V.
Como i(q) = V, entonces (3.1) ya no se puede cumplir, por lo que necesariamente i(r) = F
Como i(t) = V, entonces (1.2) ya no se puede cumplir, por lo que necesariamente i(p) = F
Como i(p) = F, entonces para que se cumpla (4.2) es necesario que i(s) = F
Como i(s) = F, entonces (2.1) se cumple
Por tanto, con la interpretación i(q) = i(t) = V y i(p) = i(r) = i(s) = F tenemos un contramodelo de
la argumentación, al conseguir verificar las condiciones 1), 2), 3) y 4).
 3. LP ‐ Deducción Natural (1,3 puntos)
Demostrar mediante deducción natural, utilizando exclusivamente reglas básicas
(es decir, no está permitido utilizar ninguna regla derivada como Corte, Modus
Tollens, De Morgan, etc…), la siguiente argumentación:

T [ ¬(p ∨ q) ] ⊢ ¬p ∧ ¬q

1. ¬(p ∨ q) Premisa
2. p Supuesto
3. p∨q Int ∨ 2
4. (p ∨ q) ∧ ¬(p ∨ q) Int ∧ 3, 1
5. p → (p ∨ q) ∧ ¬(p ∨ q) Int→ 1‐3
6. ¬p Int¬ 5
7. q Supuesto
8. p∨q Int∨ 7
9. (p ∨ q) ∧ ¬(p ∨ q) Int ∧ 7, 1
10. q → (p ∨ q) ∧ ¬(p ∨ q) Int→ 1‐3
11. ¬q Int¬ 10
12. ¬p ∧ ¬q Int∧ 6, 11

4. LP – Forma Clausular y Resolución (1,3 puntos)

4.1 ‐ Obtener la forma clausular del siguiente conjunto de fórmulas:

{ p ∧ (¬q∨¬r), (¬r∧s) ∨ (r∧¬s), ¬q ⟹ p, p ⟹ r, r ⟹ s∨q }

4.2 ‐ Demostrar por resolución que el conjunto obtenido es insatisfacible.

Transformar a forma clausular:

A1: p(¬q¬r) clausulas 1 y 2

A2: (¬rs) (r¬s) ≡(distribu vidad)

(¬r (r¬s))  (s (r¬s) ≡(distribu vidad)

((¬r r) (¬r ¬s))  ((sr)  (s ¬s) ) ≡ (elim parantesis)

(¬r r) (¬r ¬s)  (sr)  (s ¬s) clausulas 3,4,5,6

A3: ¬q p ≡ (eliminación de →) ¬¬q p≡ (elim ¬¬) q p clausulas 7

A4: pr≡ (eliminación de →)≡¬ pr clausula 8

A5: r sq≡ (eliminación de →)≡ ¬rsq clausula 9

C1: p C2: ¬q¬r C3: ¬rr C4: ¬r¬s C5: sr

C6: s¬s C7: qp C8: ¬pr C9: ¬rsq

Resolución:

R1: r (C1,C8)

R2: ¬q (R1,C2)

R3: ¬s (R1,C4)

R4: ¬rs (R2,C9)

R5: ¬r (R3,R4)

R6: □ (R5,R1)

(C3 Y C6 son tautologías que realmente no se usan en la resolución)

5. LPO – Formalización (1,0 puntos)

Formalizar el razonamiento en el lenguaje de la Lógica de Primer Orden:
 Si nadie me paga no tengo dinero. O tengo dinero o no puedo comprar ninguna
camiseta. Hay una camiseta que me gusta, y que me haría contento ponerme, pero no
la tengo a no ser que la compre. Para ponerse una prenda de ropa es necesario
tenerla. Una camiseta es una prenda de ropa. Por tanto no estoy contento a no ser
que mi primo me pague.

La constante ‘a’ significa “yo”; la constante ‘b’ significa “mi primo”

paga(x,y) significa “x paga a y”

dinero(x) significa “x tiene dinero”

compra(x,y) significa “x compra y”

camiseta(x) significa “x es una camiseta”

gusta(x,y) significa “x le gusta a y”

pone(x,y) significa “x se pone y”

tiene(x,y) significa “x tiene y”

prenda(x) significa “x es una prenda de ropa”

contento(x) significa “x está contento”

 ‐ Si nadie me paga no tengo dinero.

¬∃x paga x,a ⟹ dinero a

‐ O tengo dinero o no puedo comprar ninguna camiseta.

dinero(a) ∨ ∃x camiseta x ∧ compra a,x

‐ Hay una camiseta que me gusta, y que me haría contento ponerme, pero no la tengo a
no ser que la compre.

∃x camiseta x ∧ gusta x,a ∧ pone a,x ⟹contento a ∧

compra a,x ⟹ tiene a,x

‐ Para ponerse una prenda de ropa es necesario tenerla.

∀x ∀y prenda x ⟹ pone y,x ⟹ tiene y,x

‐ Una camiseta es una prenda de ropa.

∀x camiseta x ⟹ prenda x

‐ Por tanto no estoy contento a no ser que mi primo me pague.

⊨ ¬contento(a) ∨ paga(b,a)

NOTAS: ¡no hay una única camiseta en el mundo! Si pone “no me compro ninguna camiseta” y
“hay una camiseta” queda evidente que no puedo introducir una constante ‘c’ que significa
“una camiseta”.

6. LPO ‐ Semántica (1,0 puntos)

Demostrar con análisis semántico que el siguiente razonamiento NO es correcto.
{ ∀x∀y (p(x,y) ∨ ¬q(y,y)), ∃xq(a,x), ∀x (p(x,b)⟹r(x)) } ⊨ r(b)

Necesitamos una interpretación i que haga verdaderas todas las premisas y, a la vez, falsa la
conclusión. El dominio será { 0, 1 } con i(a) = 0 e i(b) = 1.
(1) i( ∀x∀y (p(x,y) ∨ ¬q(y,y)) ) = V sii
(1.1) i( ∀y (p(a,y) ∨ ¬q(y,y)) ) = V sii
(1.1.1) i( p(a,a) ∨ ¬q(a,a) ) = V sii
(1.1.1.1) i(p(a,a)) = V o bien (1.1.1.2) i(q(a,a)) = F
y también
(1.1.2) i( p(a,b) ∨ ¬q(b,b) ) = V sii
(1.1.2.1) i(p(a,b)) = V o bien (1.1.2.2) i(q(b,b)) = F
y también
(1.2) i( ∀y (p(b,y) ∨ ¬q(y,y)) ) = V sii
(1.2.1) i( p(b,a) ∨ ¬q(a,a) ) = V sii
 (1.2.1.1) i(p(b,a)) = V o bien (1.2.1.2) i(q(a,a)) = F
y también
(1.2.2) i( p(b,b) ∨ ¬q(b,b) ) = V sii
(1.2.2.1) i(p(b,b)) = V o bien (1.2.2.2) i(q(b,b)) = F

(2) i( ∃xq(a,x) ) = V sii

(2.1) i(q(a,a)) = V o bien (2.2) i (q(a,b)) = V

(3) i( ∀x (p(x,b)⟹r(x)) ) = V sii

(3.1) i(p(a,b) ⟹ r(a)) = V sii
(3.1.1) i(p(a,b)) = F o bien (3.1.2) i(r(a)) = V
y también
(3.2) i(p(b,b) ⟹ r(b)) = V sii
(3.2.1) i(p(b,b)) = F o bien (3.2.2) i(r(b)) = V

(4) i(r(b)) = F

Después de haber explicitado las condiciones, lo siguiente es ver si son compatibles (es decir, si
existe esta i).

‐ La condición (4) es incompatible con (3.2.2); al ser la primer obligatoria, eliminamos

(3.2.2)
‐ Ahora (3.2.1) es obligatoria, y es incompatible con (1.2.2.1); eliminamos (1.2.2.1)
‐ Ahora (1.2.2.2) es obligatoria

Entonces un posible contraejemplo (no el único) es i tal que

‐ i(p(a,a)) = i(p(a,b)) = i(p(b,a)) = V; i(p(b,b)) = F
‐ i(q(a,a)) = i(q(a,b)) = i(q(b,a)) = V; i(q(b,b)) = F
‐ i(r(a)) = V; i(r(b)) = F

7. LPO – Deducción Natural (1,0 puntos)

Demostrar la siguiente deducción con el cálculo de Deducción Natural,
justificando adecuadamente cada paso:
T [ ∀x∃y P(x,f(y)) ∨ ¬∃xQ(x), ∃x∀y(P(x,f(y)) ⟹ R(y)), P(b,f(a)) ]
⊢ Q(b) ⟹ ∃xR(x)

1. ∀x∃y P(x,f(y)) ∨ ¬∃xQ(x) premisa

2. ∃x∀y(P(x,f(y)) → R(y)) premisa
3. P(b,f(a)) premisa
4. Q(b) supuesto
 5. ∃xQ(x) introducción ∃x línea 4
6. ¬¬∃xQ(x) Intercambio línea 5 (A ⟺ ¬¬A)
7. ∀x∃y P(x,f(y)) corte 1,6
8. ∀y(P(a*,f(y)) → R(y)) elim ∃ línea 2 x/a*
9. ∃y P(a*,f(y)) elim ∀ línea 7 x/a*
10. P(a*,f(b*)) elim ∃ línea 9 y/b*
11. P(a*,f(b*)) → R(b*) elim ∀ línea 8 y/b*
12. R(b*) elim → líneas 10,11
13. ∃xR(x) introducción ∃x línea 12
14. Q(b)→ ∃xR(x) introd → líneas 3,13

8. LPO – Forma Clausular (0,8 puntos)

Obtener la forma clausular de la siguiente estructura deductiva T[P1] C. Indicar
los pasos principales del proceso de transformación y el resultado final.

P1 : ∀x(∃yM(x,y) ⟹ (R(x,y) ∨ S(a)))

C: ∃xP(x) ⟹ (M(c,y) ∧ Q(z))

P1.
∀x(∃yM(x,y)→ (R(x,y) ∨ S(a))
∀x(∃yM(x,y)→ (R(x,z) ∨ S(a))
∀x∀y(M(x,y)→ (R(x,z) ∨ S(a))
∀x∀y(¬M(x,y) ∨ R(x,z) ∨ S(a)) (forma prenex)
∃z ∀x∀y(¬M(x,y) ∨ R(x,z) ∨ S(a)) (CE)
∀x∀y(¬M(x,y) ∨ R(x,b) ∨ S(a)) (FNC)
{¬M(x,y) ∨ R(x,b) ∨ S(a)} FC
¬C.
¬(∃xP(x) → (M(c,y) ∧ Q(z)))

∃xP(x) ∧ ¬(M(c,y) ∧ Q(z))

∃xP(x) ∧ (¬M(c,y) ∨ ¬Q(z))

∃x(P(x) ∧ (¬M(c,y) ∨ ¬Q(z))) (forma prenex)

∃y∃x(P(x) ∧ (¬M(c,y) ∨ ¬Q(z)))

∃z∃y∃x(P(x) ∧ (¬M(c,y) ∨ ¬Q(z))) (CE)

P(d) ∧ (¬M(c,e) ∨ ¬Q(i)) (FS)

{P(d), ¬M(c,e) ∨ ¬Q(i)} (FC)

{ ¬M(x,y) ∨ R(x,b) ∨ S(a), ¬P(d), ¬M(c,e) ∨ ¬Q(i) }

9. LPO – Resolución con UMG (1,2 puntos)

Demostrar, mediante el método de resolución con UMG, que la siguiente
estructura deductiva es correcta:

T[C1, C2, C3, C4, C5] ⊢ ∃x∀y(¬Q(x,y) ∧ ¬R(x))

C1: R(x) ∨ P(x) ∨ ¬S(f(x))
C2: R(x) ∨ P(x) ∨ ¬Q(f(x),y)
C3: ¬P(x)
C4: ¬R(x)
C5: ¬S(a)

Se renombran las variables:

C1: R(x1) ∨ P(x1) ∨ S(f(x1))
C2: R(x2) ∨ P(x2) ∨ ¬Q(f(x2),y2)
C3: ¬S(a)
C4: ¬P(x4)
C5: ¬R(x5)

Se hace la forma clausular de la negación de la conclusión

C6: Q(x6,g(x6)) ∨ R(x6)

Para que el conjunto sea insatisfacible debe existir una derivación que permita llegar a la
cláusula vacía:

C2: R(x2) ∨ P(x2) ∨ ¬Q(f(x2),y2) C4: ¬P(x4)

{x2/x4}
R1: R(x4) ∨ ¬Q(f(x4),y2) C5: ¬R(x5)

{ x4/x5}
R2: ¬Q(f(x5),y2) C6: Q(x6,g(x6)) ∨ R(x6)

{ x6/f(x5),y2/g(f(x5))}
R3: R(f(x5)) C’5: ¬R(x7)

{ x7/f(x5)}
R4: 
Hemos encontrado la cláusula vacía , luego el conjunto de cláusulas es insatisfacible. La
estructura deductiva es correcta.