R1
De Lógica matemática y fundamentos (2018-19)
Relación 1: Sintaxis y semántica de la lógica proposicional
Ejercicio 1. Formalizar el siguiente argumento
Siempre que un número x es divisible por 10, acaba en 0. El número x no acaba en 0. Por lo tanto, x no es divisible por 10.
Usando los símbolos D: el número es divisible por 10 y C: el número acaba en cero.
Solución:
Ejercicio 2. Formalizar el siguiente argumento
Si la válvula está abierta o la monitorización está preparada, entonces se envía una señal de reconocimiento y un mensaje de funcionamiento al controlador del ordenador. Si se envía un mensaje de funcionamiento al controlador del ordenador o el sistema está en estado normal, entonces se aceptan las órdenes del operador. Por lo tanto, si la válvula está abierta, entonces se aceptan las órdenes del operador.
Usando los símbolos V: La válvula está abierta, P: La monitorización está preparada, R: Envía una señal de reconocimiento, F: Envía un mensaje de funcionamiento, A: Se aceptan órdenes del operador y N: El sistema está en estado normal.
Solución:
Ejercicio 3. Formalizar el siguiente argumento
Cuando tanto la temperatura como la presión atmosférica permanecen contantes, no llueve. La temperatura permanece constante. Por lo tanto, en caso de que llueva, la presión atmosférica no permanece constante.
Usando los símbolos T: La temperatura permanece constante, P: La presión atmosférica permanece constante y L: Llueve
Solución:
Ejercicio 4. Formalizar el siguiente argumento
En cierto experimento, cuando hemos empleado un fármaco A, el paciente ha mejorado considerablemente en el caso, y sólo en el caso, en que no se haya empleado también un fármaco B. Además, o se ha empleado el fármaco A o se ha empleado el fármaco B. En consecuencia, podemos afirmar que si no hemos empleado el fármaco B, el paciente ha mejorado considerablemente.
Usando los símbolos A: Hemos empleado el fármaco A, B: Hemos empleado el fármaco B y M: El paciente ha mejorado notablemente.
Solución:
Ejercicio 5. Definir por recursión sobre fórmulas las siguientes funciones
- nv(F) que calcula el número variables proposicionales que ocurren en la fórmula F. Por ejemplo,
- nv(p → p ∨ q) = 3.
- prof(F) que calcula la profundidad del árbol de análisis de la fórmula F. Por ejemplo,
- prof(p → p ∨ q) = 2.
Demostrar por inducción, que para toda fórmula F,
- nv(F) ≤ 2^prof(F)
Solución:
Ejercicio 6. ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente?
Solución:
Ejercicio 7. ¿Es cierto que si F → G y F son satisfacibles, entonces G es satisfacible? Si es cierto, dar una explicación. Si no es cierto, dar un contraejemplo.
Solución:
Ejercicio 8. Demostrar o refutar las siguientes proposiciones:
- Si F es una fórmula satisfacible, entonces todas las subfórmulas de F son satisfacibles.
- Existen tautologías tales que todas sus subfórmulas son tautologías.
- Si F → G es insatisfacible, entonces F es tautología.
- Si F → G es tautología, entonces F es insatisfacible.
Solución:
Ejercicio 9. Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes afirmaciones:
- Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
- Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
Solución:
Ejercicio 10. Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea insatisfactible y donde cualquier conjunción de todas ellas menos una sea satisfactible. Generalízalo a n fórmulas.
Solución:
Ejercicio 11.
- Probar que la fórmula (((p → q) → p) → p) es una tautología
- Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué valores de n es A es una tautología?
Solución: