R5
De Lógica matemática y fundamentos (2018-19)
Relación 5: Sintaxis y semántica de la Lógica de primer orden
Ejercicio 1. Formalizar el siguiente argumento (ejercicio 5 de LPO de APPLI2), verificando la corrección de la solución:
- Todo aquel que entre en el país y no sea un VIP será cacheado por un aduanero.
- Hay un contrabandista que entra en el país y que solo podrá ser cacheado por contrabandistas.
- Ningún contrabandista es un VIP.
- Por lo tanto, algún aduanero es contrabandista.
Solución:
Ejercicio 2. Formalizar el siguiente argumento (ejercicio 15 de LPO de APPLI2), verificando la corrección de la solución:
- Todos los robots obedecen a los amigos del programador jefe.
- Alvaro es amigo del programador jefe.
- Benito no obedece a Alvaro.
- Benito no es un robot.
Solución:
Ejercicio 3. Formalizar el siguiente argumento (ejercicio 16 de LPO de APPLI2), verificando la corrección de la solución:
- Hay algún pez x que para cualquier pez y, si el pez x no se come al pez y entonces existe un pez z tal que z es un tiburón o bien z protege al pez y.
- No hay ningún pez que se coma a todos los demás.
- Ningún pez protege a ningún otro.
- Por lo tanto, existe algún tiburón en la pecera.
Solución:
Ejercicio 4. Formalizar el siguiente argumento (ejercicio 21 de LPO de APPLI2), verificando la corrección de la solución:
- Carlos afeita a todos los habitantes de Las Chinas que no se afeitan a sí mismo y sólo a ellos.
- Carlos es un habitante de las Chinas.
- Por lo tanto, Carlos no afeita a nadie.
Solución:
Ejercicio 5. Sea F la fórmula P(x) → P (a) , donde a es un símbolo de constante. Dar un ejemplo de una interpretación en la que F sea verdadera. Y un ejemplo de una interpretación en la que F sea falsa.
Solución:
Ejercicio 6. Sea L un lenguaje de primer orden con dos símbolos de predicado, P (de aridad 1), Q (de aridad 2) y un símbolo de función, f , de aridad 1. Sea I = ( U, I ) la estructura dada por: U = { a, b, c, d } ; I ( P ) = { a, b } , I ( Q ) = {( a, b ) , ( b, b ) , ( c, b )} , I ( f ) = {( a, b ) , ( b, b ) , ( c, a ) , ( d, c )} . ¿Cuál es el valor de cada una de las siguientes fórmulas en dicha estructura?
- P ( x ) → ∃ yQ ( y, x ) .
- ∀ xQ ( f ( x ) , x ) .
- Q ( f ( x ) , x ) → Q ( x, x ) .
- Q ( x, y ) → P ( x ) .
Solución:
Ejercicio 7.
En el lenguaje con igualdad L = { a, f } , siendo f un símbolo de función de aridad 1 y a una constante, se consideran las siguientes fórmulas:
- F₁ : = ∀ x [ f ( x ) ≠ a ] ,
- F₂ : = ∀ x ∀ y [ f ( x ) = f ( y ) → x = y ] ,
- F₃ : = ∀ x [ x ≠ a → ∃ y [ f ( y ) = x ]] .
Probar que ninguna de estas fórmulas es consecuencia lógica de las dos restantes.
Solución:
Ejercicio 8. Dar una fórmula F, tal que todo modelo de F tenga al menos 3 elementos. Generalizarlo a n cualquiera.
Solución: