Lógica Informática (Tecnologı́as Informáticas).

14 de septiembre de 2022
Relación 1: Sintaxis y Semántica.
Lógica Proposicional

Ejercicio 1. Determina todas las subfórmulas de:

((¬p ∨ q) ∧ (q → r)), y (¬(¬(¬p ∨ p) ∨ p) ∨ q)

Ejercicio 2. Simplificación de paréntesis:

1. Elimina todos los paréntesis posibles de las siguientes fórmulas:
(((p → q) ∨ r) → (p ∧ ¬p)) (¬(p ∧ q) → (q ∧ r)) ((p → (q ∧ r)) → (¬¬p ∧ q))
¬((p ∧ p) ∧ (p ∧ p)) (((p ∨ q) ∨ (r ∨ s)) → ¬p) (p → ((q ↔ s) → p))

2. Escribe con paréntesis las siguientes fórmulas:

p → q ↔ r ∨ s, q → ¬p ∨ r ∨ s, p ∨ q ↔ ¬r ∨ s, q ∧ ¬q ∨ p → r

Ejercicio 3. Definir por recursión sobre fórmulas las siguientes funciones

1. np(F ) que calcula el número de paréntesis de la fórmula F . Por ejemplo,
np((p → (¬q ∨ p))) = 4.

2. Subf(F ) que calcula el conjunto de las subfórmulas de la fórmula F . Por ejemplo,

Subf(p → ¬q ∨ p) = {p → ¬q ∨ p, p, ¬q ∨ p, ¬q, q}.

Ejercicio 4. Demostrar por inducción que todas las fórmulas proposicionales tienen un
número par de paréntesis.
Ejercicio 5. Dada una fórmula proposicional A, sean s(A) el número de estancias de va-
riables proposicionales en A y b(A) el número de estancias de conectivas binarias en A. Prueba
que para toda fórmula A se verifica que s(A) = b(A) + 1.
Ejercicio 6. Para cada una de las siguientes fórmulas, determina todos sus modelos e
indica si son satisfactibles, insatisfactibles o tautologı́as.
p → (q → r ∧ q) q → (p ∧ ¬p) → r
(p ↔ q) ∧ (p → ¬q) ∧ p (p ∧ r) ∨ (¬p ∧ q) → ¬q

1
Ejercicio 7. Expresa mediante fórmulas proposicionales las siguientes afimaciones.
En cada caso, indica el significado que se asigna a las variables (p, q, etc.) utilizadas.
1. Si el sol brilla hoy, entonces no brillará mañana.
2. O Roberto tiene celos de Chari o no está de buen humor hoy.
3. Cuando la presión atmosférica baja, entonces llueve o nieva.
4. Si has leı́do los apuntes y has hecho los ejercicios, estás preparado para el examen. En
caso contrario, tienes un problema.
5. Si Pablo se encontró con Chari ayer, entonces tomaron café juntos o pasearon por el
parque.
6. Juan duerme muchas horas y muy profundamente.
7. Mi hermana tiene un gato blanco y negro.

Ejercicio 8. Decide razonadamente si los siguientes enunciados son verdaderos o falsos.

Si es cierto, ofrecer una explicación. Si no lo es, mostrar un contraejemplo.:
1. Si F y G son fórmulas consistentes, entonces {F, G} es consistente.
2. Si F es una tautologı́a y G es consistente, entonces {F, G} es consistente.
3. Si G es una contradicción, entonces F → G → F es una tautologı́a.
4. Si F es satisfactible, todas sus subfórmulas también lo son.
5. F es satisfactible si, y sólo si, todas sus consecuencias lógicas también lo son.
6. Si {F, G, H} es inconsistente, entonces F |= ¬G ∨ ¬H.
7. {F, G} es consistente si y sólo si {¬F, ¬G} es inconsistente.
8. Si U es un conjunto de fórmulas tal que U 6|= F , entonces U |= ¬F .
9. Si U es un conjunto de fórmulas tal que U |= F , entonces U 6|= ¬F .
10. Si F → G y F son satisfactibles, entonces G es satisfactible.

Ejercicio 9. Para cada caso, encuentra fórmulas F y G tales que:

1. ¬F → G es una contradicción.
2. F y F → G son satisfactibles, pero G es una contradicción.
3. F 6|= G y F 6|= ¬G.
4. F |= G y F |= ¬G.

Ejercicio 10. Determina cuáles de las siguientes fórmulas son consecuencia lógica de la
fórmula A ∧ B y cuáles de A ∨ ¬B:
(1) A (2) ¬B → A (3) ¬A ∨ B (4) B → ¬A
Ejercicio 11. Decide cuáles de las siguientes afirmaciones son verdaderas:

{p ∨ q} |= p → r {p → q, q → p ∧ r} |= p → (p → q) → r
{p ∧ ¬p} |= r → r ∨ q {p ∧ q ∧ r} |= r → ¬p

2
Los siguientes ejercicios son de formalización (en lógica proposicional) extraidos del libro de
Eulalia López Sedeño “Ejercicios de Lógica”. El resultado debe de ser, si es un argumento,
un par hΦ, ϕi tal que Φ |= ϕ.

Ejercicio 12. Formaliza el siguiente texto y decide si es un argumento:

Si la tormenta continúa o anochece, nos quedaremos a cenar o a dormir; si nos quedamos a
cenar o a dormir no iremos mañana al concierto; pero sı́ iremos mañana al concierto. Ası́ pues,
la tormenta no continúa.
Ejercicio 13. Formaliza el siguiente texto y decide si es un argumento:
Si un triángulo tiene tres ángulos, un cuadrado tiene cuatro ángulos rectos. Un triángulo tiene
tres ángulos y su suma vale dos ángulos rectos. Si los rombos tienen cuatro ángulos rectos,
los cuadrados no tienen cuatro ángulos rectos. Por tanto, los rombos no tienen cuatro ángulos
rectos.
Ejercicio 14. Formaliza el siguiente texto y decide si es un argumento:
Si la gorila es atractiva, el gorila sonreirá abiertamente o será infeliz. Si no es feliz, no pro-
creará en cautividad. Por consiguiente, si la gorila es atractiva, entonces, si el gorila no sonrı́e
abiertamente, no procreará en cautividad.
Ejercicio 15. Formaliza el siguiente texto y decide si es un argumento:
Si Elvira opina que hay que hacer lo posible para ser feliz, abandonará a su amante o se dedicará
a su profesión. Si se dedica a su profesión, no dejará a su marido. En conclusión, si Elvira opina
que hay que hacer lo posible para ser feliz, entonces, dejará a su marido aunque no abandone a
su amante.
Ejercicio 16. Formaliza el siguiente texto y decide si es un argumento:
Si los astrónomos observan un nuevo planeta con atmósfera fuera de nuestro sistema solar, la
Tierra no será el único planeta habitable en el Universo. O la Tierra no es el único planeta
habitable o hay sistemas inexplorados. Por tanto, o los astrónomos no observan un nuevo pla-
neta con atmósfera, fuera de nuestro sistema solar, o la Tierra es el único planeta habitable en
el Universo.
Ejercicio 17. Formaliza el siguiente texto y decide si es un argumento:
Si no es cierto que se puede ser rico y dichoso a la vez, entonces la vida está llena de frustra-
ciones y no es un camino de rosas. Si se es feliz, no se puede tener todo. Por consiguiente, la
vida está llena de frustraciones.

3
Ejercicio 18. Determina si los siguientes argumentos son lógicamente correctos:
1. Si Juan es comunista, entonces Juan es ateo. Juan es ateo. Por tanto, Juan es comunista.

2. Cuando tanto la temperatura como la presión atmosférica permanecen contantes, no

llueve. La temperatura permanece constante. En consecuencia, en caso de que llueva, la
presión atmosférica no permanece constante.

3. Siempre que un número x es divisible por 10, acaba en 0. El número x no acaba en 0.

Luego, x no es divisible por 10.

4. Para que un número x sea divisible por 5, es necesario que el número acabe en 0. El
número x no acaba en 0. Luego, x no es divisible por 5.

5. El número y es negativo si x es positivo. Cuando z es negativo, y también lo es. Por tanto,

y es negativo siempre que o bien x sea positivo o bien z sea negativo.

6. En cierto experimento, cuando hemos empleado un fármaco A, el paciente ha mejorado

considerablemente en el caso, y sólo en el caso, en que no se haya empleado también un
fármaco B. Además, o se ha empleado el fármaco A o se ha empleado el fármaco B. En
consecuencia, podemos afirmar que si no hemos empleado el fármaco B, el paciente ha
mejorado considerablemente.

Ejercicio 19. Decidir la corrección del siguiente argumento:

Se sabe que
1. Los animales con pelo o que dan leche son mamı́feros.
2. Los mamı́feros que tienen pezuñas o que rumian son ungulados.
3. Los ungulados de cuello largo son jirafas.
4. Los ungulados con rayas negras son cebras.
Se observa un animal que tiene pelos, pezuñas y rayas negras. Por consiguiente, se
concluye que el animal es una cebra.

Ejercicio 20. En una isla hay dos tribus, la de los veraces (siempre dicen la verdad) y la
de los mentirosos (qsiempre mienten). Un viajero se encuentra con tres isleños A, B y C. Cada
uno le dice una frase
1. A dice “B y C son veraces syss C es veraz”

2. B dice “Si A y C son veraces, entonces B y C son veraces y A es mentiroso”

3. C dice “B es mentiroso syss A o B es veraz”

Decide a qué tribu pertenecen A, B y C.

4
 Ejercicio 21. Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a tres puertas,
de las que el prisionero debe elegir una, y entrar en la habitación correspondiente. Se informa
al prisionero que en dos de las habitaciones hay sendos tigres, y en la otra una dama. Como es
natural, el prisionero debe elegir la puerta que le lleva a la dama (entre otras cosas, para no ser
devorado por el tigre). Para ayudarle, en cada puerta hay un letrero:

Puerta 1: en esta habitación hay un tigre

Puerta 2: en esta habitación está la dama
Puerta 3: en esta habitación está la dama

El prisionero se da cuenta inmediatamente de que los tres letreros no pueden ser verdaderos,
y el rey le informa que al menos uno es falso. Tras pensar unos minutos, el prisionero dice que,
con todo, es imposible deducir lógicamente el resultado, pues la dama podrı́a estar en cualquier
habitación. Tras comprobar el rey que esto es cierto, le informa que al menos dos letreros son
falsos. El prisionero pudo ası́ deducir la puerta correcta.
Establece una tabla para los valores de verdad de los tres letreros y, en base a ella, justifica
la historieta anterior, e indica razonadamente la puerta que eligió el prisionero.
Ejercicio 22. En una isla habitan dos tribus de nativos, A y B. Todos los miembros de la
tribu A siempre dicen la verdad, mientras que todos los de la tribu B siempre mienten. Llegamos
a esta isla y le preguntamos a un nativo si allı́ hay oro, a lo que nos responde:
Hay oro en la isla si y sólo si yo siempre digo la verdad
¿Hay oro en la isla? ¿Podemos determinar a qué tribu pertenece el nativo que nos respondió?
Ejercicio 23. Tres niños, Manolito, Juanito y Jesuli, son sorprendidos después de haberse
roto el cristal de una ventana cerca de donde estaban jugando. Al preguntarles si alguno de
ellos lo habı́a roto, respondieron lo siguiente:

Manolito: “Juanito lo hizo, Jesuli es inocente”.

Juanito: “Si Manolito lo rompió, entonces Jesuli es inocente”.
Jesuli: “Yo no lo hice, pero uno de los otros dos sı́ lo rompió”.

¿Son consistentes las afirmaciones anteriores? Si se comprueba que ninguno de los niños
rompió el cristal, ¿quiénes han mentido? Si se asume que todos dicen la verdad, ¿quién rompió
el cristal?
Ejercicio 24. Demostrar o refutar las siguientes proposiciones:

1. Para todo conjunto de fórmulas S, S |= S.

2. Para todo conjunto S1 y toda fórmula F , si S1 |= F y S1 ⊆ S2 , entonces S2 |= F .
3. Para todo conjunto S1 y fórmulas F, G, si S |= F y {F } |= G, entonces S |= G.

5
Lógica de Primer Orden
Ejercicio 25. Formalizar las siguientes argumentaciones en Lógica de Primer Orden (si es
necesario, con igualdad):

1. Existe una persona en la Feria tal que si dicha persona paga, entonces todas las personas
pagan.
2. Sócrates es un hombre. Los hombres son mortales. Luego, Sócrates es mortal.
3. Hay estudiantes inteligentes y hay estudiantes trabajadores. Por tanto, hay estudiantes
inteligentes y trabajadores.
4. Todos los participantes son vencedores. Hay como máximo un vencedor. Hay como máxi-
mo un participante. Por lo tanto, hay exactamente un participante.
5. Juan teme a Marı́a. Pedro es temido por Juan. Luego, alguien teme a Marı́a y a Pedro.
6. Los hermanos tienen el mismo padre. Juan es hermano de Luis. Jorge es padre de Luis.
Por tanto, Jorge es padre de Juan.
7. Los aficionados al fútbol aplauden a cualquier futbolista extranjero. Juanito no aplaude a
futbolistas extranjeros. Por tanto, si hay algún futbolista extranjero nacionalizado español,
Juanito no es aficionado al fútbol.
8. Toda persona pobre tiene un padre rico. Por tanto, existe una persona rica que tiene un
abuelo rico.
9. Todo lo existente tiene una causa. Luego hay una causa de todo lo existente.
10. Todos los robots obedecen a los amigos del programador jefe. Alvaro es amigo del pro-
gramador jefe, pero Benito no le obedece. Por tanto, Benito no es un robot.
11. Supongamos conocidos los siguientes hechos acerca del número de aprobados de dos asig-
naturas A y B:
a) Si todos los alumnos aprueban la asignatura A, entonces todos aprueban la asigna-
tura B.
b) Si algún delegado de la clase aprueba A y B, entonces todos los alumnos aprueban
A.
c) Si nadie aprueba B, entonces ningún delegado aprueba A.
d ) Si Manuel no aprueba B, entonces nadie aprueba B.
Por tanto, si Manuel es un delegado y aprueba la asignatura A, entonces todos los alumnos
aprueban las asignaturas A y B.
12. Carlos afeita a todos los habitantes de Sevilla que no se afeitan a sı́ mismo y sólo a ellos.
Carlos es un habitante de Sevilla Por consiguiente, Carlos no afeita a nadie.

6
Ejercicio 26. Determina las variables libres y ligadas de las siguientes fórmulas:

1. ∀x∃y[p(x, y) → p(x, z) ∨ ∃z(p(y, z) ∧ p(x, y))]

2. ∃x∃z[p(x, y) → p(x, z) ∧ ∃x(p(y, z) ∧ p(x, y))]
3. ∀x∃z[p(x, y) → p(x, z) → ∃y(p(y, z) ∧ p(x, y))]

Ejercicio 27. Calcular el conjunto de variables libres y el conjunto de variables ligadas de:

1. ∀x(P (x) → R(x, y)) → (∃yP (y) → R(x, z)).

2. ∀x(P (x) → ∃yR(x, y)).
3. ∀z(P (x) → R(x, y)).

Ejercicio 28. Determinar si las siguientes fórmulas son abiertas o cerradas:

(1) ∀x(P (x) → ∃yR(x, y)) (2) ∃xR(x, y) ∨ ∀yP (y).

Ejercicio 29. Determina, en cada caso, si la variable que se indica es sustituible por el
término propuesto en la siguiente fórmula del lenguaje de la Aritmética LA = {0, 1, +, ·, <}:

∀w (x = (y + z) · w) ∧ (∃x (x = z + 0) ∨ ∃y (w + x = y · z))

1. w por x + z 3. w por z + 1 5. x por x + y 7. y por x + y

2. y por z + (w + 1) 4. y por z + 1 6. w por z + w 8. x por z + (w + 1)

Ejercicio 30. Sea L un lenguaje de primer orden con dos sı́mbolos de predicado, P (de
aridad 1) y Q (de aridad 2) y un sı́mbolo de función, f , de aridad 1. Sea M la L–estructura
con universo |M | = {a, b, c, d} e interpretaciones:

P M = {a, b}, QM = {(a, b), (b, b), (c, b)}, f M (a) = b, f M (b) = b, f M (c) = a y f M (d) = c

Decide cuáles de las siguientes fórmulas de L se satisfacen en M :

U = {∀x (P (x) → ∃yQ(y, x)), ∀x Q(f (x), x), ∀x (Q(f (x), x) → Q(x, x)),

∀x∀y (Q(x, y) → P (x)), ∀x∃y (Q(x, y) ∨ Q(y, x))}

Ejercicio 31. Consideremos un LPO con un sı́mbolo de función f y sı́mbolos de predicado

P (·), R(·, ·). Consideremos la interpretación representada en el siguiente diagrama, donde las
flechas sólidas representan f I , las flechas punteadas RI , y P I es el conjunto de figuras negras:

Evaluar las siguientes fórmulas, mostrando todos los pasos:

1. ∀x(P (x) ∨ ∃yR(y, x))

2. ∀x(P (x) ↔ ¬P (f (f (x))))

7
 Ejercicio 32. Consideremos el lenguaje L = {A, F, P, c}, siendo A y F predicados de
aridad 1, P un predicado binario y c una constante. Sea U el siguiente conjunto de fórmulas:

U = {A(c) → ∃y (A(y) ∧ P (y, c))), ∀x (F (x) → ¬∃y (A(y) ∧ P (x, y))), F (c)}

Sea M la L–estructura con universo M = {0, 1, 2, 3} e interpretaciones:

cM = 0, AM = {0, 1, 2}, F M = {0, 1, 3}, y P M = {(0, 3), (1, 0), (1, 2), (2, 3)}.

1. Decide razonadamente qué fórmulas de U son válidas en M y cuáles no lo son.

2. Modifica razonadamente la interpretación F M para que M |= U .

Ejercicio 33. Consideremos el lenguaje de primer orden con igualdad:

LF = {pepe, pepa, pepi, pd, md, pm, P RG, HRO, HRA, M, H, CAS}
donde, pd1 , md1 y pm2 son sı́mbolos de función, y M 1 , H 1 , HRO2 , HRA2 , P RG2 y CAS 2 son
sı́mbolos de predicado (los superı́ndices expresan la aridad).
Supóngase que: pd(x) es el padre de x, md(x) es la madre de x, pm(x, y) es la persona de
mayor edad entre x e y (o x si tienen la misma edad). H(x): “x es un hombre”; M (x): “x es una
mujer”; P RG(x, y): “x es un progenitor de y”; HRO(x, y): “x es hermano de y”; HRA(x, y):
“x es hermana de y”; CAS(x, y): “x está casado/a con y”.
1. Escribe fórmulas de LF que expresen las siguientes afirmaciones:

a) Pepi es hija de Pepe y Pepa.

b) Un abuelo siempre es de mayor edad que cualquiera de sus nietos.
c) Pepe tiene exactamente 2 hijos.
d ) Pepe tiene al menos un cuñado.
e) La suegra de Pepa es la madre de Pepe.
f ) Pepi tiene una prima y un primo.
g) Todo hijo de Pepi es nieto de Pepe.
h) Pepa es la abuela materna de toda hija de Pepi.

2. Expresa en lenguaje natural el sentido de las siguientes fórmulas de LF .

a) ∃x (x 6= pepe ∧ CAS(x, pepa) ∧ ¬P ROG(pepi, x))
b) ∃x∃y (HRO(x, y) ∧ CAS(pepe, y) ∧ ∀z(P RG(x, z) → M (z)))
c) ∀x (HRA(pepa, md(x)) ∨ HRA(pepa, pd(x)) → ∀y¬CAS(x, y))
d ) pd(pepi) = pepe ∧ ∃x(CAS(x, pepi) ∧ ¬∃y (HRO(y, x) ∨ HRA(y, x)))
e) ∃x1 ∃x2 [pd(md(x1 )) = pepe∧pd(md(x2 )) = pepe∧∀x (pd(md(x)) = pepe → x = x1 ∨x =
x2 )]

8
 Ejercicio 34. ¿Cuáles de los siguientes conjuntos de fórmulas son consistentes? (en cada
caso, suponemos que P , Q y R son predicados de la aridad correcta).
1. {∃x Q(x), ∀x (Q(x) → R(x)), ∀x¬R(x)}
2. {∃y∀x P (x, y), ∀x¬P (x, x)}
3. {∀x∀y (P (x, y) → P (y, x)), ∀x¬P (x, x), ∃x∃y P (x, y)}
4. {∀x∃y P (x, y), ∀x¬P (x, x)}
5. {∃x Q(x), ∀x¬Q(x)}
Ejercicio 35. Demostrar o refutar los siguientes asertos:

1. F es válida syss ¬F es insatisfactible.

2. Si F es válida, entonces F es satisfactible.
3. Si F es satisfactible, entonces ¬F es insatisfactible.
4. Sea F una fórmula de L y x1 , . . . , xn las variables libres de F . Entonces, F es válida syss
∀x1 . . . ∀xn F es válida.
5. Sea F una fórmula de L y x1 , . . . , xn las variables libres de F . Entonces, F es satisfactible
syss ∃x1 . . . ∃xn F es satisfactible.

Ejercicio 36. Decide si son correctas o no las siguientes afirmaciones:

1. {∀x (P (x) ∨ Q(x))} |= ∀x P (x) ∨ ∀x Q(x)
2. {∀x (P (x) → Q(x))} |= ∀x P (x) → ∀x Q(x)
3. {∀x P (x) → ∀x Q(x)} |= ∀x (P (x) → Q(x))
4. {¬∀x (P (x) ∧ Q(x))} |= ∃x¬P (x) ∧ ∃x¬Q(x)
5. {∃x P (x) ∧ ∃x Q(x)} |= ∃x (P (x) ∧ Q(x))
6. {∀x (P (x) ∨ Q(f (x)))} |= ∀x (P (x) ∨ Q(x))

Ejercicio 37. Decidir si se verifican las siguientes relaciones de consecuencia lógica:

1. ∀xP (x) |= P (y).

2. P (y) |= ∀xP (x).
3. {∀x(P (x) → Q(x)), P (c)} |= Q(c).
4. {∀x(P (x) → Q(x)), Q(c)} |= P (c).
5. {∀x(P (x) → Q(x)), ¬Q(c)} |= ¬P (c).
6. {P (c), ¬P (d)} |= c 6= d.

Ejercicio 38. Formaliza el siguiente argumento: “Si una ciudad es vecina de otra, entonces
la segunda es vecina de la primera. Sevilla es vecina de Cádiz. Por tanto, Cádiz es vecina de
Sevilla” ¿Es válido?

9
Ejercicio 39. Representa en el lenguaje de la Aritmética, las siguientes propiedades:
1. y es divisible por x.
2. Todo número es divisible por sı́ mismo.
3. y tiene exactamente dos divisores.
4. x es un número par.
5. x es un número primo.
6. x es potencia de 2 (tenga en cuenta que 2 no es una constante del lenguaje).
7. Dada una fórmula F (x), u es el menor elemento que satisface F .

Ejercicio 40. Sea el lenguaje de primer orden L = {C, T, E, IZQ, DER, a, b}, donde
C, T, E son sı́mbolos de predicado de aridad 1, IZQ, DER son sı́mbolos de predicado de
aridad 2, y a, b son sı́mbolos de constante.
En este ejercicio, una cinta es una estructura para el lenguaje L cuyo universo puede ser
descrito por una lista (posiblemente infinita) de figuras (cuadrados, triángulos y estrellas) y la
interpretación de los sı́mbolos de predicado es la natural si suponemos que C(x) expresa “x es
un cuadrado”, T (x) expresa “x es un triángulo”, E(x) expresa “x es una estrella”, IZQ(x, y)
expresa “x está a la izquierda de y” y DER(x, y) expresa “x está a la derecha de y”.
Consideramos las tres cintas siguientes:
M1   F 4 
a b

M2 4 F 4  4 4
b a

M3    
a
b

1. Estudia la validez de las siguientes fórmulas en cada una de las cintas anteriores:
ψ1 : ∀x [E(x) → ∃y (C(y) ∧ IZQ(x, y))]
ψ2 : ∃x [¬T (x) ∧ IZQ(x, a) ∧ DER(b, x)]
ψ3 : ∃x [C(x) ∧ (∃y (T (y) ∧ DER(y, x)) ↔ ∀y (T (y) → DER(y, x)))]
ψ4 : ∀x∃y IZQ(x, y)
2. Para cada una de las siguientes fórmulas, describe una cinta en la que sea válida:
ϕ1 : C(a) ∨ [¬E(b) ∧ (T (b) → ∃x C(x))]
ϕ2 : ∀x [C(x) → ∃y (T (y) ∧ IZQ(y, x))]
ϕ3 : ∀x [T (x) ↔ (∃y (E(y) ∧ IZQ(y, x))]
ϕ4 : ∃x [E(x) ∧ ∀y (C(y) → ¬DER(y, x))]
3. Describe, si es posible, una cinta en la que sean válidas todas las fórmulas del apartado
anterior. ¿Es consistente el conjunto U = {ϕ1 , ϕ2 , ϕ3 , ϕ4 }?

10