R5
De Lógica informática (2014-15)
Relación 5: Temas 1 a 4
Ejercicio 1. Demostrar o refutar las siguientes proposiciones:
- F ∧ G es satisfacible syss F es satisfacible y G es satisfacible.
- F ∨ G es satisfacible syss F es satisfacible o G es satisfacible.
Solución:
Ejercicio 2. En un texto de Lewis Carroll, el tío Jorge y el tío Jaime discuten acerca de la barbería del pueblo, atendida por tres barberos: Alberto, Benito y Carlos. Los dos tíos aceptan las siguientes premisas:
- Si Carlos no está en la barbería, entonces ocurrirá que si tampoco está Alberto, Benito tendrá que estar para atender el establecimiento.
- Si Alberto no está, tampoco estará Benito.
El tío Jorge concluye de todo esto que Carlos no puede estar ausente, mientras que el tío Jaime afirma que sólo puede concluirse que Carlos y Alberto no pueden estar ausentes a la vez. Decidir con el método de los tableros semánticos cuál de los dos tiene razón y demostrarlo por deducción natural.
Solución:
Ejercicio 3. Probar que la fórmula
- (E → (F ∧ G)) → (E → F) ∨ (E → G)
es una tautología por tableros semánticos y por deducción natural.
Solución:
Ejercicio 4. Demostrar o refutar la siguiente proposición:
Si S es un conjunto inconsistente de fórmulas, entonces el tablero semántico cerrado de S obtenido aplicando las reglas α antes que las reglas β tiene menos nodos que el tablero semántico cerrado de S obtenido aplicando las reglas β antes que las reglas α.
Solución:
Ejercicio 5. Probar, mediante forma normal conjuntiva y mediante deducción natural, que la fórmula
- (p → ¬q ∧ r) → (p → (q → r))
es una tautología
Solución: