Relación 5

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:

joslopjim4

• all x ( ( entra(x) & ( -vip(x) ) ) -> ( exists y (aduanero(y) & cachea(y,x) ) ) )
• exists x (contrabandista(x) & entra(x) & ( all y (cachea(y,x) & contrabandista(y))))
• all x (contrabandista(x) -> (- vip(x)))
• exists x (aduanero(x) & contrabandista(x))

manberdel1

• all x ((entra(x) & (-vip(x))) -> (exists y (aduanero(y) & cachea(y,x))))
• exists x (contrabandista(x) & entra(x) & (all y (cachea(y,x) -> contrabandista(y))))
• all x (contrabandista(x) -> -vip(x))
• exists x (aduanero(x) & contrabandista(x))

---

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:

joslopjim4,manberdel1

• all x all y ((robot(x) & amigo(y)) -> obedece(x,y))
• amigo(Alvaro)
• -obedece(Benito,Alvaro)
• -robot(Benito)

---

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:

joslopjim4

• exists x ( all y ( -C(x,y) -> ( exists z ( T(z) | P(z,y) ) ) ) )
• all x (all y (-C( x , y ) ) )
• all x (all y (-P( x , y ) ) )
• exists x ( T(x))

manberdel1

• exists x (all y (-C(x,y) -> (exists z (T(z) | P(z,y)))))
• all x (exists y (-C(x,y)))
• all x all y (-P(x,y))
• exists x (T(x))

---

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:

joslopjim4,manberdel1

• all x ( chino(x) & ( -afeita(x,x) ) <-> afeita(Carlos,x) )
• chino(Carlos)
• all y ( -afeita(Carlos,y))

---

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:

joslopjim4

• Verdadera

U={1} I(P)={1} I(a)=1

• Falsa

U={1,2} I(P)={1} I(a)=2

---

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:

joslopjim4

A1(x)=a -> I(F)=0
A2(x)=b -> I(F)=1
A3(x)=c -> I(F)=1
A4(x)=d -> I(F)=1

I(F)=0 si x=a

A1(x)=a -> I(F)=1
A2(x)=b -> I(F)=1
A3(x)=c -> I(F)=1
A4(x)=d -> I(F)=1

A1(x)=a, A1(y)=a -> I(F)=1
A1(x)=a, A2(y)=b -> I(F)=1
A1(x)=a, A3(y)=c -> I(F)=1
A1(x)=a, A4(y)=d -> I(F)=1

A2(x)=b, A1(y)=a -> I(F)=1
A2(x)=b, A2(y)=b -> I(F)=1
A2(x)=b, A3(y)=c -> I(F)=1
A2(x)=b, A4(y)=d -> I(F)=1

A3(x)=c, A1(y)=a -> I(F)=1
A3(x)=c, A2(y)=b -> I(F)=0
A3(x)=c, A3(y)=c -> I(F)=1
A3(x)=c, A4(y)=d -> I(F)=1

A4(x)=d, A1(y)=a -> I(F)=1
A4(x)=d, A2(y)=b -> I(F)=1
A4(x)=d, A3(y)=c -> I(F)=1
A4(x)=d, A4(y)=d -> I(F)=1

---

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:

joslopjim4

• Caso 1: F3 no consecuencia lógica de F1 y F2

U=naturales I(a)=0 I(f)=x+2

---

Ejercicio 8. Dar una fórmula F, tal que todo modelo de F tenga al menos 3 elementos. Generalizarlo a n cualquiera.

---

Solución:

joslopjim4

exists x exists y exists z (x≠y & x≠z & y≠z)

Para un n cualquiera, se ponen n exists con n variable diferentes y luego se hacen sus distinciones mediante una combinación sin repetición de n elementos cogidos de dos en dos