Relación 6

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:

joslopjim4

• exists x exists y (x≠y)
• exists z exists y (x≠y & all z (z=x | x=y))
• exists x exists y exists z (x≠y & x≠z & y≠z & all a (a=x | a=y | a=z))

---

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:

joslopjim4

• No, no se satisface para x=b
• Sí, se satisface para x=b

---

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:

joslopjim4

U=Z I(P)=<

En este caso, la primera formula siempre se satisface, sin embargo la segunda nunca.