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

Facultad de Informática - UCM

SOLUCIONES Examen final - Enero 2022

NOMBRE Y APELLIDOS:

GRUPO:

Lee atentamente las siguientes instrucciones:

Escribe tu nombre 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 dura 3 horas.
Cada una de las seis primeras preguntas es tipo test y tiene una única respuesta correcta. Cada pregunta 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 0, nunca negativa. Dejar totalmente clara la respuesta escogida, o que no queréis contestar una
pregunta, sobre todo cuando haya alguna tachadura.
En cada una de las preguntas a desarrollar aparece la puntuación máxima que puede obtenerse al respon-
derlas. La mínima puntuación que puede obtenerse en estas preguntas es 0.

1. Sean a, b, c ∈ Z tales que c 6 | a y c6 | b, entonces:

nunca se tiene que c | (a + b)

x si además c es primo entonces siempre se tiene que m.c.d.(ab, c) = 1
nunca se tiene que c | ab
nunca se tiene que mcd(ab, c) = c .

Solución (b)
Si c es primo =⇒ m.c.d.(ab, c) = 1 ó c.
Si mcd(ab, c) = c =⇒ c | ab =⇒ c| a ó c| b por ser c primo, lo que contradice el enunciado. En
consecuencia, m.c.d.(ab, c) = 1.
Contraejemplo de (a): c = 5 a = 3 b = 2 c 6 | a y c6 | b pero c | (a + b) pues 5 | (a + b) = 5

Contraejemplo de (c): c = 6 a = 3 b = 2 c 6 | a y c6 | b pero c | ab pues 6 | ab = 6

Contraejemplo de (d): c = 6 a = 3 b = 2 c 6 | a y c6 | b pero mcd(ab, c) = c pues mcd(6, c = 6) =

c = 6.

2. Dadas las dos siguientes afirmaciones sobre tres conjuntos cualesquiera A, B y C

(1) ((A \ C) \ B) ∪ ((B \ C) \ A) = (A ∪ B) \ C (2) (A ⊕ B) ∩ B = A ∩ B

Ambas son siempre ciertas.
Ambas son siempre falsas.
Solamente es cierta siempre la primera.
x Solamente es cierta siempre la segunda.

Solución (d)
Contraejemplo: A = {1, 2, 4, 6} B = {2, 3, 4, 5} C = {4, 5, 6, 7}
A \ C = {1, 2} (A \ C) \ B = {1}
B \ C = {2, 3} (B \ C) \ A = {3}
 ((A \ C) \ B) ∪ ((B \ C) \ A) = {1, 3}
A ∪ B = {1, 2, 4, 6, 3, 5} (A ∪ B) \ C = {1, 2, 3}

(A ⊕ B) ∩ B = A ∩ B (A ⊕ B) = (A ∩ B) ∪ (B ∩ A)

(A ⊕ B) ∩ B = ((A ∩ B) ∪ (B ∩ A)) ∩ B = (((A ∩ B) ∩ ((B ∩ A)) ∩ B = ((A ∪ B) ∩ (B ∪ A)) ∩ B =

↑ ↑ ↑ ↑
Def (A ⊕ B) Ley de Morgan Ley de Morgan L. Conmutativa
= ((B ∪ A) ∩ (A ∪ B)) ∩ B = (B ∪ A) ∩ ((A ∪ B) ∩ B) = (B ∪ A) ∩ B = (B ∩ B) ∪ (A ∩ B) =
↑ ↑ ↑ ↑
L. Asociativa Ley Absorción Ley Distributiva (B ∩ B) = ∅
= ∅ ∪ (A ∩ B) = (A ∩ B)
↑
(∅ ∪ D = D)

3. Sean las funciones f, g : ℘(N+ ) × ℘(N+ ) → ℘(N+ ) definidas por

f (A, B) = A ∩ B y g(A, B) = A ∪ B respectivamente.
Consideramos los tres conjuntos g −1 (∅), f −1 (∅) y g −1 (∅) ∩ f −1 (∅)

El primero y el tercero son no numerables

x El segundo conjunto es el único no numerable
Los tres conjuntos son numerables
El tercero es el único numerable

Solución (b)
g −1 (∅) = {(A, B)|g(A, B) = A ∪ B = ∅} A ∪ B = ∅ =⇒ A = B = ∅ porque A, B ⊆ A ∪ B = ∅.
g −1 (∅) = {(A, B)|A ∪ B = ∅} = {(∅, ∅)} Es un conjunto finito.

f −1 (∅) = {(A, B)|f (A, B) = A ∩ B = ∅} Como A ∩ ∅ = ∅ =⇒ ∀A ⊆ ℘(N+ ) (A, ∅) ∈ f −1 (∅) =⇒

℘(N+ ) × {∅} ⊆ f −1 (∅) Luego, al ser ℘(N+ ) ∼c ℘(N+ ) × {∅}, ℘(N+ ) × {∅} es un conjunto no
numerable, y por tanto f −1 (∅) es no numerable.

g −1 (∅) ∩ f −1 (∅) = {(∅, ∅)} ∩ f −1 (∅) = {(∅, ∅)} también es un conjunto finito.

4. Sea A = {a, b, c, d, e}. Si tenemos una relación de equivalencia definida sobre A tal que [a] = {a, b}
y sabemos que la partición a la que da lugar, está formada por tres conjuntos, entonces el número de
relaciones de equivalencia distintas definidas sobre A y compatibles con las condiciones anteriores
son:

1
2
x 3
4

Solución (c)
A = {a, b, c, d, e} si [a] = {a, b} y sabemos que la partición determinada por R tiene tres conjuntos,
entonces R tiene exactamente tres clases de equivalencia.
Tenemos las siguientes posibilidades.
 [a] = {a, b} [c] = {c} [d] = {d, e}

[a] = {a, b} [c] = {c, d} [e] = {e}

[a] = {a, b} [c] = {c, e} [d] = {d}

5. Para cada n ∈ N, sea el conjunto Mn = {n · k|k ≥ 2}. Sea la familia de conjuntos C = {Mi |i ≥ 2}

x
S T
C = N \ ({0, 1} ∪ {x|x primo }); C=∅
S T
C = N; C=∅
S T
C = {x|x > 1}; C = {0}
S T
C = N \ {x|x primo }; C = {0}

Solución (a)
C = {Mi |i ≥ 2} = {M2 , M3 , M4 , . . .}
Mn = {n · k|k ≥ 2} =⇒ M2 = {2 · k|k ≥ 2} = {4, 6, 8, 10, . . .}
M3 = {3 · k|k ≥ 2} = {6, 9, 12, 15, . . .}
M4 = {4 · k|k ≥ 2} = {8, 12, 16, 20, . . .}
M5 = {5 · k|k ≥ 2} = {10, 15, 20, 25, . . .} . . .
S
C = N \ ({0, 1} ∪ {x|x primo })
S
Si 0 = m · k m, k ∈ N =⇒ m = 0 ó k = 0 =⇒ 0 6∈ Mi i ≥ 2 =⇒ 0 6∈ C
S
Si 1 = m · k m, k ∈ N =⇒ m = 1 y k = 1 =⇒ 1 6∈ Mi i ≥ 2 =⇒ 1 6∈ C
p primo, si p = m · k m, k ∈ N =⇒ (m = 1 y k = p) ó (m = p y k = 1 =⇒ p 6∈ Mi i ≥ 2 =⇒
Sea S
p 6∈ C
S
Sea m ∈ N, m ≥ 2 y m no primo. Entonces m = p · t, t ≥ 2 =⇒ m ∈ Mp =⇒ m ∈ C

T
C=∅
T
Sea m ∈ C. Por lo demostrado anteriormente, m no es primo y lo descomponemos en producto
es infinito, existe un primo p0 distinto
de primos. m = p1 · p2 · · · · · pr . Como el conjunto de primos T
0
de los anteriores y m 6= p · k, ∀k ≥ 2 =⇒ m 6∈ Mp0 =⇒ m 6∈ C
Si fuese m = p1 ·p2 ·· · ··pr = p0 ·k =⇒ p0 | p1 ·p2 ·· · ··pr =⇒ ∃j p0 | pj (por ser p0 primo) =⇒ p0 = pj .
Contradicción.

6. Dada la siguiente relación R ⊆ (N2 × N2 ) × (N2 × N2 ) definida como

(a, b) R (c, d) ⇐⇒ b = d y existe un primo p tal que p | a y p | c donde N2 = {n ∈ N|n ≥ 2}

Es una relación de orden parcial

Es una relación de equivalencia
Es una relación de orden total
x Ninguna de las tres afirmaciones anteriores es cierta

Solución (d)
Vamos a ver que no se verifica la propiedad transitiva, por lo que no es ni relación de orden (ni
parcial ni total) ni relación de equivalencia.
Transitiva: ∀(a, b), (c, d), (e, f ) (a, b) R (c, d) ∧ (c, d) R (e, f ) =⇒ (a, b) R (e, f )
(4, 5) R (6, 5) y (6, 5) R (9, 5) pero (4, 5) 6 R (9, 5)
 (4, 5) R (6, 5) ya que existe un primo p = 2 tal que 2 | 4 y 2 | 6
(6, 5) R (9, 5) ya que existe un primo q = 3 tal que 3 | 6 y 3 | 9 pero
(4, 5) 6 R (9, 5) ya que si p primo y p | 4 =⇒ p = 2 pero 2 6 | 9.

7. (1,5 puntos) Demuestra por inducción que para todo numero natural n ≥ 2,
n  
Y 1 n+1
1− 2 =
i 2n
i=2

Indica qué tipo de inducción utilizas y justifica los pasos de tu demostración, en especial indica
cuándo aplicas la hipótesis de inducción y por qué puedes aplicarla.
Solución
Lo demostramos por inducción simple:
Caso Base:
Q2  1 1 3 2+1
n = 2 S(1) ≡ i=2 1− 2
=1− = = Luego se cumple.
i 4 4 2·2
Qk  1 k+1
(HI) S(k) ≡ i=2 1 − 2 = (Usamos inducción simple).
i 2k
?
Qk+1  1 k+2
Paso Inductivo S(k + 1) ≡ i=2 1 − 2 =
i 2(k + 1)
Qk+1  1  h Qk  1 i 1  k + 1  (k + 1)2 1 
i=2 1 − 2 = i=2 1 − 2 1− = · − =
i i (k + 1)2 2k (k + 1)2 (k + 1)2
↑


Qk
H.I. 1 k+1
i=2 1− i2 = 2k
k + 1  k 2 + 2k + 1 − 1  (k + 1)k(k + 2) (k + 2)
= · 2
= 2
=
2k (k + 1) 2k(k + 1) 2(k + 1)

Podemos aplicar inducción simple porque se verifica la base de la induccióny la expresión para k+1
Qk+1 1  h Qk 
depende de la expresión para el valor inmediatamente anterior k ( i=2 1 − 2 = i=2 1 −
i
1 i 1 
2
1−
i (k + 1)2
8. (1,5 puntos) Sean las funciones f : ℘({1, 2, 3}) → ℘({2, 3}) y g : ℘({2, 3}) → ℘({1, 2, 3})
definidas por
f (A) = A \ {1} y g(A) = A ∪ {1} respectivamente.

a) Para cada una de ellas demuestra si es inyectiva y/o sobreyectiva.

b) Demuestra que f ◦ g 6= id℘({1,2,3})

Solución

a) f : ℘({1, 2, 3}) → ℘({2, 3}) No es inyectiva.

f inyectiva ⇐⇒ f (X) = f (Y ) =⇒ X = Y
Sea X = {1, 2, 3} =⇒ f (X) = {1, 2, 3} \ {1} = {2, 3}

Sea Y = {2, 3} =⇒ f (Y ) = {2, 3} \ {1} = {2, 3}

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

 Si es suprayectiva
f suprayectiva ⇐⇒ ∀Y ∈ ℘({2, 3} ∃X ∈ ℘({1, 2, 3} tal que f (X) = Y
Sea Y ∈ ℘({2, 3}. Basta tomar X = Y pues f (X) = X \ {1} = X = Y pues 1 6∈ X ∈
℘({2, 3}.
g : ℘({2, 3}) → ℘({1, 2, 3}) Si es inyectiva.
g inyectiva ⇐⇒ g(X) = g(Y ) =⇒ X = Y
Sean X, Y ∈ ℘({2, 3} tal que g(X) = X ∪ {1} = g(Y ) = Y ∪ {1}

Vamos a demostrar X = Y .
⊆)
Sea x ∈ X =⇒ x ∈ X ∪ {1} = Y ∪ {1} =⇒ x ∈ Y ya que x 6= 1 pues X ∈ ℘({2, 3}

⊇)
Sea y ∈ Y =⇒ y ∈ Y ∪ {1} = X ∪ {1} =⇒ y ∈ X ya que y 6= 1 pues Y ∈ ℘({2, 3}
No es suprayectiva
g suprayectiva ⇐⇒ ∀Y ∈ ℘({1, 2, 3} ∃X ∈ ℘({2, 3} tal que g(X) = Y
Contraejemplo. Sea Y = {2, 3}. No existe X ∈ ℘({1, 2, 3} tal que g(X) = Y ya que si
g(X) = X ∪ {1} = Y =⇒ 1 ∈ Y pero 1 6∈ {2, 3}.
b) f ◦ g 6= id℘({1,2,3})
Dos funciones h, h0 son iguales si sus dominios coinciden y ∀x ∈ dom(h) h(x) = h0 (x)
f ◦ g({2, 3}) = g(f ({2, 3}) = g({2, 3} \ {1}) = g({2, 3}) = {2, 3} ∪ {1} = {1, 2, 3}
id℘({1,2,3}) ({2, 3}) = {2, 3} Luego f ◦ g({2, 3}) 6= id℘({1,2,3}) ({2, 3}) =⇒ f ◦ g 6= id℘({1,2,3}) .

9. (1,5 puntos) Sean A = {0, 1, 3}, F = ℘(A) \ {∅} y la función f : F → N definida por
f (C) = suma de los elementos de C.
Sea R ⊆ F × F definida como XRY ⇔ f (X) + f (Y ) es par

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

b) Calcula razonadamente [{3}] y [{1, 0}]
c) ¿Cuántos elementos tiene el conjunto cociente F/R ?. Razona tu respuesta.

Solución

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

Reflexiva: ∀X ∈ F XRX.
XRX ⇐⇒ f (X) + f (X) es par. Evidentemente f (X) + f (X) = 2f (X) =⇒ XRX, ∀X ya
que 2f (X) es par.

Simétrica: ∀X, Y ∈ F XRY =⇒ Y RX.

XRY ⇐⇒ f (X) + f (Y ) es par ⇐⇒ f (X) + f (Y ) = 2t.
Si se verifica f (X) + f (Y ) = 2t =⇒ f (Y ) + f (X) = f (X) + f (Y ) = 2t =⇒ Y RX (Prop.
Conmutativa)

Transitiva: ∀X, Y, Z ∈ F XRY ∧ Y RZ =⇒ XRZ.

XRY ⇐⇒ f (X) + f (Y ) es par ⇐⇒ f (X) + f (Y ) = 2t1 .
Y RZ ⇐⇒ f (Y ) + f (Z) es par ⇐⇒ f (Y ) + f (Z) = 2t2 .

f (X) + f (Y ) = 2t1
=⇒ f (X)+f (Y )+f (Y )+f (Z) = f (X)+2f (Y )+f (Z) = 2t1 +2t2 =⇒
f (Y ) + f (Z) = 2t2
f (X) + f (Z) = 2(t1 + t2 − f (Y )) luego es par y por tanto se verifica XRZ .
b) [{3}] = {X ∈ F |XR{3}} = {X ∈ F |f (X) + f ({3}) es par } = {X ∈ F |f (X) + 3 es par } =
{X ∈ F |f (X) es impar } = {{3}, {1}, {0, 1}, {0, 3}}
 [{1, 0}]{X ∈ F |XR{1, 0}} = {X ∈ F |f (X)+f ({1, 0}) es par } = {X ∈ F |f (X)+1 es par } =
{X ∈ F |f (X) es impar } = {{3}, {1}, {0, 1}, {0, 3}}
[{3}] = [{1, 0}]
c) F/R = {[{0}], [{1}]}
[{0}] = {X ∈ F |XR{0}} = {X ∈ F |f (X) + f ({0}) es par } = {X ∈ F |f (X) + 0 es par } =
{X ∈ F |f (X) es par } = {{0}, {1, 3}, {0, 1, 3}}
[{1}] = {X ∈ F |XR{1}} = {X ∈ F |f (X) + f ({1}) es par } = {X ∈ F |f (X) + 1 es par } =
{X ∈ F |f (X) es impar } = {{1}, {3}, {0, 3}, {0, 1}}
F/R tiene exactamente dos elementos porque ∀X ∈ F, f (X) es siempre par en cuyo caso
X ∈ [{0}] ó es impar y X ∈ [{1}].

10. (1,5 puntos) Sean A = {1, 2, 3, 4, 6}, F = {X ∈ ℘(A)||X| = 2}

Sea R ⊆ F × F definida como

 min(X) = min(Y )
XRY ⇔ min(X) < min(Y ) ó y
max(Y ) | max(X) (divide a)


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

b) Dibuja su diagrama de Hasse
c) Determina, razonadamente los extremos y extremales de (F, R).

Solución

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

Reflexiva: ∀X ∈ F XRX. 
 min(X) = min(X)
XRX ⇐⇒ min(X) < min(X) ó y
max(X) | max(X)

Evidentemente min(X) ≮ min(X) pero min(X) = min(X) y max(X) | max(X) =⇒
XRX, ∀X ∈ F

Antisimétrica: ∀X, Y ∈ F XRY ∧ Y RX =⇒ X = Y .


 min(X) = min(Y )
XRY ⇔ min(X) < min(Y ) ó y
max(Y ) | max(X)


 min(X) = min(Y )
Y RX ⇔ min(Y ) < min(X) ó y
max(X) | max(Y )

Si se verificase min(X) < min(Y ) sería incompatible con min(Y ) < min(X) y con min(Y ) =
min(X)
 luego si XRY y también Y RX sólo puede ser cierto si min(X) = min(Y ) y
max(Y ) | max(X)
=⇒ max(X) = max(Y ) ya que ambos son positivos.
max(X) | max(Y )

min(X) = min(Y )
Como |X| = |Y | = 2 y =⇒ X = Y .
max(X) = max(Y )

Transitiva: ∀X, Y, Z ∈ F XRY ∧ Y RZ =⇒ XRZ.


min(X) = min(Y )
XRY ⇔ min(X) < min(Y ) ó
max(Y ) | max(X)

min(Y ) = min(Z)
Y RZ ⇔ min(Y ) < min(Z) ó
max(Z) | max(Y )

Si se verifica (min(X) < min(Y )) ∧ (min(Y ) < min(Z)) =⇒ min(X) < min(Z) =⇒ XRZ
 
min(Y ) = min(Z)
Si se verifica (min(X) < min(Y )) ∧ =⇒ min(X) < min(Y ) =
max(Z) | max(Y )
min(Z) =⇒ min(X) < min(Z) =⇒ XRZ

min(X) = min(Y )
Si se verifica ∧ (min(Y ) < min(Z)) =⇒ min(X) = min(Y ) <
max(Y ) | max(X)
min(Z) =⇒ XRZ
 
min(X) = min(Y )
min(Y ) = min(Z)
Si se verifica ∧ =⇒ min(X) = min(Y ) =
max(Y ) | max(X)
max(Z) | max(Y )

min(X) = min(Z)
min(Z) ∧ max(Z) | max(Y ) | max(X) =⇒ =⇒ XRZ
max(Z) | max(X)

b) Diagrama de Hasse

{4,6})

{3,4} {3,6}

{2,3}

{2,4} {2,6}

{1,2} {1,3}

{1,4} {1,6}

c) {4,6} es el único maximal y por tanto es máximo.

{4,6} es maximal ya que no existe X ∈ F tal que {4, 6}RX.
∀Y ∈ F Y R{4, 6} ya que min(Y ) < 4 =⇒ {4, 6} es máximo.

{1,4} y {1,6} son minimales y como hay varios minimales no existe mínimo.
{1,4} y {1,6} son minimales porque no existe X ∈ F tal que XR{1, 4} ó XR{1, 6}.
No existe ningún conjunto X tal que min(X) < 1 y {1, 6}R{1, 2} pues min({1, 6}) =
min({1, 2} y 2 | 6. Análogamente {1, 6}R{1, 3} y {1, 4}R{1, 2}.
{1, 4} 6 R{1, 6} y {1, 6} 6 R{1, 4}