Relación 8

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: