Lógica informática (2014-15) - Contribuciones del usuario [es]

Relación 8

2014-11-16T11:19:29Z

Javgarcal: /* Relación 8: Temas 1 a 7 */

=== Relación 8: Temas 1 a 7 ===

----
'''Ejercicio 1.''' Decidir, mediante resolución, DPLL y tableros semánticos, si
: {p → q, ¬p → r, q ∨ r → s} ⊧ s

En caso afirmativo, probarlo por deducción natural.

----

'''Solución:'''
RES:
p → q

≡ ¬p v q

1: {¬p, q}

¬p → r

≡ ¬¬p v r

≡ p v r

2: {p, r}

q v r → s

≡ ¬(q v r) v s

≡ (¬q ^ ¬r) v s

≡ (¬q v s) ^ (¬r v s)

3: {¬q, s}

4: {¬r, s}

¬s

5: {¬s}

{¬p, q} {p, r} {¬q, s} {¬r, s} {¬s}

res ({¬s}, {¬q, s}) = {¬q}

res ({¬s}, {¬r, s}) = {¬r}

res ({¬r}, {p, r}) = { p}

res ({p}, {¬p, q}) = { q}

res ({q}, {¬q}) = []

DPLL:

{{¬p, q} {p, r} {¬q, s} {¬r, s} {¬s}}

~ {{¬p, q} {p, r} {¬q} {¬r}} UNITARIA {¬s}

~ {{¬p, q} {p} {¬q}} UNITARIA {¬r}

~ {{¬p {p}} UNITARIA {¬q}

~ {[]} UNITARIA {p}

TS:

1. p → q
2. ¬p → r
3. q v r → s
4. ¬s
5. ¬(q v r) (3) 6. s (3)
7. ¬q (5) *(4,6)
8. ¬r (5)
9. ¬p (1) 10. q (1)
11. p (2) 12. r (2) *(7,10)
*(9,11) *(8,12)

----
'''Ejercicio 2.''' Decidir, utilizando formas normales, tableros semánticos,
resolución y DPLL, si la fórmula
: (q → p ∧ r) ∨ ¬(p ↔ p ∨ q)

es una tautología.

----

'''Solución:'''

----
'''Ejercicio 3.''' Demostrar o refutar las siguientes proposiciones:
* Sean G₁ una forma normal disyuntiva de F₁ y G₂ una forma normal disyuntiva de F₂. Si F₁ y F₂ son equivalentes, entonces G₁ y G₂ son fórmulas iguales.
* Para toda fórmula F se tiene que si G₁ es una forma normal conjuntiva de F y G₂ es una forma normal normal disyuntiva de F, entonces G₁ y G₂ son fórmulas distintas.

----

'''Solución:'''

----
'''Ejercicio 4.''' Demostrar, por deducción natural, que la siguiente fórmula es insatisfacible:

: (¬p ∨ q) ∧ (p ∧ ¬q)

----

'''Solución:'''

----

'''Ejercicio 5.''' Formalizar las siguiente sentencias utilizando los símbolos indicados:
* Los chinos tienen como máximo un hijo.
: (Símbolos: C(x) representa que x es chino y H(x, y) representa que x es hijo de y).
* Hay exactamente un participante.
: (Símbolos: P(x) representa que x es un participante).
* Ningún socio del club está en deuda con el tesorero del club.
: (Símbolos: S(x) representa que x es socio del club, D(x, y) representa que x está en deuda con y y a representa al tesorero del club).
* No hay ningún pez que se coma a todos los peces.
: (Símbolos: P(x) representa que x es un pez y C(x, y) representa que x se come a y).

----

'''Solución:'''

Relación 8

2014-11-16T11:14:00Z

Javgarcal: /* Relación 8: Temas 1 a 7 */

=== Relación 8: Temas 1 a 7 ===

----
'''Ejercicio 1.''' Decidir, mediante resolución, DPLL y tableros semánticos, si
: {p → q, ¬p → r, q ∨ r → s} ⊧ s

En caso afirmativo, probarlo por deducción natural.

----

'''Solución:'''
RES:
p → q

≡ ¬p v q

1: {¬p, q}

¬p → r

≡ ¬¬p v r

≡ p v r

2: {p, r}

q v r → s

≡ ¬(q v r) v s

≡ (¬q ^ ¬r) v s

≡ (¬q v s) ^ (¬r v s)

3: {¬q, s}

4: {¬r, s}

¬s

5: {¬s}

{¬p, q} {p, r} {¬q, s} {¬r, s} {¬s}

res ({¬s}, {¬q, s}) = {¬q}

res ({¬s}, {¬r, s}) = {¬r}

res ({¬r}, {p, r}) = { p}

res ({p}, {¬p, q}) = { q}

res ({q}, {¬q}) = []

DPLL:

{{¬p, q} {p, r} {¬q, s} {¬r, s} {¬s}}

�~ {{¬p, q} {p, r} {¬q} {¬r}} UNITARIA {¬s}

�~ {{¬p, q} {p} {¬q}} UNITARIA {¬r}

�~ {{¬p {p}} UNITARIA {¬q}

�~ {[]} UNITARIA {p}

----
'''Ejercicio 2.''' Decidir, utilizando formas normales, tableros semánticos,
resolución y DPLL, si la fórmula
: (q → p ∧ r) ∨ ¬(p ↔ p ∨ q)

es una tautología.

----

'''Solución:'''

----
'''Ejercicio 3.''' Demostrar o refutar las siguientes proposiciones:
* Sean G₁ una forma normal disyuntiva de F₁ y G₂ una forma normal disyuntiva de F₂. Si F₁ y F₂ son equivalentes, entonces G₁ y G₂ son fórmulas iguales.
* Para toda fórmula F se tiene que si G₁ es una forma normal conjuntiva de F y G₂ es una forma normal normal disyuntiva de F, entonces G₁ y G₂ son fórmulas distintas.

----

'''Solución:'''

----
'''Ejercicio 4.''' Demostrar, por deducción natural, que la siguiente fórmula es insatisfacible:

: (¬p ∨ q) ∧ (p ∧ ¬q)

----

'''Solución:'''

----

'''Ejercicio 5.''' Formalizar las siguiente sentencias utilizando los símbolos indicados:
* Los chinos tienen como máximo un hijo.
: (Símbolos: C(x) representa que x es chino y H(x, y) representa que x es hijo de y).
* Hay exactamente un participante.
: (Símbolos: P(x) representa que x es un participante).
* Ningún socio del club está en deuda con el tesorero del club.
: (Símbolos: S(x) representa que x es socio del club, D(x, y) representa que x está en deuda con y y a representa al tesorero del club).
* No hay ningún pez que se coma a todos los peces.
: (Símbolos: P(x) representa que x es un pez y C(x, y) representa que x se come a y).

----

'''Solución:'''

Relación 8

2014-11-16T11:06:41Z

Javgarcal: /* Relación 8: Temas 1 a 7 */

=== Relación 8: Temas 1 a 7 ===

----
'''Ejercicio 1.''' Decidir, mediante resolución, DPLL y tableros semánticos, si
: {p → q, ¬p → r, q ∨ r → s} ⊧ s

En caso afirmativo, probarlo por deducción natural.

----

'''Solución:'''
RES:
p → q

≡ ¬p v q

1: {¬p, q}

¬p → r

≡ ¬¬p v r

≡ p v r

2: {p, r}

q v r → s

≡ ¬(q v r) v s

≡ (¬q ^ ¬r) v s

≡ (¬q v s) ^ (¬r v s)

3: {¬q, s}

4: {¬r, s}

¬s

5: {¬s}

{¬p, q} {p, r} {¬q, s} {¬r, s} {¬s}

res ({¬s}, {¬q, s}) = {¬q}

res ({¬s}, {¬r, s}) = {¬r}

res ({¬r}, {p, r}) = { p}

res ({p}, {¬p, q}) = { q}

res ({q}, {¬q}) = []

----
'''Ejercicio 2.''' Decidir, utilizando formas normales, tableros semánticos,
resolución y DPLL, si la fórmula
: (q → p ∧ r) ∨ ¬(p ↔ p ∨ q)

es una tautología.

----

'''Solución:'''

----
'''Ejercicio 3.''' Demostrar o refutar las siguientes proposiciones:
* Sean G₁ una forma normal disyuntiva de F₁ y G₂ una forma normal disyuntiva de F₂. Si F₁ y F₂ son equivalentes, entonces G₁ y G₂ son fórmulas iguales.
* Para toda fórmula F se tiene que si G₁ es una forma normal conjuntiva de F y G₂ es una forma normal normal disyuntiva de F, entonces G₁ y G₂ son fórmulas distintas.

----

'''Solución:'''

----
'''Ejercicio 4.''' Demostrar, por deducción natural, que la siguiente fórmula es insatisfacible:

: (¬p ∨ q) ∧ (p ∧ ¬q)

----

'''Solución:'''

----

'''Ejercicio 5.''' Formalizar las siguiente sentencias utilizando los símbolos indicados:
* Los chinos tienen como máximo un hijo.
: (Símbolos: C(x) representa que x es chino y H(x, y) representa que x es hijo de y).
* Hay exactamente un participante.
: (Símbolos: P(x) representa que x es un participante).
* Ningún socio del club está en deuda con el tesorero del club.
: (Símbolos: S(x) representa que x es socio del club, D(x, y) representa que x está en deuda con y y a representa al tesorero del club).
* No hay ningún pez que se coma a todos los peces.
: (Símbolos: P(x) representa que x es un pez y C(x, y) representa que x se come a y).

----

'''Solución:'''

Relación 7

2014-11-16T10:31:45Z

Javgarcal: /* Relación 7: Temas 1 a 6 */

=== 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:'''
1. Suponemos:
S = {p}
T = {p ^ ¬p}

Por tanto

S U T = {p, p ^ ¬p}

Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto.
Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.

2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.

3. Suponemos:
S = {p}
T = {p ^ ¬p, p}

Por tanto

S ∩ T = {p}

En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.

{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.

4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
----
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución
: ¬(p ∧ ¬q) ⊧ p → q
----

'''Solución:'''
DN:
1. ¬(p ^ ¬q) prem. hqd p → q

2. p sup.
3. q v ¬q LEM

4. q sup.
5. p → q →i 2-4

6. ¬q sup.
7. p ^ ¬q ^i 2,6
8. contradicción ¬e 1,7
9. p → q eliminación de lo falso 8

10. p → q ve 3, 4-5, 6-9

11. p → q →i 2-10

TS:
1. ¬(p ^ ¬q)
2. ¬(p → q)

3. p (2)
4. ¬q (2)
5. ¬p (1) 6. ¬¬q (1)
*(3,5) 7. q (6)
*(4,6)

RES:

¬(p ^ ¬q)

≡ ¬p v ¬¬q

≡ ¬p v q

{ {¬p, q} }

¬(p → q)

≡ p ^ ¬q

{ {p}, {¬q} }

1: {¬p, q}
2: {p}
3: {¬q}

res(1, 2) = {q} 4

res(3, 4) = []

----
'''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 cuatro letreros, al menos tres mienten.

----

'''Solución:'''

----
'''Ejercicio 4.''' Decidir, utilizando formas normales, si la fórmula
: (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.

----

'''Solución:'''

(p → ¬(q → ¬r)) ∧ (r → ¬q)

≡ (¬p v ¬(q → ¬r)) ^ (¬r v ¬q)

≡ (¬p v (q ^ r)) ^ (¬r v ¬q)

FNC: ≡ (¬p v q) ^ (¬p v r) ^ (¬r v ¬q)

FND: ≡ (¬p ^ ¬r) v (¬p ^ ¬q) v (q ^ r ^ ¬r) v (q ^ r ^ ¬q)

observando la FNC no hay ninguna cláusula con un literal y su complementario, luego no es una tautología.

si miramos la FND existen cláusulas con un literal y sin su complementario, luego es satisfacible.

----
'''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:'''

Relación 7

2014-11-16T10:25:35Z

Javgarcal: /* Relación 7: Temas 1 a 6 */

=== 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:'''
1. Suponemos:
S = {p}
T = {p ^ ¬p}

Por tanto

S U T = {p, p ^ ¬p}

Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto.
Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.

2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.

3. Suponemos:
S = {p}
T = {p ^ ¬p, p}

Por tanto

S ∩ T = {p}

En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.

{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.

4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
----
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución
: ¬(p ∧ ¬q) ⊧ p → q
----

'''Solución:'''
DN:
1. ¬(p ^ ¬q) prem. hqd p → q

2. p sup.
3. q v ¬q LEM

4. q sup.
5. p → q →i 2-4

6. ¬q sup.
7. p ^ ¬q ^i 2,6
8. contradicción ¬e 1,7
9. p → q eliminación de lo falso 8

10. p → q ve 3, 4-5, 6-9

11. p → q →i 2-10

TS:
1. ¬(p ^ ¬q)
2. ¬(p → q)

3. p (2)
4. ¬q (2)
5. ¬p (1) 6. ¬¬q (1)
*(3,5) 7. q (6)
*(4,6)

RES:

¬(p ^ ¬q)

≡ ¬p v ¬¬q

≡ ¬p v q

{ {¬p, q} }

¬(p → q)

≡ p ^ ¬q

{ {p}, {¬q} }

1: {¬p, q}
2: {p}
3: {¬q}

res(1, 2) = {q} 4

res(3, 4) = []

----
'''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 cuatro letreros, al menos tres mienten.

----

'''Solución:'''

----
'''Ejercicio 4.''' Decidir, utilizando formas normales, si la fórmula
: (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.

----

'''Solución:'''

----
'''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:'''

Relación 7

2014-11-16T10:22:54Z

Javgarcal: /* Relación 7: Temas 1 a 6 */

=== 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:'''
1. Suponemos:
S = {p}
T = {p ^ ¬p}

Por tanto

S U T = {p, p ^ ¬p}

Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto.
Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.

2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.

3. Suponemos:
S = {p}
T = {p ^ ¬p, p}

Por tanto

S ∩ T = {p}

En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.

{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.

4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
----
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución
: ¬(p ∧ ¬q) ⊧ p → q
----

'''Solución:'''
DN:
1. ¬(p ^ ¬q) prem. hqd p → q

2. p sup.
3. q v ¬q LEM

4. q sup.
5. p → q →i 2-4

6. ¬q sup.
7. p ^ ¬q ^i 2,6
8. contradicción ¬e 1,7
9. p → q eliminación de lo falso 8

10. p → q ve 3, 4-5, 6-9

11. p → q →i 2-10

TS:
1. ¬(p ^ ¬q)
2. ¬(p → q)

3. p (2)
4. ¬q (2)
5. ¬p (1) 6. ¬¬q (1)
*(3,5) 7. q (6)
*(4,6)

RES:

¬(p ^ ¬q)
≡ ¬p v ¬¬q
≡ ¬p v q
{{¬p, q}}

¬(p → q)
≡ p ^ ¬q
{{p}, {¬q}}

{¬p, q}1 {p}2 {¬q}3

res(1, 2) = {q}4
res(3, 4) = []

----
'''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 cuatro letreros, al menos tres mienten.

----

'''Solución:'''

----
'''Ejercicio 4.''' Decidir, utilizando formas normales, si la fórmula
: (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.

----

'''Solución:'''

----
'''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:'''

Relación 7

2014-11-16T10:16:18Z

Javgarcal: /* Relación 7: Temas 1 a 6 */

=== 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:'''
1. Suponemos:
S = {p}
T = {p ^ ¬p}

Por tanto

S U T = {p, p ^ ¬p}

Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto.
Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.

2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.

3. Suponemos:
S = {p}
T = {p ^ ¬p, p}

Por tanto

S ∩ T = {p}

En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.

{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.

4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
----
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución
: ¬(p ∧ ¬q) ⊧ p → q
----

'''Solución:'''
DN:
1. ¬(p ^ ¬q) prem. hqd p → q

2. p sup.
3. q v ¬q LEM

4. q sup.
5. p → q →i 2-4

6. ¬q sup.
7. p ^ ¬q ^i 2,6
8. contradicción ¬e 1,7
9. p → q eliminación de lo falso 8

10. p → q ve 3, 4-5, 6-9

11. p → q →i 2-10

TS:
1. ¬(p ^ ¬q)
2. ¬(p → q)

3. p (2)
4. ¬q (2)
5. ¬p (1) 6. ¬¬q (1)
*(3,5) 7. q (6)
*(4,6)

----
'''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 cuatro letreros, al menos tres mienten.

----

'''Solución:'''

----
'''Ejercicio 4.''' Decidir, utilizando formas normales, si la fórmula
: (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.

----

'''Solución:'''

----
'''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:'''

Relación 7

2014-11-16T10:11:45Z

Javgarcal: /* Relación 7: Temas 1 a 6 */

=== 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:'''
1. Suponemos:
S = {p}
T = {p ^ ¬p}

Por tanto

S U T = {p, p ^ ¬p}

Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto.
Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.

2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.

3. Suponemos:
S = {p}
T = {p ^ ¬p, p}

Por tanto

S ∩ T = {p}

En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.

{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.

4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
----
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución
: ¬(p ∧ ¬q) ⊧ p → q
----

'''Solución:'''
DN:
1. ¬(p ^ ¬q) prem. hqd p → q

2. p sup.
3. q v ¬q LEM

4. q sup.
5. p → q →i 2-4

6. ¬q sup.
7. p ^ ¬q ^i 2,6
8. contradicción ¬e 1,7
9. p → q eliminación de lo falso 8

10. p → q ve 3, 4-5, 6-9

11. p → q →i 2-10

----
'''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 cuatro letreros, al menos tres mienten.

----

'''Solución:'''

----
'''Ejercicio 4.''' Decidir, utilizando formas normales, si la fórmula
: (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.

----

'''Solución:'''

----
'''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:'''

Relación 7

2014-11-16T10:10:04Z

Javgarcal: /* Relación 7: Temas 1 a 6 */

=== 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:'''
1. Suponemos:
S = {p}
T = {p ^ ¬p}

Por tanto

S U T = {p, p ^ ¬p}

Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto.
Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.

2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.

3. Suponemos:
S = {p}
T = {p ^ ¬p, p}

Por tanto

S ∩ T = {p}

En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.

{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.

4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
----
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución
: ¬(p ∧ ¬q) ⊧ p → q
----

'''Solución:'''
DN:
1. ¬(p ^ ¬q) prem. hqd p → q

2. p sup.
3. q v ¬q LEM

4. q sup.
5. p → q →i 2-4

6. ¬q sup.
7. p ^ ¬q ^i 2,6
8. contradicción ¬e 1,7
9. p → q eliminación de lo falso 8

10. p → q ve 3, 4-5, 6-9

11. p → q →i 2-10

----
'''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 cuatro letreros, al menos tres mienten.

----

'''Solución:'''

----
'''Ejercicio 4.''' Decidir, utilizando formas normales, si la fórmula
: (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.

----

'''Solución:'''

----
'''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:'''

Archivo:DN.jpg

2014-11-16T09:57:32Z

Javgarcal:

Relación 7

2014-11-16T09:50:42Z

Javgarcal: /* Relación 7: Temas 1 a 6 */

=== 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:'''
1. Suponemos:
S = {p}
T = {p ^ ¬p}

Por tanto

S U T = {p, p ^ ¬p}

Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto.
Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.

2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.

3. Suponemos:
S = {p}
T = {p ^ ¬p, p}

Por tanto

S ∩ T = {p}

En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.

{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.

4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
----
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución
: ¬(p ∧ ¬q) ⊧ p → q
----

'''Solución:'''

----
'''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 cuatro letreros, al menos tres mienten.

----

'''Solución:'''

----
'''Ejercicio 4.''' Decidir, utilizando formas normales, si la fórmula
: (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.

----

'''Solución:'''

----
'''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:'''