Relación 7

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:

De Lógica informática (2014-15)

Relación 7: Temas 1 a 6