Jalonso en 19:26 16 nov 2014

2014-11-16T19:26:18Z

Jalonso: Página creada con '=== 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 incon...'

2014-11-16T19:24:49Z

Página creada con '=== 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 incon...'

Página nueva

=== 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.

@@ Línea 261: / Línea 261: @@
       {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.

R7 sol - Historial de revisiones

Jalonso en 19:26 16 nov 2014

Jalonso: Página creada con '=== 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 incon...'