R7 sol
De Lógica informática (2014-15)
Relación 7: Temas 1 a 6
Ejercicio 1. Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes sentencias:
- Si S es consistente y T es inconsistente, entonces S ∪ T es consistente.
- Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
- Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
- Si S es consistente y T es inconsistente, entonces S ∩ T es inconsistente.
Solución:
Para este ejercicio basta tener presente que
- Si S ⊆ T y T es consistente, entonces S es consistente.
- Si S ⊆ T y S es inconsistente, entonces T es inconsistente.
- S ⊆ S ∪ T
- T ⊆ S ∪ T
- S ∩ T ⊆ S
- S ∩ T ⊆ T
- Apartado 1: Es falso, ya que T es es inconsistente y T ⊆ S ∪ T (por 3); luego, S ∪ T es inconsistente (por 2).
- Apartado 2 Es cierto, por el apartado 1.
- Apartado 3: Es cierto, ya que S es consistente y S ∩ T ⊆ S (por 5); luego, S ∩ T es consistente (por 1).
- Apartado 4: Es falso, por el apartado 3.
Ejercicio 2. Demostrar por deducción natural, tableros semánticos y resolución
- ¬(p ∧ ¬q) ⊧ p → q
Solución:
Por deducción natural
1. ¬(p ∧ ¬q) Prem ┌─────────────┐ │ 2. p │ Sup │┌───────────┐│ ││ 3. ¬q ││ Sup ││ 4. p ∧ ¬q ││ ∧I 2,3 ││ 5. ⊥ ││ ¬E 1,4 │└───────────┘│ │ 6. q │ RAA 3-5 └─────────────┘ 7. p → q →I 2-6
Por tablero semántico
1 ¬(p ∧ ¬q)
2 ¬(p → q)
3 p (2)
4 ¬q (2)
┌─────┴─────┐
5 ¬p (1) 6 ¬¬q (1)
C 5,3 C 6,4
Por resolución
Primero se transforma las fórmulas a cláusulas
¬(p ∧ ¬q) ≡ ¬p ∨ ¬¬q
≡ ¬p ∨ q
≡ {[¬p, q]}
¬(p → q) ≡ p ∧ ¬q
≡ {{p}, {¬q}}
La resolución es
{¬p,q} {p} {¬q}
└──┬──┘ │
{q} │
└───┬──┘
□
Ejercicio 3. Un pirata se encuentra con cuatro cofres y una inscripción en cada uno de ellos. En el primer cofre dice "El tesoro no está aquí". En el segundo, dice "El tesoro está en el cofre 3". En el tercero dice "El cofre 1 dice la verdad". Y, en el cuarto dice "El cofre 2 miente". Ayuda al pirata a encontrar el tesoro, sabiendo que de los tres letreros, al menos tres mienten.
Solución:
Se usarán las siguientes variables
- ci (1 ≤ i ≤ 4) representa que el cartel de cofre i dice la verdad
- ti (1 ≤ i ≤ 4) representa que el el tesoro está en el cofre i.
La formalización del problema es
- c1 ↔ ¬t1
- c2 ↔ t3
- c3 ↔ c1
- c4 ↔ ¬c2
- ¬(c1 ∧ c2)
- ¬(c1 ∧ c3)
- ¬(c1 ∧ c4)
- ¬(c2 ∧ c3)
- ¬(c2 ∧ c4)
- ¬(c3 ∧ c4)
- ¬(t1 ∧ t2)
- ¬(t1 ∧ t3)
- ¬(t1 ∧ t4)
- ¬(t2 ∧ t3)
- ¬(t2 ∧ t4)
- ¬(t3 ∧ t4)
- t1 ∨ t2 ∨ t3 ∨ t4
Para buscar modelos usamos Mace4. La lista de fórmulas es
c1 <-> -t1. c2 <-> t3. c3 <-> c1. c4 <-> -c2. -(c1 & c2). -(c1 & c3). -(c1 & c4). -(c2 & c3). -(c2 & c4). -(c3 & c4). -(t1 & t2). -(t1 & t3). -(t1 & t4). -(t2 & t3). -(t2 & t4). -(t3 & t4). t1 | t2 | t3 | t4.
La búsqueda de modelos devuelve
relation(c1, [ 0 ]), relation(c2, [ 0 ]), relation(c3, [ 0 ]), relation(c4, [ 1 ]), relation(t1, [ 1 ]), relation(t2, [ 0 ]), relation(t3, [ 0 ]), relation(t4, [ 0 ])
Lo que indica que el tesoro está en el cofre 1. Vamos a demostrarlo, por deducción natural:
1 c1 ↔ ¬t1 2 c2 ↔ t3 3 c3 ↔ c1 4 c4 ↔ ¬c2 5 ¬(c1 ∧ c2) 6 ¬(c1 ∧ c3) 7 ¬(c1 ∧ c4) 8 ¬(c2 ∧ c3) 9 ¬(c2 ∧ c4) 10 ¬(c3 ∧ c4) 11 ¬(t1 ∧ t2) 12 ¬(t1 ∧ t3) 13 ¬(t1 ∧ t4) 14 ¬(t2 ∧ t3) 15 ¬(t2 ∧ t4) 16 ¬(t3 ∧ t4) 17 t1 ∨ t2 ∨ t3 ∨ t4 ┌─────────────┐ │ 18 ¬t1 │ Sup │ 19 ¬t1 → c1 │ ↔E₂ 1 │ 20 c1 │ →E 19,18 │ 21 c1 → c3 │ ↔E₂ 1 │ 22 c3 │ →E 21,20 │ 23 c1 ∧ c3 │ ∧I 20,22 │ 24 ⊥ │ ¬E 6,23 └─────────────┘ 25 t1 RAA 18-25
Ejercicio 4. Decidir, utilizando formas normales, si la fórmula
- (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.
Solución: Para decidir si es tautología se calcula la FNC
(p → ¬(q → ¬r)) ∧ (r → ¬q) ≡ (p → (q ∧ ¬¬r)) ∧ (¬r ∨ ¬q) ≡ (¬p ∨ (q ∧ r)) ∧ (¬r ∨ ¬q) ≡ (¬p ∨ q) ∧ (¬p ∨ r) ∧ (¬r ∨ ¬q)
Por tanto, no es tautología ya que la interpretación I con I(p)=1 e I(q)=0 es un contramodelo. En efecto,
(p → ¬(q → ¬r)) ∧ (r → ¬q) 1 0 0 0 1 0
Para decidir si es insatisfactible se calcula la FND
(p → ¬(q → ¬r)) ∧ (r → ¬q) ≡ (p → (q ∧ ¬¬r)) ∧ (¬r ∨ ¬q) ≡ (¬p ∨ (q ∧ r)) ∧ (¬r ∨ ¬q) ≡ (¬p ∧ (¬r ∨ ¬q)) ∨ ((q ∧ r) ∧ (¬r ∨ ¬q)) ≡ ((¬p ∧ ¬r) ∨ (¬p ∧ ¬q)) ∨ ((q ∧ r ∧ ¬r) ∨ (q ∧ r ∧ ¬q)) ≡ (¬p ∧ ¬r) ∨ (¬p ∧ ¬q)
Por tanto, no es insatisfacible ya que la interpretación I con I(p)=0 e I(r)=0 es un modelo. En efecto,
(p → ¬(q → ¬r)) ∧ (r → ¬q) 0 1 1 0 1
Ejercicio 5. Decidir, usando el algoritmo DPLL y resolución, si el conjunto de cláusulas
- {{p,r,¬s}, {¬q,s}, {¬p,¬s,¬r}, {¬p,s,q}, {s,q,p}, {¬q,¬r}, {¬s,¬r,p}}
es consistente. En caso de que lo sea, proporcionar un modelo del mismo.
Solución:
Por el algoritmo DPLL.
Sea S = {{p,r,¬s}, {¬q,s}, {¬p,¬s,¬r}, {¬p,s,q},{s,q,p}, {¬q,¬r}, {¬s,¬r,p}}. No tiene cláusulas unitarias ni literales puros. Elegimos el literal p para dividir los casos.
Primer caso:
S ∪ {p}
= {{p,r,¬s}, {¬q,s}, {¬p,¬s,¬r}, {¬p,s,q}, {s,q,p}, {¬q,¬r}, {¬s,¬r,p}, {p}}
= { {¬q,s}, {¬s,¬r}, {s,q}, {¬q,¬r}, } [Unit. p]
= { {¬q,s}, {s,q}, } [Puro ¬r]
= { } [Puro s]
Por tanto, S es consistente y un modelo es la interpretación I con I(p)=1, I(r)=0 e I(s)=1. En efecto,
{{p,r,¬s}, {¬q,s}, {¬p,¬s,¬r}, {¬p,s,q}, {s,q,p}, {¬q,¬r}, {¬s,¬r,p}}
1 1 10 1 1 10 1
Por resolución:
{p,r,¬s}¹ {¬q,s}² {¬p,¬s,¬r}³ {¬p,s,q}⁴ {s,q,p}⁵ {¬q,¬r}⁶ {¬s,¬r,p}⁷
║ ║ ║ ╙───┬───╜ ║ ║
║ ║ ║ {s,q}⁸ ║ ║
║ ╙────────║────────────────╢ ║ ║
║9 ║9 {s}⁹ ║ ║9
{p,r}¹⁰ {¬p,¬r}¹¹ ║ {¬r,p}¹²
╟────────────────║─────────────────────────────║─────────╜
{p}¹³ ║13 ║
{¬r}¹⁴ ║14
{ }¹⁵
Por tanto, S es consistente y un modelo es la interpretación I tal que I(p)=1, I(r)=0 e I(s)=1.