Download Lógica Computacional

Lógica Computacional - Seminari 1
1. Escribe las siguientes oraciones como formulas en lógica proposicional usando
variables proposicionales para representar las oraciones atómicas, es decir las
oraciones que no están hechas de otras oraciones:
(a) Si el Sr. López esta feliz, la Sra. López esta infeliz,
y si el Sr. López esta infeliz, la Sra. López esta feliz.
(b) Si X es positivo, X+2 es positivo.
(c) Voy al cine si y solo si hay una comedia en cartelera.
(d) Si la criatura tiene orejas largas y dientes grandes, es un conejo.
(e) La criatura tiene orejas largas, dientes largos y no es un conejo.
2. Para cada una de las siguientes formulas (a) escribe su tabla de verdad y di si es
una tautología, contradicción o fórmula mixta.
(a) ¬(p) ∧ q
(b) (p ∧ q) → p
(c) p ↔ (¬p ∨ (q ∧ ¬p))
(d) (p → q) ∧ (r → q)
(e) (q → p) → (r → (q → p))
(f) r → (((p → q) → r) →r)
(g) ¬ (p →q → (¬p ∨ q))
3.
(a) Expresa p → q y p∧q usando solo ¬ y ∨
(b) Expresa p → q y p∨q usando solo ¬ y ∧
4. Son las siguientes 2 formulas equivalentes?
p ∨ (p ∧ (¬ p ∨ q )) ∨ q
p∨q
5. Clasifica las siguientes fórmulas entre válidas, satisfacibles, e insatisfacibles:
(a) p
(b) (p∧¬q)
(c) (p∧¬p)
(d) (p∨¬p)
(e) (p→p)
(f) ¬(p→p)
(g) ((p→q)→p)
(h) (p→¬p)
6. Verifica formalmente si los siguientes argumentos son validos:
(a) Si no hay control de nacimientos, entonces la población crece ilimitadamente.
Pero si la población crece ilimitadamente, aumentará el índice de pobreza. Por
consiguiente, si no hay control de nacimientos, aumentara el índice de pobreza.
(b) Si los jóvenes socialistas españoles apoyan a Almunia, entonces renuncian a su
programa de reivindicaciones. Y si no apoyan a Almunia, entonces favorecen a
Aznar. Pero una de dos: o apoyan a Almunia o no lo apoyan. Por consiguiente,
habrán de renunciar a su programa de reivindicaciones o favorecer a Aznar.
7. Prueba el siguiente teorema:
“una formula A es tautología (valida) si y solo si ¬A es insatisfacible”
8.
(a) Es el conjunto {p, ¬p ∨ q, q ∧ r} satisfacible?
(b) Es el conjunto {p, q ∧ r, ¬p ∧ q } satisfacible?
(c) prueba que si un conjunto de formulas S={A1,…,An} es satisfacible, entonces el
conjunto S1 que resulta de quitarle una de las As es también satisfacible.
9. Usando tableaux semánticos prueba que las siguientes formulas son tautologías.
(a) ¬ (p ∧ ¬p)
(b) (¬q → ¬p) → (p → q)
(c) p → (q → p)
(d) ¬ ((p ∨ q) ∧ (¬p ∧ ¬q))
(e) (p∨¬p)
10. Sin usar tablas de verdad prueba:
(a) p ∨ (p ∧ (¬p ∨ q)) ∨ q =T p ∨ q
(b) (p ∧ ¬q) ∨ (¬p ∧ q) =T ¬(p ∧ q) ∧ (p ∨ q)