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:

∀x (C(x)∧∃y H(x,y)→∀z(H(x,z)→z=y))
∀x (P(x)→∀y(P(y)→y=x)
¬∃x (S(x)∧D(x,a))
¬∃x (P(x)∧∀y (C(x,y)))

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

Relación 8: Temas 1 a 7