Lógica y Computabilidad Primer Cuatrimestre 2011
Práctica 3 -Lógica de primer orden-
Ejercicio 1. Sea L un lenguaje de primer orden con signatura compuesta por un sı́mbolo de
predicado binario P , dos sı́mbolos de función f1 , f2 , donde f1 es unario y f2 es binario, y un
sı́mbolo de constante c.
a. Si x, y denotan variables, decidir cuáles de las siguientes expresiones son términos y cuáles
son fórmulas del lenguaje L:
1) ∃f2 (x)P (f2 (x)). 5) ∀c∃xP (x, c). 9) ∀z(∀xP (z, x)) ∨ P (c, z).
2) f2 (f1 (x), f1 (y)). 6) ∃xP (x, y) → ∃yP (y, z). 10) P (x, c).
3) ∀x∃cP (x, c). 7) f2 (f1 (x), f2 (c, c)). 11) ∃f1 (∀x(f1 (x) = x)).
4) ∀∃P (∃, ∃). 8) ∃x∃y∃xP (f2 (x, y), f1 (y)). 12) f2 (x).
b. Para cada fórmula de la lista anterior, encontrar las apariciones libres y ligadas de las varia-
bles de dicha fórmula.
c. Elija dos términos y dos fórmulas de la lista anterior y desarrolle una cadena de formación
para cada uno de ellos.
Ejercicio 2. Decidir si las siguientes interpretaciones son apropiadas sobre las signaturas dadas,
en donde f es un sı́mbolo unario y g es binario:
√
a. C = ∅, F = {f, g}, P = {=}, UI = N, fI (n) = n, gI (n, m) = n + m.
b. C = {c}, F = {f, g}, P = {=}, UI = N, fI (n) = n2 , gI (n, m) = n + m, cI = 2.
c. C = {c, d}, F = {f, g}, P = {=}, UI = N, gI (n, n) = n2 − n, cI = dI = 0,
1 si n es primo
fI (n) =
2 si n no es primo
Ejercicio 3. En cada uno de los siguientes ejemplos, describir la propiedad que determinan los
siguientes enunciados. Cuando sea posible determinar si el enunciado es verdadero o falso en la
interpretación correspondiente.
a. ∀x∀y(P (x, y) → ∃z((Q(z) ∧ P (x, z)) ∧ P (z, y))), donde P y Q son sı́mbolos de predicados
binario y unario respectivamente, el universo de la interpretación son los números reales,
PI = <, QI (x) significa x es un número racional.
b. ∀x(Q(x) → ∃y(R(y) ∧ P (y, x))), donde P es un sı́mbolo de predicado binario, Q y R son
sı́mbolos de predicados unarios, el universo de la interpretación es el conjunto de los dı́as
y las personas, PI (x, y) significa x nace en el dı́a y, QI (x) significa x es un dı́a, y RI (x)
significa x es un hombre libre.
c. ∀x∀y((Q(x) ∧ Q(y)) → P (f (x, y))), donde Q y P son sı́mbolos de predicados unarios, f es un
sı́mbolo de función binario, el universo de la interpretación son los números enteros, QI (x)
significa x es par, PI (x) significa x es impar, y fI (x, y) = x + y.
d. Para los siguientes enunciados, el universo de interpretación es el conjunto de personas, el
predicado binario P (x, y) se interpreta como ‘x quiere a y’ y el sı́mbolo de constante g se
interpreta como Kurt Gödel :
a. ∃x∀y¬P (x, y). d. ∃x∀z(P (z, g) → P (x, z)).
b. ∀y∃xP (x, y). e. ∃x∃y((∀zP (y, z)) → P (x, y)).
c. ∃yP (y, g). f. ∀y(P (g, y) → y = g).
1
Ejercicio 4. Supongamos dados los siguiente predicados:
H(x): x es un humano; T (x): x es un camión;
C(x): x es un auto; D(x, y): x maneja a y.
Escribir fórmulas representando las siguientes obviedades: (a) nungún humano es un auto, (b)
sólo las personas manejan, (c) los autos existen. Escriba fórmulas que representen las siguientes
propiedades: (a) todos los humanos manejan un camión o un auto, (b) algunas personas no manejan
ninguno, (c) algunas personas manejan ambos, (d) nadie maneja ambos.
Supongamos que además tenemos el siguiente predicado
I(x, y): x e y son idénticos.
Escriba fórmulas que expresen las siguientes propiedades: (a) todo auto tiene a lo sumo un con-
ductor, (b) todo camión tiene exactamente dos conductores, (c) toda persona maneja exáctamente
un vehı́culo (auto o camión), (d) todo auto es conducido por alguien, (e) nadie maneja dos camio-
nes.
Ejercicio 5. Sea P un sı́mbolo de relación unario y sea f un sı́mbolo de función binario. Para
cada una de las fórmulas ∀x∀y f (x, y) = x, ∃x∀y f (x, y) = y, ∃x(P (x) ∧ ∀y P (f (x, y))) hallar una
interpretación que la satisfaga y otra que no la satisfaga.
Ejercicio 6. Usando el predicado R(x, y) (x es un ancestro de y), traduzca el siguiente argumento
a una sentencia del cálculo de predicados.
Todo ancestro de un ancestro de una persona es un ancestro de esa persona. Nadie es
su propio ancestro. Por lo tanto, existe una persona que no tiene ancestro.
¿Es válido este razonamiento? Justifique su respuesta encontrando una interpretación apropiada
de su traducción del razonamiento.
Ejercicio 7. En la lógica de primer orden sobre la signatura compuesta por un sı́mbolo de relación
binario ≤, consideremos las siguientes fórmulas.
ϕT = ∀x∀y∀z (x ≤ y ∧ y ≤ z → x ≤ z)
ϕA = ∀x∀y (x ≤ y ∧ y ≤ x → x = y)
ϕR = ∀x (x ≤ x)
ϕL = ∀x∀y (x ≤ y ∨ y ≤ x)
ϕD = ∃x∃y (x 6= y) ∧ ∀x∀y ((x ≤ y ∧ x 6= y) → ∃z(x ≤ z ∧ x 6= z ∧ z ≤ y ∧ z 6= y)))
ϕSE = ∀x∃y (x ≤ y ∧ x 6= y) ∧ ∀x∃y (y ≤ x ∧ x 6= y).
Una interpretación de dicho lenguaje que satisface ϕOrd = ϕT ∧ ϕA ∧ ϕR (i.e., un modelo
de ϕOrd ) se llama un orden parcial y la clase de todos los modelos de ϕOrd se llama la clase
de los órdenes parciales y la clase de los modelos de ϕT ot := ϕOrd ∧ ϕL se llama la clase de los
órdenes totales o cadenas. Para cada fórmula en C = {ϕL , ϕD , ϕSE } construir un orden parcial
que satisfaga dicha fórmula y que no satisfaga a las dos restantes fórmulas de C.
Ejercicio 8. Considerar un lenguaje con un sı́mbolo de función f binario. Escribir una fórmula
ϕ que cumpla A |= ϕ sii fA es inyectiva. Escribir una fórmula ψ que cumpla A |= ψ sii fA es
sobreyectiva.
Hallar un modelo de ϕ∧¬ψ y otro de ψ ∧¬ϕ. ¿Es posible encontrar un modelo finito de ϕ∧¬ψ?
2
Ejercicio 9. Una fórmula que no contiene ¬, → ni ↔ se llama positiva. Mostrar que para toda
fórmula positiva hay una interpretación que la satisface.
Definición. Decimos que un elemento e del universo de una interpretación I es distinguible con
el lenguaje L si existe una L-fórmula ϕ(x) con una sola variable libre x tal que I |= ϕ(x)[v] si y
sólo si v(x) = e.
Ejercicio 10. Sea L un lenguaje con igualdad y un sı́mbolo de función binario, y sean I1 e I2 las
siguientes interpretaciones:
I1 = (N, +), I2 = (N, ·).
Probar que 1 es un elemento distinguido en ambas interpretaciones. ¿Qué ocurre con el 2? Dar
una fórmula que sea verdadera en una interpretación y falsa en la otra.
Ejercicio 11. Dar un ejemplo de un lenguaje (sin constantes) y una interpretación de dicho
lenguaje con universo infinito tal que todo elemento del universo de la interpretación dada sea
distinguible.
Ejercicio 12. Sea L un lenguaje de primer orden y con un sı́mbolo de predicado binario ≤. Probar
que todos los elementos del universo de la siguientes interpretaciones son distinguibles,
6 3
5
4 5
2
2 3
a) 1 b) 1
Definición. Dada una interpretación I con universo |I|, decimos que una relación R ⊆ |I|n es
expresable con el lenguaje L si existe una L-fórmula ϕ(x1 , . . . , xn ) con n variables libres tal que
para toda valuación v
I |= ϕ(x1 , . . . , xn )[v] sii (v(x1 ), . . . , v(xn )) ∈ R.
Ejercicio 13. Demostrar que las siguientes relaciones son expresables.
a. I1 = hN, ×, =i con × el producto de naturales.
R1 = {(n, m) : n divide a m}.
P1 = {n : n es primo}.
b. I2 = hN, +, =, 0, 1i con + la suma de naturales.
R2 = {(n, m) : n < m}.
c. I3 = hL, ◦, =i con L el conjunto de todas las listas, ◦ la concatenación de listas.
R3 = {(a, b) : a es sublista de b}.
d. I4 = hR, +, ×, =, 0, 1i, donde + y × son la suma y producto respectivamente.
R4 = {(x, y) : x < y}.
1
*. I5 = hN, +, ×, =, 0, 1i con + y × la suma y el producto de naturales respectivamente.
R5 = {(i, j, k) : ij = k}.
1 Muy difı́cil!
3
Ejercicio 14. Demostrar que, en cambio, las siguientes relaciones no son expresables:
e. J1 = hR, +, =, 0i, donde + es la suma de números reales.
Q1 = {(x, y) : x < y}.
f. J2 = hN, P i, donde P es el predicado unario ser par.
Q2 = {n ∈ N : n es múltiplo de 3}.
g. J3 = hN, ×i, donde × es el producto de naturales.
Q3 = {(i, j, k) ∈ N3 : i + j = k}.
Definición. Decimos que una clase de modelos K es definible 2 con el lenguaje L si existe un
conjunto finito de L-sentencias ϕ1 , ..., ϕs tal que para toda interpretación I de L
I |= ϕ1 ∧ ... ∧ ϕs sii I ∈ K.
Si esto ocurre, llamamos a ϕ1 , ..., ϕs los axiomas de la teorı́a 3 de K.
Ejercicio 15. Demostrar que las siguientes clases de modelos son definibles en sus respectivos
lenguajes.
a. L0 = {=}. K0 = ∅.
b. L1 = {=}. K1 = {todas las interpretaciones}.
c. L2 = {R, =} con P predicado binario. K2 = {I : P I es irreflexivo y simétrico}.
K2 es conocida como la clase de grafos no orientados.
d. L3 = {f, g, =} con f, g funciones unarias. K3 = {I : Im f I ⊆ Im g I }.
e. L4 = {≤, =} con ≤ predicado binario. K4 = {I :≤I es un orden parcial}.
f. L5 = {×,−1 , =, 1} con ×,−1 sı́mbolos de función binario y unario respectivamente y 1 un
I
sı́mbolo de constante. K5 = {I : h|I|, ×I ,−1 , 1I i es un grupo abeliano}.
2 También se dice que es una clase elemental. En este contexto elemental se usa como sinónimo de definible en
la lógica de primer orden.
3 Por ejemplo, en el item (f) del próximo ejercicio tiene que escribir los axiomas de la teorı́a de grupos abelianos
y en el item (e) los axiomas de la teorı́a de órdenes parciales.