Diferencia entre revisiones de «Relación 6»
De Lógica matemática y fundamentos (2014-15)
(→Relación 6: Sintaxis y semántica de la Lógica de primer orden) |
|||
| (No se muestran 4 ediciones intermedias de 3 usuarios) | |||
| Línea 3: | Línea 3: | ||
---- | ---- | ||
'''Ejercicio 1.''' | '''Ejercicio 1.''' | ||
| − | Sea F la fórmula P(x) → P ( a ) , donde a es un símbolo de constante. ¿Es | + | 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? | F satisfacible? ¿Tiene modelos? ¿Es F una fórmula válida? | ||
| Línea 11: | Línea 11: | ||
---- | ---- | ||
| − | '''Ejercicio 2.''' | + | '''Ejercicio 2.''' 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: |
| − | Sea L un lenguaje de primer orden con dos símbolos de predicado, P (de | + | * U = {a, b, c, d} ; |
| − | aridad 1), Q (de aridad 2) y un símbolo de función, f , de aridad 1. Sea I = ( U, I ) la | + | * I(P) = {a, b} , |
| − | estructura dada por: | + | * I(Q) = {(a,b), (b,b), (c,b)} , |
| − | U = { a, b, c, d } ; | + | * I(f) = {(a,b), (b,b), (c,a), (d,c)} . |
| − | I ( P ) = { a, b } , | + | Decidir cuáles de las siguientes fórmulas de L son válidas en I: |
| − | I ( Q ) = {( a, b ) , ( b, b ) , ( c, b )} , | + | * P(x) → ∃yQ(y,x). |
| − | I ( f ) = {( a, b ) , ( b, b ) , ( c, a ) , ( d, c )} . | + | * ∀xQ(f(x),x). |
| − | Decidir cuáles de las siguientes fórmulas de L son válidas en I : | + | * Q(f(x),x) → Q(x,x). |
| − | * P ( x ) → | + | * Q(x,y) → P(x). |
| − | * | ||
| − | * Q ( f ( x ) , x ) → Q ( x, x ) . | ||
| − | * Q ( x, y ) → P ( x ) . | ||
---- | ---- | ||
'''Solución:''' | '''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. | ||
| + | |||
| + | -- Alba González Parra | ||
---- | ---- | ||
| − | '''Ejercicio 3.''' | + | '''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₁ : = ∀x[f(x) ≠ a], | |
| − | En el lenguaje con igualdad L = { a, f } , siendo f un símbolo de función | + | * F₂ : = ∀x∀y[f(x) = f(y) → x = y], |
| − | de aridad 1 y a una constante, se consideran las siguientes fórmulas: | + | * F₃ : = ∀x[x ≠ a → ∃y[f(y) = x]] . |
| − | * | ||
| − | * | ||
| − | * | ||
Probar que ninguna de estas fórmulas es consecuencia lógica de las dos restantes. | Probar que ninguna de estas fórmulas es consecuencia lógica de las dos restantes. | ||
Revisión actual del 11:16 4 abr 2015
Relación 6: Sintaxis y semántica de la Lógica de primer orden
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. 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.
-- Alba González Parra
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₁ : = ∀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: