R8
De Lógica informática (2014-15)
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: