Diferencia entre revisiones de «R6»
De Lógica matemática y fundamentos (2017-18)
(Página creada con '=== Relación 6: Sintaxis y semántica de la Lógica de primer orden (b) === ---- '''Ejercicio 1.''' Dar una fórmula F satisfacible, tal que todos sus modelos sean necesariam...') |
|||
| Línea 40: | Línea 40: | ||
'''Ejercicio 4.''' | '''Ejercicio 4.''' | ||
| − | Sea L un lenguaje de primer orden con un símbolo de predicado, Q (de aridad 2) | + | Sea L un lenguaje de primer orden con un símbolo de predicado, Q (de aridad 2) y un símbolo de función, f (de aridad 1). Se considera la estructura I dada por: Universo: {a,b}, Qᴵ={(a,b), (b,a)}, fᴵ(a)= a y fᴵ(b)=a. Decidir cuáles de las siguientes fórmulas se satisfacen en la estructura: |
| − | |||
| − | |||
| − | |||
* ∀x (Q(f(x),x) → Q(x,x)) | * ∀x (Q(f(x),x) → Q(x,x)) | ||
* ∃x (Q(f(x),x) → Q(x,x)) | * ∃x (Q(f(x),x) → Q(x,x)) | ||
| Línea 54: | Línea 51: | ||
'''Ejercicio 5.''' | '''Ejercicio 5.''' | ||
| − | Sea L un lenguaje de primer orden con un símbolo de predicado P de aridad | + | Sea L un lenguaje de primer orden con un símbolo de predicado P de aridad 2. Probar que las fórmulas ∀x ∃y P(x,y) y ∃x ∀y P(x,y) no son equivalentes, |
| − | 2. Probar que las fórmulas ∀x ∃y P(x,y) y ∃x ∀y P(x,y) no son equivalentes, | ||
dando una estructura que sea modelo de la primera pero no de la segunda. | dando una estructura que sea modelo de la primera pero no de la segunda. | ||
Revisión del 19:25 2 abr 2018
Relación 6: Sintaxis y semántica de la Lógica de primer orden (b)
Ejercicio 1. Dar una fórmula F satisfacible, tal que todos sus modelos sean necesariamante infinitos.
Solución:
Ejercicio 2. ¿Cuántos elementos han de tener los modelos de la fórmula F = ∀x f(f(x))= x ∧ ∀x f(x) ≠ x?
Solución:
Ejercicio 3.
- Dar un ejemplo de una fórmula F tal que todos sus modelos tengan al menos dos elementos.
- Dar un ejemplo de una fórmula F tal que todos sus modelos tengan dos elementos como máximo.
- Dar un ejemplo de una fórmula F tal que todos sus modelos tengan exactamente dos elementos.
- Dar un ejemplo de una fórmula F tal que todos sus modelos tengan exactamente tres elementos.
Solución:
Solución:
Ejercicio 4.
Sea L un lenguaje de primer orden con un símbolo de predicado, Q (de aridad 2) y un símbolo de función, f (de aridad 1). Se considera la estructura I dada por: Universo: {a,b}, Qᴵ={(a,b), (b,a)}, fᴵ(a)= a y fᴵ(b)=a. Decidir cuáles de las siguientes fórmulas se satisfacen en la estructura:
- ∀x (Q(f(x),x) → Q(x,x))
- ∃x (Q(f(x),x) → Q(x,x))
Solución:
Ejercicio 5.
Sea L un lenguaje de primer orden con un símbolo de predicado P de aridad 2. Probar que las fórmulas ∀x ∃y P(x,y) y ∃x ∀y P(x,y) no son equivalentes, dando una estructura que sea modelo de la primera pero no de la segunda.
Solución: