DEPARTAMENTO DE ÁLGEBRA
Fundamentos Lógicos de la Programación
Curso 2009-2010
Problemas Extra Tema 2
1. Estudia si la siguiente fórmula es o no universalmente válida
P (x) → (∀x¬P (x) → ¬P (f (a)))
2. Estudiar para cada una de las siguientes fórmulas, si es universalmente válida, satisfacible, refu-
table o contradicción:
1. ∀x∃y R(x, y ) → ∃y ∀xR(x, y )
2. ∃x∀y R(x, y ) → ∀y ∃xR(x, y )
3. ∀x∀y (R(x, y ) → R(y , x))
3. Dadas las siguientes fórmulas:
ϕ = ∀x∃y P (x, y ); ψ = ∃x∀y P (x, y )
Encuentra una interpretación en la que ambas sean ciertas y otra en la que ϕ sea cierta y ψ sea falsa.
¿Es cierto que {ϕ} ψ?
4. Dadas las siguientes fórmulas
α = ∀x(P (x) → P (a)), β = ∀xP (x) → P (a)
estudiar cuáles son universalmente válidas, satisfacibles y/o refutables.
5. Consideramos el lenguaje de primer orden L definido por Cons(L) = {a} F unc(L) = {f , g}, Rel(L) =
{P, Q} y la L-estructura U dada por: D = Z10 , a = 4, f = + (suma en Z10 ) y g(x) = x 2 ,
P = {(k, k): k ∈ D}, Q = {(0, 0), (1, 9), (2, 8), (3, 7), (4, 6), (5, 5), (6, 4), (7, 3), (8, 2), (9, 1)} In-
terpretar las fórmulas siguientes usando la asignación
v : V ar (L) → Z10
x 7→ 0, y 7→ 4
1. ∀x(P (g(x), a) → Q(f (y , a), x))
2. ∀x∃y ∃z P (x, f (g(y ), g(z)))
1
6. Consideremos el lenguaje de primer orden L definido por Cons(L) = {a, b, c} F unc(L) =
{f , g}, Rel(L) = {P } y la L-estructura U dada por:
D = Z6 ,
a = 0, b = 1, c = 2
f = +(suma en Z6 ) y g(x) = ·(el producto en Z6 )
P = {(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}
1. Describir todas las asignaciones v sobre el conjunto de variables {x, y } en esta estructura para
las que la siguiente fórmula se interpreta como verdadera:
¬P (g(x, f (b, b)), a) → P (f (y , c), g(y , y ))
2. Interpretar la sentencia ∀x∃y P (g(y , c), x).
7.
1. Describir todas las estructuras en las que la fórmula siguiente es válida:
R(x) → ∀xR(x)
2. Estudiar la fórmula R(f (x)) → ∃y R(y ).
3. Representa mediante una fórmula de primer orden la frase “ser fuerte no es condición necesaria
ni suficiente para ser un macarra”.
8. Consideremos el lenguaje de primer orden L definido por Cons(L) = {a} F unc(L) = {f , g}, Rel(L) =
{P } y la L-estructura U dada por:
D = Z6 ,
a=2
f = +(suma en Z6 ) y g(x) = ·(el producto en Z6 )
P = {(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}
la asignación v en U tal que v (x1 ) = 2, v (x2 ) = 0, v (x3 ) = 0, v (x4 ) = 3, interpretar las siguientes
fórmulas:
1. ¬∃x1 ∀x2 P (f (x1 , x4 ), a)
2. ∀x1 (P (x1 , g(x1 , x1 )) ↔ P (g(a, x1 ), f (a, a)))
9. Sea (X, ≤) un conjunto ordenado. Consideramos un lenguaje de primer orden con un símbolo de
predicado binario R, y cinco símbolos de variables x, y , z, t, u.
Sea ahora la L-estructura, cuyo universo es X, y para la que R =≤, es decir:
1 si x ≤ y
R(x, y ) =
0 en otro caso
Escribe una fórmula que signifique que X es un retículo.
2
10. Dada la fórmula
R(x) ↔ ∃xR(x),
se pide:
1. Prueba que no es universalmente válida.
2. Encuentra una estructura donde la fórmula no sea válida.
3. ¿Es satisfacible la fórmula en cualquier estructura?
4. ¿Es refutable en toda estructura?
11. Interpretar la fórmula
∀x∀y (P (x, y ) → ¬P (y , x))
en las siguientes estructuras
1. D = {0, 1, 2, 3}
P = {(0, 0), (0, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
2. D = R
P es la relación binaria “x es estrictamente menor que y”
3. D = N
P es la relación binaria “x es múltiplo de y”
12. Interpreta la fórmula
∀x∀y (P (x, y ) → ¬P (y , x))
en las siguiente estructura D = {0, 1, 2, 3}
P = {(0, 0), (0, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
13. Determina el carácter (satisfacible y refutable, universalmente válida o contradicción) de la
fórmula:
∀x∃y (P (x, y ) → ¬P (y , x))
14. Dada la fórmula
P (x) → ∀x(P (x) ∨ ¬P (f (x)))
señalar para cuáles de las siguientes interpretaciones es verdadera.
D = Z4
f (x) = x + 1(mod 4)
a)
P = {0, 1, 3}
v (x) = 2
D = Z4
f (x) = x + 1(mod 4)
b)
P = {0, 1, 3}
v (x) = 1
3
D=Z
f (x) = x + 1
c)
P (x) := x es par
v (x) = 2
D=Z
f (x) = x + 1
d)
P (x) := x es par
v (x) = 1
15. Entre las siguientes fórmulas señalar las que sean sentencias:
1. ∀x[∃y Q(x, y ) ∨ R(y )]
2. ∀x[∃y Q(y , y ) ∨ R(x)]
3. ∀x[∃y Q(z , y ) ∨ R(x)]
4. ∀x[Q(x, x) ∨ ∃y R(y )]
16. Se considera la fórmula
∀x[Q(x, x) → ∃z S(z)]
¿qué necesitamos para interpretarla?
1. Describir la estructura y elegir una asignación para las variables.
2. Determinar el dominio, los valores de x y z y los predicados.
3. Describir el dominio y los predicados Q y S.
4. Nada, es satisfacible y refutable.
17. Para el lenguaje de primer orden correspondiente se considera la estructura:
D=N
R(x, y ) := “x es múltiplo de y 00
a=0
b=1
Determinar cuáles de las siguientes fórmulas son verdaderas bajo esta interpretación:
a) R(a, b)
b) ∃y ¬R(y , a)
c) ∀xR(b, x)
d) ∀x∀y (R(x, y ) → R(y , x))
4
18. De entre las siguientes equivalencias lógicas señalar cuáles son verdaderas y cuáles son falsas.
1. ∀xS(x) ∨ ∀xP (x) ≡ ∀x(S(x) ∨ P (x))
2. ∀xS(x) ∧ ∀xP (x) ≡ ∀x(S(x) ∧ P (x))
3. ∀xS(x) ∨ P (a) ≡ ∀x(S(x) ∨ P (a))
4. ∀xS(x) ∨ ∀x¬S(x) ≡ ∀x(S(x) ∨ ¬S(x))
19. ¿Cuáles de las siguientes fórmulas son tautologías?
1. ∃xP (x) → P (a)
2. P (a) → ∃xP (x)
3. ¬∃xP (x) → ¬P (a)
4. ∃x¬P (x) → ¬P (a)