Soluciones Examen de Matemática Discreta y Lógica Matemática

(Febrero 2017)

1. Dadas las dos siguientes afirmaciones:

(A \ B) \ C = A \ (B \ C) (A \ B) \ C = A \ (B ∪ C)

Ambas son ciertas.

Ambas son falsas.
Solamente es cierta la primera.
X Solamente es cierta la segunda.
Solución
(C \ D) = C ∩ D
(A \ B) \ C = (A ∩ B) \ C = (A ∩ B) ∩ C = A ∩ (B ∩ C) = A ∩ (B ∪ C) = A \ (B ∪ C)
↑ ↑ ↑ ↑ ↑
def \ def \ ley asociativa ley De Morgan def \

(A \ B) \ C = A \ (B \ C)
Contraejemplo:
A = {1, 2, 3} B = {2, 4, 5} C = {2, 4, 6}
A \ B = {1, 2, 3} \ {2, 4, 5} = {1, 3} (A \ B) \ C = {1, 3} \ {2, 4, 6} = {1, 3}
B \ C = {2, 4, 5} \ {2, 4, 6} = {5} A \ (B \ C) = {1, 2, 3} \ {5} = {1, 2, 3}
2. Sea la familia de conjuntos:
Ak = {m ∈ Z | |m| ≤ k} k ∈ N
Indica la respuesta correcta:
S T
{Ak | k ∈ N} = N y {Ak | k ∈ N} = ∅.
S T
X {Ak | k ∈ N} = Z y {Ak | k ∈ N} = {0}.
S T
{Ak | k ∈ N} = Z y {Ak | k ∈ N} = ∅.
S T
{Ak | k ∈ N} = N y {Ak | k ∈ N} = {0}..
Solución
Ak = {m ∈ Z | |m| ≤ k} k ∈ N

A0 = {m ∈ Z | |m| ≤ 0} = {m ∈ Z | 0 ≤ m ≤ 0} = {0}
A1 = {m ∈ Z | |m| ≤ 1} = {m ∈ Z | − 1 ≤ m ≤ 1} = {−1, 0, 1} = Z ∩ [−1, 1]
A2 = {m ∈ Z | |m| ≤ 2} = {m ∈ Z | − 2 ≤ m ≤ 2} = {−2, −1, 0, 1, 2} = Z ∩ [−2, 2]
..
.
Ak = {m ∈ Z | |m| ≤ k} = {m ∈ Z | − k ≤ m ≤ k} = Z ∩ [−k, k]

A0 ⊆ A1 ⊆ A2 ⊆ · · ·

S S S
{Ak | k ∈ N} = A0 ∪ {Ak | k ≥ 1} = {0} ∪ {Ak | k ≥ 1} = {0} ∪ (Z ∩ [−1, 1]) ∪ (Z ∩ [−2, 2]) ∪ · · · =

= {0} ∪ {−1, 0, 1} ∪ {−2, −1, 0, 1, 2} ∪ · · · = Z

T T T
{Ak | k ∈ N} = A0 ∩ {Ak | k ≥ 1} = {0} ∩ {Ak | k ≥ 1} = {0} ∩ (Z ∩ [−1, 1]) ∩ (Z ∩ [−2, 2]) ∩ · · · =

= {0} ∩ {−1, 0, 1} ∩ {−2, −1, 0, 1, 2} ∩ · · · = {0} = A0

3. Dados los conjuntos
{2n | n ∈ N} × {0, 1} [0, 2] ∩ Q P(N)

Los tres son numerables.

Solamente el primero es numerable.
Solamente el segundo es numerable.
X Solamente el primero y el segundo son numerables.
Solución
P(N) sabemos por teorı́a que no es numerable.
{2n | n ∈ N} × {0, 1} es numerable porque es el producto cartesiano de dos conjuntos numerables.
Ambos son numerables al ser subconjuntos de N.
[0, 2] ∩ Q ⊆ Q es numerable ya que es un subconjunto de Q que es numerable.
4. Dados los conjuntos
{a, b, c} × {a, b, c} ({a, b, c} −→ {0, 1}) P({a, b, c})

Solamente los dos primeros son finitos.

Los tres son finitos, y todos tienen el mismo tamaño.
X Los tres son finitos, y solamente dos tienen el mismo tamaño.
Los tres son finitos, y tienen tamaño distinto dos a dos.

Solución
|{a, b, c} × {a, b, c}| = 3 · 3 = 9
|({a, b, c} −→ {0, 1})| = |{0, 1}||{a,b,c}| = 23
|P({a, b, c})| = 2|{a,b,c}| = 23
5. Sea S el conjunto de subconjuntos no vacı́os de cardinal impar de {a, b, c, d, e, f }. Definimos el orden
parcial R en S como sigue:

XRY ⇐⇒ (X = {a} y a 6∈ Y ) ó (X ⊆ Y )

(S, R) tiene máximo y mı́nimo.

(S, R) tiene máximo pero no tiene mı́nimo.
X (S, R) no tiene máximo pero tiene mı́nimo.
(S, R) no tiene máximo ni mı́nimo.
Solución
6. R es una relación de orden ⇐⇒ R es reflexiva, antisimétrica y transitiva.

Reflexiva: ∀X XRX ⇐⇒ (X = {a} y a 6∈ X) ó (X ⊆ X)

∀X XRX ya que X ⊆ X

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

XRY ⇐⇒ (X = {a} y a 6∈ Y ) ó (X ⊆ Y )
Y RX ⇐⇒ (X = {a} y a 6∈ Y ) ó (X ⊆ Y ).
Solo son compatibles (X ⊆ Y ) con (Y ⊆ X) =⇒ X = Y
(Si (X = {a} y a 6∈ Y ) no puede verificarse simultáneamente Y ⊆ X = {a} ya que a 6∈ Y .
Si (X = {a} y a 6∈ Y ) no puede verificarse simultáneamente (Y = {a} y a 6∈ X).)
Luego ∀X, Y XRY ∧ Y RX =⇒ X = Y . Es antisimétrica.

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

XRY ⇐⇒ (X = {a} y a 6∈ Y ) ó (X ⊆ Y )
Y RZ ⇐⇒ (Y = {a} y a 6∈ Z) ó (Y ⊆ Z)
 XRZ ⇐⇒ (X = {a} y a 6∈ Z) ó (X ⊆ Z).
Si se verifica XRY porque (X = {a} y a 6∈ Y ) entonces si Y RZ sólo puede ser porque Y ⊆ Z. Hay
dos posibilidades:
a 6∈ Z pero entonces (X = {a} y a 6∈ Z) =⇒ XRZ
a ∈ Z =⇒ {a} = X ⊆ Z =⇒ XRZ
Sea XRY porque X ⊆ Y e Y RZ. Si (Y = {a} y a ∈ 6 Z). Como X ⊆ Y = {a} =⇒ X = ∅ ⊆ Z o
X = {a}. Como a 6∈ Z, tenemos (X = {a} y a 6∈ Z) . Luego XRZ en ambos casos.
Sea XRY porque X ⊆ Y e Y RZ porque Y ⊆ Z =⇒ X ⊆ Z =⇒ XRZ.
Se verifica ∀X, Y, Z XRY ∧ Y RZ =⇒ XRZ luego es transitiva.

(S, R) tiene mı́nimo que es {a} ya que ∀Y ∈ S {a}RY . En efecto:

Sea Y ∈ S. Si a 6∈ Y =⇒ ({a} = {a} y a 6∈ Y ) =⇒ {a}RY .
Si a ∈ Y =⇒ ({a} ⊆ Y ) =⇒ {a}RY .

(S, R) no tiene máximo porque {b, c, d, e, f }, {a, c, d, e, f }, {a, b, d, e, f }, {a, b, c, e, f }, {a, b, c, d, f }, {a, b, c, d, e}
son todos maximales de S, ya que son de cardinal impar y no tienen ningún conjunto de S por arriba,
ya que el único conjunto que los contiene es {a, b, c, d, e, f } pero no es un elemento de S por ser de
cardinal 6 que es par. El máximo, de existir, tiene que ser maximal pero único.
7. Sobre el conjunto {0, 1} se define la relación binaria {(0, 0), (0, 1), (1, 0)} entonces:

es una relación de equivalencia.

es un orden parcial.
es un orden estricto.
X Ninguna de las anteriores afirmaciones es cierta.
Solución
R es una relación de equivalencia ⇐⇒ R es reflexiva, simétrica y transitiva.
R es una relación de orden ⇐⇒ R es reflexiva, antisimétrica y transitiva.
R es una relación de orden estricto ⇐⇒ R es antireflexiva y transitiva.

R es reflexiva ⇐⇒ ∀x xRx
R es antirreflexiva ⇐⇒ ∀x x 6 Rx
No es reflexiva porque 1 6 R1 ya que (1, 1) 6∈ R =⇒ R no es de equivalencia ni de orden.
No es antirreflexiva porque 0R0 ya que (0, 0) ∈ R =⇒ R no es un orden estricto.
(Es simétrica (1, 0), (0, 1) ∈ R pero no es ni antisimétrica ( (1, 0), (0, 1) ∈ R y 1 6= 0 ni transitiva
(1, 0), (0, 1) ∈ R pero (1, 1) 6∈ R.)

8. Dada la siguiente sucesión recurrente:


 1 si n = 0
an = a a si n > 0 n par
 n/2 n/2
2an−1 si n > 0 n impar

Demuestra por inducción que para todo n ≥ 0 se cumple an = 2n . Indica el tipo de inducción que
utilizas.
Solución.
Base: k = 0 S(0) ≡ a0 = 1 = 20 Luego se cumple.

Paso Inductivo S(0), . . . , S(k) =⇒ S(k + 1)

(Aplicamos inducción completa porque la definición recursiva de an depende de an/2 ) (no exclusiva-
mente del elemento inmediatamente anterior an−1 ).
 a0 = 2 0 

..

j
(HI) S(0), . . . , S(k) ⇐⇒ .  ⇐⇒ aj = 2 0≤j≤k
ak = 2 k


?
S(k + 1) ≡ ak+1 = 2k+1
 
a(k+1)/2 a(k+1)/2 si k + 1 par a(k+1)/2 a(k+1)/2 si k + 1 = 2j para algún j ∈ N
ak+1 = ⇐⇒ ak+1 =
2a(k+1)−1 si k + 1 impar 2a(k+1)−1 si k + 1 = 2j + 1 para algún j ∈ N
  j j
aj aj si k + 1 = 2j j ∈ N 2 2 si k + 1 = 2j j ∈ N
⇐⇒ ak+1 = ⇐⇒ ak+1 = ⇐⇒
2ak si k + 1 = 2j + 1 j ∈ N 22k si k + 1 = 2j + 1 j ∈ N
↑ ↑
(k+1)/2=j H.I. (aj = 2j (j ≤ k) ak = 2k )

22j 2k+1
 
si k + 1 = 2j j ∈ N si k + 1 = 2j j ∈ N
⇐⇒ ak+1 = ⇐⇒ ak+1 = ⇐⇒
2k+1 si k + 1 = 2j + 1 j ∈ N 2k+1 si k + 1 = 2j + 1 j ∈ N

ak+1 = 2k+1
9. Sea p primo, si p/a y p/a2 + b2 demuestra que p/b.

Solución:
Si p/a =⇒ a = p · t =⇒ p/a2 ya que a2 = a · a = p · t · p · t = p(tpt) = p · t′
Como p/a2 + b2 =⇒ a2 + b2 = p · d =⇒ b2 = p · d − a2 =⇒ p · d − p · t′ = p(d − t′ ) es decir p/b2 y como
p es primo se verifica p/b por el siguiente teorema.
Teorema
Si p es primo y p | x1 . . . xn con x1 . . . xn ∈ Z entonces p | xi para algún i, 1 ≤ i ≤ n
10. Sobre el conjunto F = {X ∈ P(N) | X es finito} se define la relación binaria

XRY ⇐⇒ |Y | = |X| + 5k, para algún k ∈ Z (|A| es el cardinal de A)

a) Demuestra que R es de equivalencia sobre F .

b) Da dos elementos distintos de F que estén relacionados y dos que no lo estén.
c) Describe la clase de equivalencia de {1} y del ∅.
d ) ¿Cuántas clases de equivalencia distintas hay?
Solución:

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

Reflexiva: ∀X XRX ⇐⇒ |X| = |X| + 5k, para algún k ∈ Z

XRX ⇐⇒ si existe k ∈ Z|X| = |X| + 5k. Basta tomar k = 0

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

XRY ⇐⇒ si |Y | = |X| + 5k1 k1 ∈ Z
Y RX ⇐⇒ si existe k2 ∈ Z |X| = |Y | + 5k2 .
|Y | = |X| + 5k1 =⇒ |X| = |Y | − 5k1 = |Y | + 5(−k1 ) −k1 ∈ Z Luego XRY =⇒ Y RX. Es
simétrica.

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

XRY ⇐⇒ si |Y | = |X| + 5k1 k1 ∈ Z
Y RZ ⇐⇒ si |Z| = |Y | + 5k2 k2 ∈ Z
XRZ ⇐⇒ si existe k3 ∈ Z |Z| = |X| + 5k3 .
Como XRY y Y RZ |Y | = |X| + 5k1 , |Z| = |Y | + 5k2 =⇒ |Z| = |Y | + 5k2 = |X| + 5k1 + 5k2 =
|X| + 5(k1 + k3 ). Luego existe
k3 = k1 + k2 ∈ Z tal que |Z| = |X| + 5k3 . Luego XRZ.
Se verifica ∀X, Y, Z XRY ∧ Y RZ =⇒ XRZ luego es transitiva.
 b) Sea X = {1, 2, 3} =⇒ |X| = 3. Para que un conjunto Y 6= X esté relacionado con X debe verificar
que |Y | = |X| + 5k1 k1 ∈ Z Si tomamos k1 = 1 =⇒ |Y | = |X| + 5 = 8
Podemos considerar cualquier conjunto Y con |Y | = 8, por ejemplo, Y = {5, 6, 7, 8, 9, 10, 11, 12}
Por tanto, para encontrar un conjunto Y tal que Y 6 RX basta con considerar cualquier conjunto
Y con |Y | =
6 |X| + 5k1 es decir |Y | =
6 8, 13..., por ejemplo, Y = {5, 6, 7, 8, 9}
c) [{1}] = {Y ∈ F | Y R{1}} = {Y ∈ F | |Y | = |{1}| + 5k1 k1 ∈ Z} = {Y ∈ F | |Y | = 1 + 5k1 k1 ∈ Z} =
= {Y ∈ F | |Y | ∈ {1, 6, 11, ...}}
[∅] = {Y ∈ F | Y R∅} = {Y ∈ F | |Y | = |∅| + 5k1 k1 ∈ Z} = {Y ∈ F | |Y | = 0 + 5k1 k1 ∈ Z} =
= {Y ∈ F | |Y | ∈ {0, 5, 10, ...}}
d ) El conjunto cociente es: F /R = {[X] | X ∈ F }.
Lo que determina la clase de equivalencia de un conjunto X es su |X|.
Si dividimos |X| por 5 se verifica |X| = 5m + r donde r < 5 y por tanto 0 ≤ r ≤ 4
Cualquier conjunto Y con |Y | = 5m′ + r se verifica Y está relacionado con cualquier conjunto X
tal que |X| = r.
Luego F /R = {[X] | |X| ≤ 4} ya que los restos posibles al dividir un entero entre 5 son: 0,1,2,3,4
=⇒ |F/R| = 5

11. Sea g : N → N una función biyectiva. Estudia si la función f : N → N × N definida como f (n) =
(g(n), 2g(n)) es inyectiva, suprayectiva. En caso afirmativo demuéstralo formalmente y en caso negativo
da un contraejemplo.
Solución
f es inyectiva ⇐⇒ f (x1 ) = f (x2 ) =⇒ x1 = x2
f es suprayectiva ⇐⇒ ∀z ∈ Im(f ) = N × N ∃a ∈ Dom(f ) = N tal que f (a) = z (En nuestro caso
z = (x, y) y f (a) = (x, y) = z)

f es inyectiva:

g(n1 ) = g(n2 )
f (n1 ) = f (n2 ) =⇒ f (n1 ) = (g(n1 ), 2g(n1 )) = f (n2 ) = (g(n2 ), 2g(n2 )) =⇒ =⇒
2g(n1 ) = 2g(n2 )
g(n1 ) = g(n2 ) =⇒ n1 = n2 ya que g es inyectiva al ser biyectiva.
f no es suprayectiva:
f (n) = (g(n), 2g(n)) Vemos que la segunda componente del par (g(n), 2g(n)) es siempre par, luego si
tomamos z = (4, 1), por ejemplo, no existe n ∈ N tal que f (n) = (g(n), 2g(n)) = (4, 1). Por tanto, f
no es suprayectiva aunque g lo es.