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

Facultad de Informática - UCM

Examen nal -Enero 2024

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. Dejad 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 responderlas.
La mínima puntuación que puede obtenerse en estas preguntas es 0.

1. Sean a y b ∈ N tales que a|b2 , entonces

siempre se da a|b
⋆ si a es primo entonces a | ((b + 1)2 + (a − 1))
a|b sólo cuando b es primo
Ninguna de las anteriores

Solución (b).
Aplicamos 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.
Si a|b2 y a es primo =⇒ a|b o a|b. En consecuencia, podemos deducir que a|b =⇒ b = a · t1 .
Si a|b2 b2 = a · t2 .
(b + 1)2 + (a − 1) = b2 + 2b + 1 + a − 1 = b2 + 2b + a entonces b2 + 2b + a = at2 + 2at1 + a =
a(t2 + 2t1 + 1) =⇒ a | ((b + 1)2 + (a − 1))

(a) es falso.
Contraejemplo. Sea a = 9 y b = 6
Se verica a = 9|b2 = 36 pero a = 9 ∤ 6 = b.

(c) es falso.
Contraejemplo. Sea a = 9 y b = 3 es decir, b es primo.
Se verica a = 9|b2 = 32 = 9 pero a = 9 ∤ 3 = b.
2. Dados tres conjuntos cualesquiera A, B y C , entonces

nunca (A ∪ B) ∩ C = (C ∪ B) ∪ A
siempre (A ∪ B) ∩ C = (C ∪ B) ∩ A
⋆ si C ⊆ A ∪ B entonces (A ⊕ B) ∩ C = (A ∩ B) ∩ C .
nunca (A ⊕ C) ⊆ (A ⊕ B) ∪ (B ⊕ C)
 ( Recuerda que A ⊕ B =def (A \ B) ∪ (B \ A) )
Solución
(a) es falsa.
(A ∪ B) ∩ C = (A ∪ B) ∪ C = (A ∪ B) ∪ C = A ∪ (B ∪ C) = (B ∪ C) ∪ A = (C ∪ B) ∪ A
↑ ↑ ↑ ↑ ↑
L.De Morgan D=D L. Asociativa L. Conmutativa L. Conmutativa

(b) es falsa.
Contraejemplo. A = {a, b} B = {b, c} C = ∅
(A ∪ B) ∩ C = (A ∪ B) ∪ C = (A ∪ B) ∪ C = (A ∪ B) ∪ ∅ = (A ∪ B) ∪ U = U .
↑ ↑ ↑ ↑ ↑
L.De Morgan D=D C=∅ ∅=U D∪U =U

(c) es cierta.
si C ⊆ A ∪ B entonces (A ⊕ B) ∩ C = (A ∩ B) ∩ C .

En la demostración vamos a utilizar los siguientes resultados:

si C ⊆ A ∪ B entonces C ∩ A ∪ B = ∅
En efecto, C ∩ A ∪ B ⊆ (A ∪ B) ∩ A ∪ B = ∅ =⇒ C ∩ A ∪ B = ∅ ya que ∅ ⊆ C ∩ A ∪ B .

Si tenemos la intersección de 3 conjuntos, dos de ellos arbitrarios y el tercero el complementario

de uno de ellos, su intersección es el ∅. El orden en el que se presenten es irrelevante porque se
verican la ley asociativa y la conmutativa.
(A ∩ B) ∩ A = (B ∩ A) ∩ A = B ∩ (A ∩ A) = B ∩ ∅ = ∅

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

↑ ↑ ↑ ↑
Def de A ⊕ B E\D =E∩D L. De Morgan L. De Morgan
= ((A∪B)∩(B∪A))∩C = ((A∪B)∩(B∪A))∩C = (A∪B)∩((B∪A)∩C) = (A∪B)∩((B∩C)∪(A∩C)) =
↑ ↑ ↑ ↑
D=D L. Asociativa L. Distributiva L. Distributiva
= ((A∪B)∩(B∩C))∪((A∪B)∩(A∩C)) = [(A∩(B∩C))∪(B∩(B∩C))]∪[(A∩(A∩C))∪(B∩(A∩C))] =
↑ ↑
L. Distributiva(a ambos corchetes) Resultado 2
= [((A ∪ B ∩ C) ∪ ∅] ∪ [∅ ∪ (B ∩ (A ∩ C))] = [∅ ∪ ∅] ∪ [∅ ∪ (B ∩ (A ∩ C))] = ∅ ∪ (B ∩ (A ∩ C)) =
↑ ↑ ↑
Resultado 1 ∅∪D =D ∅∪D =D
= (B ∩ (A ∩ C)) = (B ∩ A) ∩ C = (A ∩ B) ∩ C
↑ ↑
L. Asociativa L. Conmutativa

(d) es falsa.
(A ⊕ C) ⊆ (A ⊕ B) ∪ (B ⊕ C) se verica siempre.
(A ⊕ C) = (A ∩ C) ∪ (C ∩ A)
(A ⊕ B) = (A ∩ B) ∪ (B ∩ A)
(B ⊕ C) = (B ∩ C) ∪ (C ∩ B)
Sea x ∈ (A ⊕ C) = (A ∩ C) ∪ (C ∩ A) =⇒ x ∈ (A ∩ C) o x ∈ (C ∩ A)

Sea x ∈ (A ∩ C) . Siempre x ∈ B o x ∈ B . Supongamos x ∈ B =⇒ x ∈ B ∩ C =⇒

x ∈ (B ∩ C) ∪ (C ∩ B) =⇒ x ∈ B ⊕ C =⇒ x ∈ (A ⊕ B) ∪ (B ⊕ C)

Sea x ∈ (C ∩ A) . Siempre x ∈ B o x ∈ B . Supongamos x ∈ B =⇒ x ∈ B ∩ A =⇒

x ∈ (B ∩ A) ∪ (A ∩ B) =⇒ x ∈ A ⊕ B =⇒ x ∈ (A ⊕ B) ∪ (B ⊕ C)

Otra forma de demostrar que (A ⊕ C) ⊆ (A ⊕ B) ∪ (B ⊕ C) es demostrar que

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

Si tenemos la intersección de 4 conjuntos, tres de ellos arbitrarios y el cuarto, el complementario

de uno de ellos, su intersección es el ∅. El orden en el que se presenten es irrelevante porque se
verican la ley asociativa y la conmutativa.
((A∩B)∩C)∩A = ((B ∩A)∩C)∩A = (B ∩A)∩(C ∩A) = (B ∩A)∩(A∩C) = B ∩(A∩(A∩C)) =
B ∩ ((A ∩ A) ∩ C)) = B ∩ (∅ ∩ C) = B ∩ ∅ = ∅

Si tenemos la intersección de 4 conjuntos, dos de ellos arbitrarios y los otros dos el mismo, su
intersección es la intersección de los tres distintos. El orden en el que se presenten es irrelevante
porque se verican la ley asociativa y la conmutativa.
(B ∩ A) ∩ (B ∩ C) = (A ∩ B) ∩ (B ∩ C) = A ∩ (B ∩ (B ∩ C)) = A ∩ ((B ∩ B) ∩ C) = A ∩ (B ∩ C)

(A ⊕ C) ∩ ((A ⊕ B) ∪ (B ⊕ C)) = ((A ∩ C) ∪ (C ∩ A)) ∩ [((A ∩ B) ∪ (B ∩ A)) ∪ ((B ∩ C) ∪ (C ∩ B))] =

↑ ↑
Def de D ⊕ E L. Distributiva
[((A∩C)∪(C ∩A))∩((A∩B)∪(B ∩A))]∪[((A∩C)∪(C ∩A))∩((B ∩C)∪(C ∩B))] = [((A∩C)∪(C ∩A))∩
↑
L. Distributiva en ambos corchetes
∩(A∩B)]∪[((A∩C)∪(C ∩A))∩(B ∩A)]∪[((A∩C)∪(C ∩A))∩(B ∩C)]∪[((A∩C)∪(C ∩A))∩(C ∩B)] =
↑
L. Distributiva en ambos corchetes
= ((A ∩ C) ∩ (A ∩ B)) ∪ ((C ∩ A) ∩ (A ∩ B)) ∪ ((A ∩ C) ∩ (B ∩ A)) ∪ ((C ∩ A) ∩ (B ∩ A)) ∪ ((A ∩ C)∩

∩(B ∩ C)) ∪ ((C ∩ A) ∩ (B ∩ C)) ∪ ((A ∩ C) ∩ (C ∩ B)) ∪ ((C ∩ A) ∩ (C ∩ B)) = (A ∩ C ∩ B) ∪ ∅ ∪ ∅∪

↑
Resultado 1
∪(C ∩ A ∩ B) ∪ (A ∩ C ∩ B) ∪ ∅ ∪ ∅ ∪ (C ∩ A ∩ B) = (A ∩ C ∩ B) ∪ (C ∩ A ∩ B) ∪ (A ∩ C ∩ B) ∪ (C ∩ A ∩ B) =
↑ ↑
D∪∅=∅ L. Conmutativa
= (A ∩ C ∩ B) ∪ (A ∩ C ∩ B) ∪ (C ∩ A ∩ B) ∪ (C ∩ A ∩ B) = ((A ∩ C) ∩ (B ∪ B)) ∪ ((C ∩ A) ∩ (B ∪ B)) =
↑ ↑
L. Distributiva D∪D = U
= ((A ∩ C) ∩ U) ∪ ((C ∩ A) ∩ U) = (A ∩ C) ∪ (C ∩ A) = A ⊕ C
↑ ↑
D∩U =D Def de D ⊕ E
3. Sean A = {a, b, c, d, e} y R una relación de equivalencia denida sobre A tal que bRc, aRe y a R ̸ b. Si
P = {C1 , C2 , · · · , Cn } es la partición de A a la que da lugar R, y además se verica que {b, d} ⊆ C1 ,
entonces necesariamente
|Ci | < 3 ∀i ∈ {1, · · · , n}
|P | = 3
⋆ |P | = 2

no hay una única R vericando las condiciones del enunciado

Solución
(a) es falsa.
Se verica bRc, y {b, d} ⊆ C1 =⇒ bRc, bRd =⇒ [b] = {b, c, d} luego (a) es falsa ya que |C1 | = 3
Si a ̸ R b. =⇒ [a] ̸= [b] y, por tanto, a ̸∈ [b] = {b, c, d} y como aRe =⇒ e ∈ [a] = {a, e} ya que
[a] ∩ [b] = ∅.
En consecuencia, |P | = 2 y, además hay una única R vericando las condiciones del enunciado pues
necesariamente hay dos únicas clases [a] = {a, e}, [b] = {b, c, d} y no hay más posibilidades. Luego (b)
y (d) son falsas.
4. La función f : N → N+ denida por f (x) = 4 · 2x − 1

f es biyectiva
f es sobreyectiva pero no inyectiva
f no es ni inyectiva ni sobreyectiva
⋆ f es inyectiva pero no sobreyectiva

Solución (d)
f es inyectiva ⇐⇒ f (x) = f (y) =⇒ x = y .
Si f (x) = f (y) =⇒ 4 · 2x − 1 = 2x+2 − 1 = 4 · 2y − 1 = 2y+2 − 1 =⇒ 2x+2 = 2y+2 y como la descompo-
sición en primos es única x + 2 = y + 2 =⇒ x = y

f no es suprayectiva.
f suprayectiva ⇐⇒ ∀y ∈ N+ ∃ x ∈ N+ tal que f (x) = y .
Contraejemplo. y = 3 − 1
Si existe x ∈ N+ tal que f (x) = 4 · 2x − 1 = 2x+2 − 1 = 3 − 1 =⇒ 2x+2 = 3 lo que es imposible pues 2
y 3 son primos distintos y la descomposición en primos es única.
5. Dado el siguiente diagrama de Hasse:
g

d e f

b c

⋆ ̸ ∃ ⊔ {b, c} y ⊓{b, c} = a

̸ ∃ ⊔ {b, c} y ̸ ∃ ⊓ {b, c}
⊔{b, c} = g y ̸ ∃ ⊓ {b, c}
⊔{b, c} = g y ⊓{b, c} = a

Solución
Calculamos las cotas superiores e inferiores de {b, c}.
CotasSup({b, c}) = {d, c, g} pues b, c ⊑ d, e, g . f no es cota superior porque aunque c ⊑ f, b ̸⊑ f .
No existe un elemento mínimo de CotasSup({b, c}) = {d, c, g} ya que tiene dos minimales d y e. Ni
d ⊑ e ni e ⊑ d. Por tanto, no existe ⊔{b, c}.

d e

CotasInf ({b, c}) = {a} Este conjunto tiene máximo que es a. Luego ⊓{b, c} = a
6. Dados los conjuntos P(N), {X ⊆ N/X nito} y Q ∩ R+ :

es posible denir una función sobreyectiva de N en el primero de ellos.

no es posible denir una función sobreyectiva de N en el segundo de ellos.
⋆ es posible denir una función sobreyectiva de N en el tercero de ellos.

Ninguna de las anteriores.

Solución (c)
Sabemos que P(N) es un conjunto innito no numerable, {X ⊆ N/X nito} es un conjunto innito
numerable y Q ∩ R+ ⊆ Q es numerable pues es un subconjunto de un conjunto numerable. (De hecho,
Q ∩ R+ = Q+ que es innito numerable.)
Aplicamos el apartado b) del siguiente teorema.
Teorema
a ) A es numerable sii existe una inyección f : A −→ N. (A ≤c N).
b) A ≠ ∅, A es numerable sii existe una función suprayectiva g : N −→ A.

En consecuencia, es posible denir una función sobreyectiva de N en el tercero de ellos pues es nume-
rable.
7. (1,25 puntos) Demuestra por inducción que para todo número natural n ≥ 0 se cumple que
n
X
(i + 1)2 2i = (n2 + 2)2n+1 − 3
i=0

Indica qué tipo de inducción utilizas y justica los pasos de tu demostración, en especial indica cuándo
aplicas la hipótesis de inducción.
Solución.
Lo demostramos por inducción simple porque la denición recursiva de f (n) = ni=0 ai depende sólo
P

de f (n − 1) = i=0 ai ) (un único valor previo).

Pn−1

Caso Base:
Luego se cumple.
P0
n = 0 S(0) ≡ i=0 (i + 1)2 2i = (0 + 2)2 20 = 1 = (02 + 2)20+1 − 3 = 4 − 3

(HI) S(k) ≡ ki=0 (i + 1)2 2i = (k2 + 2)2k+1 − 3 (Usamos inducción simple).

P

Paso Inductivo S(k) =⇒ S(k + 1) ∀k ≥ 0

Pk+1
S(k + 1) ≡ i=0 (i + 1)2 2i = ((k + 1)2 + 2)2(k+1)+1 − 3

Pk+1 ?
2 i 2 k+2
S(k + 1) ≡ i=0 (i + 1) 2 = ((k + 1) + 2)2 −3

Pk+1 Pk
i=0 (i + 1)2 2i = i=0 (i + 1)2 2i + ((k + 1) + 1)2 2k+1 = (k 2 + 2)2k+1 − 3 + (k + 2)2 2k+1 =
↑
H.I. ( ki=0 (i + 1)2 2i = (k2 + 2)2k+1 − 3
P

= 2k+1 (k 2 + 2 + (k + 2)2 ) − 3 = 2k+1 (k 2 + 2 + k 2 + 4k + 4) − 3 = 2k+1 (2k 2 + 4k + 6) − 3 =

2k+1 2(k 2 + 2k + 3) − 3 = 2k+2 (k 2 + 2k + 1 + 2) − 3 = 2k+2 ((k + 1)2 + 2) − 3
8. (0,75 puntos) Sean a, b ∈ Z tales que m.c.d.(a, 6) = 2 y m.c.d.(b, 6) = 3. Demuestra que entonces
m.c.d.(a + b, 6) = 1.
Solución
Si m.c.d.(a, 6) = 2 =⇒ a = 2t1 y 3 ∤ t1 ya que en ese caso t1 = 3m =⇒ a = 2 · 3 · m =⇒ 6|a por lo que
mcd(a, 6) = 6
Análogamente si m.c.d.(b, 6) = 3 =⇒ b = 3t2 y 2 ∤ t2 ya que en ese caso mcd(b, 6) = 6
Supongamos m.c.d.(a + b, 6) = d =⇒ a + b = dw y 6 = dm =⇒ 2 · 3 = dm =⇒ 2|m o 2|d por ser 2
primo.
Análogamente 3|m o 3|d por ser 3 primo. Si 2 ∤ d y 3 ∤ d =⇒ 6 ∤ d =⇒ d = 1 = mcd(a + b, 6)

Vamos a demostrar que 2 ∤ d.

Supongamos que d = 2r1 =⇒ a + b = dw = 2r1 w =⇒ a + b = 2t1 + b = 2r1 w =⇒ b = 2r1 w − 2t1 =
2(r1 w − t1 ) =⇒ 2|b. Contradicción porque 2|3t2 =⇒ 2|t2 ya que 2 es primo y 2 ∤ 3.
(Teorema: Si p es primo y p | x1 . . . xn con x1 . . . xn ∈ Z entonces p | xi para algún i, 1 ≤ i ≤ n.)

Vamos a demostrar que 3 ∤ d.

Supongamos que d = 3r2 =⇒ a + b = dw = 3r2 w =⇒ a + b = a + 3t2 = 3r2 w =⇒ a = 3r2 w − 3t2 =
3(r2 w − t2 ) =⇒ 3|a. Contradicción porque 3|2t1 = a =⇒ 3|t1 ya que 3 es primo y 3 ∤ 2.
 Otra demostración.

Si m.c.d.(a, 6) = 2, a es par y no es divisible por 3, luego a mod 3 = 1 o a mod 3 = 2

Si m.c.d.(b, 6) = 3 =⇒ b es divisible por 3 y no es divisible por 2, por lo que es impar luego b mod 3 = 0
y a + b es impar ya que a es par y b es impar.
Supongamos a mod 3 = 1 y b mod 3 = 0 =⇒ a = 3c0 + 1 y b = 3c1 =⇒ a + b = 3c0 + 1 + 3c1 =⇒
(a + b) mod 3 = 1 =⇒ 3 ∤ (a + b).
Análogamente si a mod 3 = 2 y b mod 3 = 0 =⇒ a = 3c′0 + 2 y b = 3c′1 =⇒ a + b = 3c′0 + 2 + 3c′1 =⇒
(a + b) mod 3 = 2 =⇒ 3 ∤ (a + b).
Si a + b es impar y 3 ∤ (a + b) =⇒ 2 ∤ (a + b) =⇒ m.c.d.(a + b, 6) = 1
9. (1,15 puntos) Sea R ⊆ (Z × Z) × (Z × Z) la siguiente relación de equivalencia:
∀(a, b), (c, d) ∈ Z × Z (a, b)R(c, d) ⇔ |a − b| = |c − d|

a ) (0,3 puntos) Calcula razonadamente las clases de equivalencia de los pares (0, 0) y (−1, 0).
b ) (0,6 puntos) Calcula razonadamente la clase de equivalencia de un par cualquiera (x, y). ¾Cuál es
su cardinal? Justica tu respuesta
c ) (0,25 puntos) ¾Cuál es el cardinal del conjunto cociente (Z × Z)/R? Justica tu respuesta.

Solución
a ) [(0, 0)] = 
{(a, b) ∈ (Z×Z) | |a−b| = |0−0| = 0} = {(a, b) | a = b} = {(0, 0), (1, 1), (−1, −1), (−2, −2), . . .}.
a − b si a − b ≥ 0
|a − b| = =⇒ a − b = 0 o b − a = 0 =⇒ a = b
b − a si a − b < 0
[(−1, 0)] = {(a, b) ∈ (Z × Z) | |a − b| = | − 1 − 0| = 1} = {(a, b) | a = b + 1 o a = b − 1} =
{(b + 1, b), (b − 1, b) | b ∈ Z} = {(−1, 0), (0, 1), (1, 0), (−2, −1), (−1, −2), . . .}.
a − b si a − b ≥ 0

|a − b| = =⇒ a − b = 1 o b − a = 1 =⇒ a = b + 1 o a = b − 1
b − a si a − b < 0

b ) [(x, y)] = {(a, b) ∈ (Z × Z) | |a − b| = |x − y|} = {(a, b) | a = b + m o a = b − m} =

{(b+m, b), (b−m, b) | b ∈ Z} = {(m, 0), (−m, 0), (1+m, 1), (1−m, 1), (m−2, −2), (−2−m, −2) . . .}.
a − b si a − b ≥ 0

|a−b| = =⇒ a−b = m = |x−y| o b−a = m =⇒ a = b+m o a = b−m
b − a si a − b < 0
Dada una clase de equivalencia cualquiera [(x, y)] sea |x − y| = m ∈ N. Para cada b ∈ Z,
(b + m, b) y (b − m, b) ∈ [(x, y)] luego, cada clase de equivalencia es innita. Más formalmente,
podemos denir una función inyectiva
f : Z −→ [(x, y)]
f (b) = (b + m, b)
f es inyectiva: f (b) = f (b′ ) =⇒ (b + m, b) = (b′ + m, b′ ) =⇒ b = b′
Además N ,→ Z −→ [(x, y)] =⇒ N ≤c [(x, y)] =⇒ [(x, y)] es innito.
También [(x, y)] ⊆ (Z × Z) =⇒ [(x, y)] es numerable ya que (Z × Z) es numerable.
c ) Las clases de equivalencia [(x, y)] vienen determinadas por |x − y| ∈ N. Si |x − y| =
̸ |x′ − y ′ | =⇒
[(x, y)] ̸= [(x , y )].
′ ′

(Z × Z)/R = {[(0, 0)], [(1, 0)], [(2, 0)], [(3, 0)], . . .}

Podemos denir una función inyectiva
g : N −→ (Z × Z)/R
g(n) = [(n, 0)]
g es inyectiva: g(n) = g(n′ ) =⇒ [(n, 0)] = [(n′ , 0)] =⇒ (n, 0)R(n′ , 0) ⇐⇒ |n−0| = n = |n′ −0| = n′
En consecuencia N ≤c (Z × Z)/R y (Z × Z)/R es innito. Además (Z × Z)/R ⊆ (Z × Z) por lo
que se trata de un conjunto innito numerable.
10. (1,5 puntos) Sean las funciones f, g : {X ∈ ℘(N+ ) / |X| = 2} → N+
y h : N+ → {X ∈ ℘(N+ ) / |X| = 2} denidas por

f ({a, b}) = a + b (a, b ∈ N+ )

g({a, b}) = max{a, b} − min{a, b} (a, b ∈ N+ )
y
h(a) = {1, a + 1} (a ∈ N+ )

a ) (1,2 puntos) Para cada una de ellas estudia si es inyectiva, suprayectiva o biyectiva. , En caso
armativo demuéstralo y si no da un contraejemplo.
b ) (0,3 puntos) ¾Es biyectiva h ◦ g ? Justica tu respuesta.

Solución
a ) f inyectiva ⇐⇒ f ({x, y}) = f ({x′ , y ′ }) =⇒ {x, y} = {x′ , y ′ }

f es suprayectiva ⇐⇒ ∀z ∈ N+ ∃{x, y} ∈ ℘(N+ ) tal que f ({x, y}) = z

f : {X ∈ ℘(N+ ) / |X| = 2} → N+
f ({a, b}) = a + b

f no es inyectiva. Contraejemplo: f ({3, 2}) = 3 + 2 = 5 = 1 + 4 = f ({1, 4} y {3, 2} =

̸ {1, 4}.

f no es suprayectiva. Contraejemplo: no existe {a, b} ∈ ℘(N+ ) tal que f ({a, b}) = a + b = 1

ya que a, b ∈ N+ luego a, b ≥ 1 =⇒ a + b ≥ 2.
g : {X ∈ ℘(N+ ) / |X| = 2} → N+
g({a, b}) = max{a, b} − min{a, b}

g no es inyectiva. Contraejemplo: g({3, 2}) = max{3, 2} − min{3, 2} = 3 − 2 = 1 = 4 − 3 =

max{4, 3} − min{4, 3} = g({4, 3} y {3, 2} = ̸ {4, 3}.

g es suprayectiva. Sea z ∈ N+ , existe {a, b} ∈ ℘(N+ ) tal que g({a, b}) = z .

g({a, b}) = max{a, b} − min{a, b} = z
Si tomamos a ≥ b =⇒ g({a, b}) = max{a, b} − min{a, b} = a − b = z =⇒ a = b + z
g({a, b}) = g({b + z, b}) = max{b + z, b} − min{b + z, b} = b + z − b = z. Se verica b + z > b
ya que z > 0 b ∈ N+ puede ser cualquiera.
h : N+ → {X ∈ ℘(N+ ) / |X| = 2}
h(a) = {1, a + 1}

h es inyectiva.
Si h(a) = {1, a + 1} = h(b) = {1, b + 1} como a + 1 > 1 pues a ∈ N+ =⇒ a ≥ 1. Por tanto,
a + 1 = b + 1 =⇒ a = b

h no es suprayectiva. Contraejemplo: no existe a ∈ N+ tal que h(a) = {1, a + 1} = {2, 3} ya

que 1 ̸∈ {2, 3}.
b ) h ◦ g : N+ −→ N+ es biyectiva.
h ◦ g(a) = g(h(a)) = g({1, a + 1}) = max{1, a + 1} − min{1, a + 1} = a + 1 − 1 = a ya que
a + 1 > 1 pues a ∈ N+ .
dom(h ◦ g) = dom(idN+ ) = N+ y (h ◦ g)(a) = idN+ (a) = a =⇒ h ◦ g = idN+ y al tratarse de la
identidad en N+ es una función biyectiva.
11. (1,35 puntos) Sobre N × N denimos la siguiente relación R ⊆ (N × N) × (N × N) :

∀(a, b), (c, d) ∈ N × N (a, b)R(c, d) ⇐⇒ ∃k ∈ N+ tal que c = ka y d = kb

a ) (0,75 puntos) Demuestra que R es una relación de orden parcial

b ) (0,6 puntos) Considera S = {(1, 1), (2, 1), (3, 4), (6, 8), (9, 12), (18, 24), (27, 36), (36, 18)}.
Dibuja el diagrama de Hasse de (S, R) y halla, si existen, los elementos extremales y extremos de
(S, R). Razona tu respuesta.
Solución
a ) R es una relación de orden parcial
R relación de orden ⇐⇒ R es reexiva, antisimétrica y transitiva.
Reexiva: ∀(a, b) ∈ N × N (a, b)R(a, b).
(a, b)R(a, b) ⇐⇒ ∃k ∈ N+ tal que a = ka y b = kb lo que es cierto si k = 1.
Antisimétrica: ∀(a, b), (c, d) ∈ N × N (a, b)R(c, d) ∧ (c, d)R(a, b) =⇒ (a, b) = (c, d).
(a, b)R(c, d) ⇐⇒ ∃k ∈ N+ tal que c = ka y d = kb
(c, d)R(a, b) ⇐⇒ ∃k ′ ∈ N+ tal que a = k ′ c y b = k ′ d
Se verica,
c = ka = kk ′ c luego c(1 − kk ′ ) = 0 =⇒ c = 0 o 1 − kk ′ = 0
Si 1 − kk′ = 0 =⇒ k · k′ = 1 =⇒ k = k′ = 1 ya que k, k′ están en N+ =⇒ c = a.
Si c = 0 =⇒ c = ka = 0 =⇒ a = 0 = c pues k ∈ N+ .
También d = kb = kk′ d luego d(1 − kk′ ) = 0 =⇒ d = 0 o 1 − kk′ = 0
Si k · k′ = 1 =⇒ k = k′ = 1 ya que k, k′ están en N+ =⇒ d = b.
Si d = 0 =⇒ d = kb = 0 =⇒ b = 0 = d pues k ∈ N+ .
En consecuencia, (a, b) = (c, d).
Transitiva: ∀(a, b), (c, d), (e, f ) ∈ N+ × N+ (a, b)R(c, d) ∧ (c, d)R(e, f ) =⇒ (a, b)R(e, f ).
(a, b)R(c, d) ⇐⇒ ∃k ∈ N+ tal que c = ka y d = kb
(c, d)R(e, f ) ⇐⇒ ∃k ′ ∈ N+ tal que e = k ′ c y f = k ′ d
(a, b)R(e, f ) ⇐⇒ ∃t ∈ N+ tal que e = ta y f = tb
Se verica, e = k′ c = k′ ka
También f = k′ d = k′ kb luego podemos tomar k′ k = t y entonces e = ta y f = tb
En consecuencia, (a, b)R(e, f ).
b ) Considera S = {(1, 1), (2, 1), (3, 4), (6, 8), (9, 12), (18, 24), (27, 36), (36, 18)}.
Diagrama de Hasse de (S, R).

(18,24) (27,36)

(36,18) (6,8) (9,12)

(1,1) (2,1) (3,4)

(1, 1), (2, 1) y (3, 4) son minimales y como hay varios minimales no existe mínimo ya que ni
(1, 1)R(2, 1) ya que (2, 1) es minimal ni (2, 1)R(1, 1) ya que (1, 1) es minimal. Análogamente para
(3, 4).
(1, 1) es minimal ya que no existe (a, b) ∈ S, (a, b) ̸= (1, 1) tal que (a, b)R(1, 1) ⇐⇒
∃k ∈ N+ tal que 1 = ka y 1 = kb (k, a, b ∈ N+ =⇒ k = a = b = 1 ).
(2, 1) es minimal ya que no existe (a, b) ∈ S, (a, b) ̸= (2, 1) tal que (a, b)R(2, 1) ⇐⇒
∃k ∈ N+ tal que 2 = ka y 1 = kb (k, a, b ∈ N+ =⇒ k = b = 1 =⇒ a = 2 ).
(3, 4) es minimal ya que no existe (a, b) ∈ S, (a, b) ̸= (3, 4) tal que (a, b)R(3, 4) ⇐⇒
∃k ∈ N+ tal que 3 = ka y 4 = kb (k, a, b ∈ N+ =⇒ k|3 y k|4 =⇒ k|mcd(3, 4) = 1 =⇒ k = 1 =⇒
a = 3, b = 4 ).

(1,1),(18,24),(27,36),(36,18) son maximales y como hay varios maximales no existe máximo. La

demostración es análoga a: Si existen varios minimales entonces no hay mínimo.
(1, 1) es maximal ya que no existe (a, b) ∈ S, (a, b) ̸= (1, 1) tal que (1, 1)R(a, b) ⇐⇒
∃k ∈ N+ tal que a = k · 1 y b = k · 1 (k, a, b ∈ N+ =⇒ k = a = b y no existe ningún par
(m, m) ̸= (1, 1) ∈ S ).
(18, 24) es maximal ya que no existe (a, b) ∈ S, (a, b) ̸= (18, 24) tal que (18, 24)R(a, b) ⇐⇒
∃k ∈ N+ tal que a = k · 18 y b = k · 24 (k, a, b ∈ N+ y no existe ningún par (m, n) ̸= (18, 24) ∈ S
tal que 18|a y 24|b).
Análogamente para (27, 36) y (36, 18).