Relación 6
De Lógica Matemática y fundamentos (2015-16)
Relación 6: Sintaxis y semántica de la Lógica de primer orden[editar]
Ejercicio 1. Sea F la fórmula P(x) → P ( a ) , donde a es un símbolo de constante. ¿Es F satisfacible? ¿Tiene modelos? ¿Es F una fórmula válida?
Solución:
Ejercicio 2. Formalizar el siguiente argumento 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 )} . Decidir cuáles de las siguientes fórmulas de L son válidas en I :
- P ( x ) → ∃ yQ ( y, x ) .
- ∀ xQ ( f ( x ) , x ) .
- Q ( f ( x ) , x ) → Q ( x, x ) .
- Q ( x, y ) → P ( x ) .
Solución: 1. No es válida pues existe una asignación que hace a la fórmula falsa. Tomando A(x) = a
P(a) = 1
Q(y,a) = 0 para cualquier asignación de y
Luego la implicación es falsa.
2. No es válida pues existe una asignación que hace a la fórmula falsa.
Tomando de nuevo A(x)=a
Q(f(a),a)=Q(b,a)=0
Luego hemos encontrado un x que no satisface Q(f(x),x) y
por tanto la fórmula es falsa.
3. Si es válida pues para toda asignación de x se verifica la fórmula.
Si A(x)=a entonces Q(f(a),a)=Q(b,a)=0 y Q(a,a)=0 luego la implicación es verdadera.
Si A(x)=b entonces Q(f(b),b)=Q(b,b)=1 y Q(b,b)=1 luego la implicación es verdadera.
Si A(x)=c entonces Q(f(c),c)=Q(a,c)=0 y Q(c,c)=0 luego la implicación es verdadera.
Si A(x)=d entonces Q(f(d),d)=Q(c,d)=0 y Q(d,d)=0 luego la implicación es verdadera.
4. No es válida pues existe una asignación que hace a la fórmula falsa.
Tomando A(x)=c y A(y)=b tenemos que Q(c,b)=1 y P(c)=0 luego es falsa la implicación.
Ejercicio 3.
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_1 : = ∀ x [ f ( x ) ≠ a ] , F_2 : = ∀ x ∀ y [ f ( x ) = f ( y ) → x = y ] , F_3 : = ∀ x [ x ≠ a → ∃ y [ f ( y ) = x ]] .
Probar que ninguna de las tres fórmulas es consecuencia de las dos restantes.
Solución: