R8

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:

---

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: