Matemática Discreta y Lógica Matemática I

Doble Grado en Ingeniería Informática - Matemáticas

Doble Grado en Administración y Dirección de Empresas - Ingeniería Informática
Grados en Ingeniería Informática, Ingeniería del Software, Ingeniería de Computadores
Examen Final - Febrero 2021

NOMBRE Y APELLIDOS:
GRUPO:

Lee atentamente las siguientes instrucciones:

Escribe tu nombre, apellidos y grupo en el lugar indicado en esta hoja.
NO puedes usar calculadora. Desconecta el teléfono móvil (si lo tienes contigo).
El examen durará 2 horas y media estrictamente.
Cada una de las cuatro primeras preguntas es tipo test y tiene una única respuesta correcta. Cada pre-
gunta de ellas respondida correctamente puntuará 0,5 puntos. Cada pregunta respondida incorrectamente
puntuará -0,15 puntos. Las preguntas sin contestar puntuarán 0 puntos. La puntuación total del test
será, como mínimo, de 0 puntos, nunca será negativa. Deja totalmente clara la respuesta escogida, o
bien que no quieres contestar una pregunta, sobre todo cuando haya alguna tachadura.
Cada una de las preguntas a desarrollar restantes vale 1,5 puntos, salvo la séptima, que vale 1 punto.
El examen se calificará sobre 9 puntos. A esta nota se le sumará la evaluación por curso (de 0 a 1 punto).

Preguntas de Test

1 (0.5 puntos) Sean a, b, c ∈ Z tales que a|(b · c). Entonces siempre sucede que

a | (b + c)
a | mcd(b, c)
(a | b) o (a | c)
x Ninguna de las anteriores.

Solución (d)
(a) es falsa.
Contraejemplo. Sea a = 6, b = 2, c = 3. a = 6 | (b · c = 2 · 3 = 6)
pero a = 6 - (b + c = 5)
(b) es falsa.
Contraejemplo. Sea a = 6, b = 2, c = 3. mcd(b, c) = mcd(2, 3) = 1
pero a = 6 - mcd(b, c) = 1
(c) es falsa.
Contraejemplo. Sea a = 6, b = 2, c = 3.
a=6-b=2ya=6-c=3
2 (0.5 puntos) Dados los conjuntos {x ∈ R | − 5 < x < 5}, {X ∈ P(N)||X| = 2} y Q × Z, marca la
respuesta correcta:

Los tres conjuntos son no numerables.

x El primero es el único no numerable.
El primero y el tercero son los únicos no numerables.
El primero y el segundo son los únicos no numerables.

Solución (b)
{x ∈ R| − 5 < x < 5} = (−5, 5) es un intervalo de R por lo que es no numerable.
{X ∈ P(N)||X| = 2} es numerable. Vamos a demostrarlo.
Podemos definir f : {X ∈ P(N)||X| = 2} −→ N × N inyectiva
f ({a < b}) = (a, b)
Es inyectiva. Si f ({a < b}) = f ({c < d}) =⇒ (a, b) = (c, d) =⇒ a = c, b = d =⇒ {a < b} = {c < d}.
Podemos, por tanto, definir una función inyectiva {X ∈ P(N)||X| = 2} −→ N × N ∼c N (la
composición de una función inyectiva con una biyección es inyectiva) =⇒ {X ∈ P(N)||X| = 2} es
numerable aplicando el teorema:

1. Teorema

a) A es numerable sii existe una inyección f : A −→ N. (A ≤c N).

b) A 6= ∅, A es numerable sii existe una función suprayectiva g : N −→ A.

Q × Z es el producto cartesiano de dos conjuntos numerables y, en consecuencia, es numerable.

3 (0.5 puntos) Sea A un conjunto finito y sea f : A → B. Definimos una relación de equivalencia
R sobre A como
xRy ⇐⇒ f (x) = f (y)

Para que |A/R| = |A| :

f tiene que ser suprayectiva.

x f tiene que ser inyectiva.
f tiene que ser biyectiva.
Se verifica siempre, cualquiera que sea f .

Solución (b) |A/R| = |A| =⇒ f inyectiva.

(a) es falsa.
Contraejemplo. Sean A = {0, 1} y B = {a, b, c} y f : A −→ B definida por f (0) = a, f (1) = b
0 6 R1 ya que f (0) 6= f (1) =⇒ [0] 6= [1] =⇒ |A/R| = |A| = 2 pero f no es suprayectiva ya que
im(f ) = {a, b} =
6 B.
(c) es falsa.
Contraejemplo. El anterior sirve como contraejemplo ya que al no ser suprayectiva tampoco es
biyectiva. A = {0, 1} y B = {a, b, c} y f : A −→ B definida por f (0) = a, f (1) = b
0 6 R1 ya que f (0) 6= f (1) =⇒ [0] 6= [1] =⇒ |A/R| = |A| = 2 pero como f no es suprayectiva al ser
im(f ) = {a, b} =
6 B =⇒ f no es biyectiva.
 (d) es falsa.
Contraejemplo. A = {0, 1} y B = {a}. Sea f : A −→ B definida por f (0) = f (1) = a
0R1 ya que f (0) = f (1) =⇒ [0] = [1] =⇒ |A/R| = 1 < |A| = 2.
(b) |A/R| = |A| =⇒ f inyectiva.
Vamos a demostrarlo por reducción al absurdo. Supongamos que f no es inyectiva, es decir existen
x, y ∈ A tal que x 6= y y f (x) = f (y) =⇒ xRy =⇒ [x] = [y] =⇒ |A/R| < |A|. Contradicción.

4 (0.5 puntos) Sean (A, v1 ) y (B, v2 ) conjuntos totalmente ordenados tales que |A|, |B| ≥ 2. Si
definimos la relación binaria en A × B

(x, y) v (x0 , y 0 ) ⇐⇒ x v1 x0 ∧ y v2 y 0

Señala la respuesta correcta:

v no es una relación de orden.

x v es una relación de orden pero no es total.
v es una relación de orden total.
v es una relación de orden estricto.

Solución (b)
Relación de orden en A × B.
R es una relación de orden ⇐⇒ R es reflexiva, antisimétrica y transitiva.
Reflexiva: ∀(x, y) ∈ A × B, (x, y) v (x, y) ⇐⇒ x v1 x y y v2 y. Se verifica trivialmente ya que
v1 y v2 son relaciones de orden y cumplen la reflexiva para x y para y.

Antisimétrica: ∀(x, y), (x0 , y 0 ) ∈ A × B, (x, y) v (x0 , y 0 ) ∧ (x0 , y 0 ) v (x, y) =⇒ (x, y) = (x0 , y 0 )
(x, y) v (x0 , y 0 ) ⇐⇒ x v1 x0 , y v2 y 0

=⇒ x = x0 , y = y 0 =⇒ (x, y) = (x0 , y 0 )
(x0 , y 0 ) v (x, y) ⇐⇒ x0 v1 x, y 0 v2 y

Porque v1 y v2 son antisimétricas

Transitiva:
∀(x, y), (x0 , y 0 ), (x00 , y 00 ) ∈ A × B, (x, y) v (x0 , y 0 ) ∧ (x0 , y 0 ) v (x00 , y 00 ) =⇒ (x, y) v (x00 , y 00 ).
(x, y) v (x0 , y 0 ) ⇐⇒ x v1 x0 , y v2 y 0

=⇒ x v1 x00 , y v2 y 00 =⇒ (x, y) v (x00 , y 00 )
(x0 , y 0 ) v (x00 , y 00 ) ⇐⇒ x0 v1 x00 , y 0 v2 y 00
Porque v1 y v2 son transitivas.

No es un orden total.
Sean x, x0 ∈ A, x 6= x0 (existen porque |A| ≥ 2) luego x v1 x0 ó x0 v1 x por ser v1 orden total.
Supongamos que se verifica x v1 x0 . (Si se verifica x0 v1 x sería análogo.)
Sean y, y 0 ∈ B, y 6= y 0 (existen porque B| ≥ 2) luego y v2 y 0 ó y 0 v2 y por ser v2 orden total.
Supongamos que se verifica y 0 v2 y. (Si se verifica y v2 y 0 sería análogo.)
Entonces ni (x, y) v (x0 , y 0 ) (y 6v y 0 ) ni (x0 , y 0 ) v (x, y) (x0 6v x)

Si se verifica x0 v1 x y y 0 v2 y entonces consideramos (x0 , y) y (x, y 0 )

Ni (x0 , y) v (x, y 0 ) pues (y 6v y 0 ) ni (x, y 0 ) v (x0 , y) ya que (x 6v x0 )
 v no es un orden estricto. Para que v sea un orden estricto tiene que ser antirreflexiva (∀(x, y) ∈
A × B, (x, y) 6v (x, y)) y transitiva.
Ya hemos demostrado que ∀(x, y) ∈ A × B, (x, y) v (x, y) luego es reflexiva y no es antirreflexiva

Preguntas de Desarrollo

5 (1.5 puntos) Dada la siguiente función definida recursivamente


 6 si n = 0
f (n) = 2 si n = 1
6f (n − 2) − f (n − 1) si n ≥ 2


Demuestra por inducción matemática que para todo número natural n, f (n) = 2(2n+1 +(−3)n ).
Indica el tipo de inducción que utilizas.
Solución:
Caso Base: f (0) = 6 = 2(21 + (−3)0 ) = 2(2 + 1) = 2 ∗ 3 = 6 Se verifica.
f (1) = 2 = 2(22 + (−3)1 ) = 2(4 − 3) = 2 Se verifica.

Paso Inductivo S(0), . . . , S(k) =⇒ S(k + 1) (Aplicamos inducción completa porque la definición
recursiva de f (n) depende de f (n − 1) y f (n − 2)) (varios valores previos).

(HI) S(2), . . . , S(k) ≡ f (2) = 2(22+1 + (−3)2 ); . . . ; f (k) = 2(2k+1 + (−3)k )

?
S(k + 1) ≡ f (k + 1) = 2(2k+2 + (−3)k+1 )
h i h
f (k + 1) = 6f (k − 1) − f (k) = 6 2(2k + (−3)k−1 − 2(2k+1 + (−3)k ) = 2 6 ∗ 2k − 2k+1 +
↑
(HI. S(k), S(k − 1) inducción completa)
i h i h i
+(−3)k−1 (6 − (−3)) = 2 3 ∗ 2k+1 − 2k+1 + (−3)k−1 (9) = 2 2k+1 (3 − 1) + (−3)k−1 (−3)(−3) =
= 2(2k+2 + (−3)k+1 )
En el caso base tenemos que incluir n = 0 y n = 1 ya que f (n) = 6f (n − 2) − f (n − 1) y para
n = 2 f (2) = 6f (0) − f (1)
En el paso inductivo escribimos f (k + 1) = 6f (k − 1) − f (k) = 6(2(2k + (−3)k−1 )) − 2(2k+1 + (−3)k )
donde k + 1 ≥ 2 y aplicamos f (k) = 2(2k+1 + (−3)k ) y f (k − 1) = 2(2k + (−3)k−1 ) Tiene que ser
una demostración válida para k + 1 = 2. En este caso se tiene f (2) = 6f (0) − f (1) luego también
tendrá que ser cierto f (1) = 2(22 +(−3)1 ) y f (0) = 2(21 +(−3)0 ). f (0) y f (1) vienen dados por dos
valores independientes luego sólo podemos comprobar si se cumple o no, para ambos, incluyéndolos
en el caso base.

6 (1.5 puntos) Si A, B, C y D son conjuntos cualesquiera, demuestra:

(a) (A \ B) ∩ C = (A ∩ C) \ (B ∩ C)
(b) (A × B) \ (C × D) = ((A \ C) × B) ∪ (A × (B \ D))

Solución
 (a) (A \ B) ∩ C = (A ∩ C) \ (B ∩ C)

(A ∩ C) \ (B ∩ C) = Definición de (A \ B)A ∩ B
= (A ∩ C) ∩ (B ∩ C) = Ley de DeMorgan
= (A ∩ C) ∩ (B ∪ C) = Ley Distributiva
= ((A ∩ C) ∩ B) ∪ ((A ∩ C) ∩ C)) = Ley Asociativa
= ((A ∩ C) ∩ B) ∪ (A ∩ (C ∩ C)) = Ley del Complementario
= ((A ∩ C) ∩ B) ∪ (A ∩ ∅)) = Ley del Conjunto Vacío (A ∩ ∅ = ∅)
= ((A ∩ C) ∩ B) ∪ ∅ = Ley del Conjunto Vacío (A ∪ ∅ = A)
= (A ∩ C) ∩ B = Ley Asociativa
= A ∩ (C ∩ B) = Ley Conmutativa
= A ∩ (B ∩ C) = Ley Asociativa
= (A ∩ B) ∩ C = Definición de (A \ B)
= (A \ B) ∩ C
(b) (A × B) \ (C × D) = ((A \ C) × B) ∪ (A × (B \ D))
⊆)
Sea x ∈ (A × B) \ (C × D) =⇒ x ∈ (A × B), x 6∈ (C × D) =⇒
x = (a, b) con a ∈ A, b ∈ B, x = (a, b) 6∈ (C × D) =⇒ a 6∈ C ó b 6∈ D
Supongamos a ∈ A, a 6∈ C =⇒ a ∈ (A \ C) como b ∈ B =⇒ (a, b) ∈ (A \ C) × B
Supongamos b ∈ B, b 6∈ D =⇒ b ∈ (B \ D) como a ∈ A =⇒ (a, b) ∈ A × (B \ D) luego
x = (a, b) ∈ ((A \ C) × B) ∪ (A × (B \ D))

⊇)
Sea x ∈ ((A \ C) × B) ∪ (A × (B \ D)) =⇒ x ∈ ((A \ C) × B) ó x ∈ (A × (B \ D))
Supongamos x ∈ ((A \ C) × B) =⇒ x = (a, b) con a ∈ (A \ C), b ∈ B =⇒ a ∈ A, a 6∈ C, b ∈ B
=⇒ (a, b) ∈ A × B, (a, b) 6∈ C × D =⇒ x = (a, b) ∈ (A × B) \ (C × D)

Supongamos x ∈ (A × (B \ D)) =⇒ x = (a, b) con a ∈ A, b ∈ (B \ D) =⇒ a ∈ A, b ∈ B, b 6∈ D

=⇒ (a, b) ∈ A × B, (a, b) 6∈ C × D =⇒ x = (a, b) ∈ (A × B) \ (C × D)

7 (1 punto) Sea f : P(N) \ {∅} → P(N) una función definida por f (X) = X \ {mínimo(X)}.
Estudia si f es inyectiva y/o suprayectiva. En cada caso debes demostrar formalmente si se
cumple la propiedad o dar un contraejemplo si no se cumple.

Solución

No es inyectiva.
f inyectiva ⇐⇒ f (X) = f (Y ) =⇒ X = Y
f : P(N) \ {∅} → P(N)
f (X) = X \ {mínimo(X)}
Sea X = {1, 4, 5}, min(X) = 1 =⇒ f (X) = {1, 4, 5} \ {1} = {4, 5}

Sea Y = {2, 4, 5}, min(Y ) = 2 =⇒ f (Y ) = {2, 4, 5} \ {2} = {4, 5}

Se verifica f (X) = f (Y ) pero X 6= Y .

No es suprayectiva
f suprayectiva ⇐⇒ ∀Y ∈ P(N) ∃X ∈ P(N) \ {∅} tal que f (X) = Y
Sea Y = {0}. Vamos a ver que no existe X tal que f (X) = {0}.
Si f (X) = {0} =⇒ X \ {min(X)} = {0} min(X) ∈ X =⇒ X = {min(X), 0} =⇒
min(X) < 0 lo que es imposible pues min(X) ∈ N.
8 (1.5 puntos) Considera la relación R ⊆ Z × Z definida por

x R y ⇐⇒ 4 | (x − y + 2) ∨ 4 | (x − y).

(a) Demuestra que R es una relación de equivalencia.

(b) Describe con precisión la clase de equivalencia de 7, justificando tu respuesta.
(c) ¿Cuántos elementos tiene el conjunto cociente Z/R ? Descríbelo detalladamente.

Solución

(a) R relación de equivalencia ⇐⇒ R es reflexiva, simétrica y transitiva.

Reflexiva: ∀x ∈ Z xRx.
xRx ⇐⇒ 4 | (x − x + 2) ∨ 4 | (x − x). Evidentemente x − x = 0 = 4 ∗ 0 =⇒ 4 | (x − x) =⇒
xRx, ∀x

Simétrica: ∀x, y ∈ Z xRy =⇒ yRx.

xRy ⇐⇒ 4 | (x − y + 2) ∨ 4 | (x − y).
Si se verifica 4 | (x − y) =⇒ (x − y) = 4 ∗ t1 =⇒ (y − x) = 4(−t1 ) =⇒ 4 | (y − x) =⇒ yRx
Si se verifica 4 | (x − y + 2) =⇒ (x − y + 2) = 4 ∗ t2 =⇒ (y − x) = 2 + 4 ∗ (−t2 ) =⇒ (y − x) + 2 =
2 + 4 ∗ (−t2 ) + 2 = 4(−t2 + 1) =⇒ 4 | (y − x + 2) =⇒ yRx

Transitiva: ∀x, y, z ∈ Z xRy ∧ yRz =⇒ xRz.

xRy ⇐⇒ 4 | (x − y + 2) ∨ 4 | (x − y).
yRz ⇐⇒ 4 | (y − z + 2) ∨ 4 | (y − z).

Si se verifica 4 | (x − y) ∧ 4 | (y − z) =⇒ (x − y) = 4 ∗ t1 ∧ (y − z) = 4 ∗ t2 =⇒ x − z =
(x − y) + (y − z) = 4 ∗ t1 + 4 ∗ t2 = 4(t1 + t2 ) =⇒ 4 | (x − z) =⇒ xRz

Si se verifica 4 | (x − y) ∧ 4 | (y − z + 2) =⇒ (x − y) = 4 ∗ t1 ∧ (y − z) + 2 = 4 ∗ t2 =⇒ (x − y) =
4 ∗ t1 ∧ (y − z) = 4 ∗ t2 − 2 =⇒ x − z = (x − y) + (y − z) = 4 ∗ t1 + 4 ∗ t2 − 2 =⇒ x − z + 2 =
4(t1 + t2 ) =⇒ 4 | (x − z) =⇒ xRz

Si se verifica 4 | (x − y + 2) ∧ 4 | (y − z) =⇒ (x − y) + 2 = 4 ∗ t1 ∧ (y − z) = 4 ∗ t2 =⇒
x−z = (x−y)+(y −z) = 4∗t1 −2+4∗t2 =⇒ x−z +2 = 4(t1 +t2 ) =⇒ 4 | (x−z +2) =⇒ xRz

Si se verifica 4 | (x − y + 2) ∧ 4 | (y − z + 2) =⇒ (x − y) + 2 = 4 ∗ t1 ∧ (y − z) + 2 = 4 ∗ t2 =⇒
x−z = (x−y)+(y −z) = 4∗t1 −2+4∗t2 −2 =⇒ x−z = 4(t1 +t2 −1) =⇒ 4 | (x−z) =⇒ xRz

(b) [7] = {y ∈ Z | yR7} = {y ∈ Z | 4 | (7 − y + 2) ∨ 4 | (7 − y)} =

= {y ∈ Z | 4 | (7 − y)} ∪ {y ∈ Z | 4 | (7 − y + 2)} = {..., −5, −1, 3, 7, 11, 15, 19, ..} ∪
{..., −3, 1, 5, 7, 9, 13, 17, ..} = {..., −5, −3, −1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, ..}
(c) ∀x ∈ Z x = 4 ∗ t + r con 0 ≤ r < 4
Si r = 0 =⇒ xR0 ya que x − 0 = 4 ∗ t =⇒ 4 | x − 0 =⇒ x ∈ [0]
Si r = 1 =⇒ xR1 ya que x − 1 = 4 ∗ t + 1 − 1 =⇒ 4 | =⇒ x ∈ [1]
Si r = 2 =⇒ xR0 ya que x − 0 + 2 = (4 ∗ t + 2) + 2 = 4(t + 1) =⇒ 4 | (x − 0) + 2 =⇒ x ∈ [0]
Si r = 3 =⇒ xR1 ya que x−1+2 = x+1 = (4∗t+3)+1 = 4(t+1) =⇒ 4 | (x−1)+2 =⇒ x ∈ [1]
[0] = {..., −4, −2, 0, 2, 4, 6, ...} [1] = {..., −3, −1, 1, 3, 5, 7, ...}
Z/R = {[0], [1]}
9 (1.5 puntos) Sea R una relación sobre N, definida como a R b ⇐⇒ Existe n ∈ N tal que a = bn .

(a) Demuestra que R es una relación de orden.

(b) Sea A = {1, 2, 3, 4, 5, 9}. Dibuja el diagrama de Hasse para el conjunto ordenado(A, R).
(c) ¿Cuáles son los elementos maximales y minimales de A? ¿Tiene máximo y/o mínimo?
Justifica tu respuesta.

Solución

(a) R relación de orden ⇐⇒ R es reflexiva, antisimétrica y transitiva.

Reflexiva: ∀a ∈ N aRa.
aRa ⇐⇒ Existe n ∈ N tal que a = an . Basta tomar n = 1

Antisimétrica: ∀a, b ∈ N aRb ∧ bRa =⇒ a = b.

aRb ⇐⇒ Existe n ∈ N tal que a = bn .
bRa ⇐⇒ Existe m ∈ N tal que b = am .
a = bn = (am )n = amn =⇒ a(1 − amn−1 ) =⇒ a = 0 ó 1 = amn−1
Si a = 0 =⇒ a = 0 = bn y como n ∈ N =⇒ b = 0 = a
Si 1 = amn−1 =⇒ a = 1 ó mn − 1 = 0
Si a = 1 =⇒ b = 1m = 1 ya que m ∈ N =⇒ b = 1 = a
Si mn − 1 = 0 =⇒ mn = 1 =⇒ m = n = 1 ya que m, n ∈ N Por tanto a = b1 = b

Transitiva: ∀a, b, c ∈ N aRb ∧ bRc =⇒ aRc.

aRb ⇐⇒ Existe n ∈ N tal que a = bn .
bRc ⇐⇒ Existe m ∈ N tal que b = cm .
a = bn = (cm )n = cmn =⇒ aRc
(b) Sea A = {1, 2, 3, 4, 5, 9}. Dibuja el diagrama de Hasse para el conjunto ordenado(A, R).
1R4 ya que 1 = 40
1R9 ya que 1 = 90
1R5 ya que 1 = 50
4R2 ya que 4 = 22
9R3 ya que 9 = 32

2 3

4 9 5

(c) ¿Cuáles son los elementos maximales y minimales de A? ¿Tiene máximo y/o mínimo?
Justifica tu respuesta.
1 es el único minimal y por tanto es mínimo.
1 es minimal ya que no existe b ∈ A tal que bR1.
∀a ∈ A 1Ra ya que 1 = a0 =⇒ 1 es mínimo.

2, 3 y 5 son maximales y como hay varios maximales no existe máximo.

2, 3 y 5 son maximales porque no existe b ∈ A tal que 2Rb, 3Rb ó 5Rb.