EXAMEN de Matemática Discreta y Lógica Matemática

(Parcial Febrero 2018)

NOMBRE:

GRUPO:

Lee atentamente las siguientes instrucciones:

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 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.

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. Dadas las dos siguientes afirmaciones:

   
6a2 =⇒ 6a 4a2 =⇒ 4a

Ambas son ciertas.

Ambas son falsas.
X Solamente es cierta la primera.
Solamente es cierta la segunda.

Solución
  
6a2 =⇒ a2 = 6 · t = 2 · 3 · t =⇒ 2a2 =⇒ 2a ya que 2 es primo y se obtiene aplicando el siguiente
teorema: Si p es primo y p | x1 . . . xn con x1 . . . xn ∈ Z entonces p | xi para algún i, 1 ≤ i ≤ n
 
Análogamente 3a2 =⇒ 3a.
  
Luego a = 2 · t1 = 3 · t2 =⇒ 32 · t1 =⇒ 3t1 =⇒ t1 = 3 · t3 =⇒ a = 2 · 3 · t3 = 6 · t3 =⇒ 6a.
↑  
Lema de Euclides (a b · c y mcd(a, b) = 1 =⇒ ac)
 
4a2 =⇒ 4a Es falso.
 
Contraejemplo: a = 10 4102 pero 4  10
2. Dadas las dos siguientes afirmaciones, donde A ⊕ B = (A \ B) ∪ (B \ A):
(A \ (B ∪ C)) ∪ B = (A \ C) ∪ B A ⊕ B = ∅ =⇒ A = B

X Ambas son ciertas.

Ambas son falsas.
Solamente es cierta la primera.
Solamente es cierta la segunda.

Solución
(A \ (B ∪ C)) ∪ B = (A ∩ (B ∪ C)) ∪ B = (A ∩ (B ∩ C)) ∪ B = (A ∩ (C ∩ B)) ∪ B = ((A ∩ C) ∩ B) ∪ B =
↑ ↑ ↑ ↑
(C \ D = C ∩ D)De Morgan(B ∪ C = B ∩ C) L.Conmutativa L.Asociativa

= ((A ∩ C) ∪ B) ∩ (B ∪ B) = ((A ∩ C) ∪ B) ∩ U = (A ∩ C) ∪ B = (A \ C) ∪ B
↑ ↑ ↑ ↑
L.Distributiva B∪B =U C ∩U =C (C \ D = C ∩ D)
 A ⊕ B = ∅ =⇒ A = B
A ⊕ B = (A \ B) ∪ (B \ A) = ∅ =⇒ (A \ B) ⊆ (A \ B) ∪ (B \ A) = ∅ =⇒ (A \ B) = ∅
A ⊕ B = (A \ B) ∪ (B \ A) = ∅ =⇒ (B \ A) ⊆ (A \ B) ∪ (B \ A) = ∅ =⇒ (B \ A) = ∅

A = A ∩ U = A ∩ (B ∪ B) = (A ∩ B) ∪ (A ∩ B) = (A \ B) ∪ (A ∩ B) = ∅ ∪ (A ∩ B) = (A ∩ B)
↑ ↑ ↑ ↑
(U = B ∪ B) L. Distributiva (C \ D = C ∩ D) (A \ B) = ∅

B = B ∩ U = B ∩ (A ∪ A) = (B ∩ A) ∪ (B ∩ A) = (B \ A) ∪ (B ∩ A) = ∅ ∪ (B ∩ A) = (B ∩ A)
Luego A = (A ∩ B) = (B ∩ A) = B
3. Sean las familias de conjuntos:
Ak = {n ∈ N | n ≤ k} Bk = {n ∈ N | n > k}
Indica la respuesta correcta:
 
{Ak | k ∈ N} = N y {Bk | k ∈ N} = N.
 
{Ak | k ∈ N} = ∅ y {Bk | k ∈ N} = ∅.
 
X {Ak | k ∈ N} = N y {Bk | k ∈ N} = ∅.
 
{Ak | k ∈ N} = ∅ y {Bk | k ∈ N} = N.
Solución
Ak = {n ∈ N | n ≤ k} k ∈ N

A0 = {n ∈ N | n ≤ 0} = {0}
A1 = {n ∈ N | n ≤ 1} = {0, 1}
A2 = {n ∈ N | n ≤ 2} = {0, 1, 2}
..
.
Ak = {n ∈ N | n ≤ k} = {0, 1, 2 . . . k}
..
.

A0 ⊆ A1 ⊆ A2 ⊆ · · ·


{Ak | k ∈ N} = A0 ∪ A1 · · · ∪ Ak ∪ · · · = N


Puesto que Ak ⊆ N ∀k ∈ N =⇒ {Ak | k ∈ N} ⊆ N
  
∀m ∈ N, m ∈ Am = {0, 1, 2 . . . m} ⊆ {Ak | k ∈ N} =⇒ m ∈ {Ak | k ∈ N} =⇒ N ⊆ {Ak | k ∈ N}

{Ak | k ∈ N} = N

Bk = {n ∈ N | n > k} k ∈ N

B0 = {n ∈ N | n > 0} = {1, 2, 3, . . .}
B1 = {n ∈ N | n > 1} = {2, 3, . . .}
B2 = {n ∈ N | n > 2} = {3, 4, . . .}
..
.
Bk = {n ∈ N | n > k} = {k + 1, k + 2, . . .}
..
.

B0 ⊇ B1 ⊇ B2 ⊇ · · ·


{Bk | k ∈ N} = ∅

En efecto, sea m ∈ N, si m ∈ {Bk | k ∈ N} =⇒ m ∈ Bk ∀k =⇒ m ∈ Bm = {m + 1, m + 2, . . .}.
Contradicción, luego {Bk | k ∈ N} = ∅.
4. Sea f : {2n/n ∈ N} × R −→ {n ∈ N/n > 5} × Q, señala la respuesta correcta.
X f puede ser suprayectiva pero no biyectiva.
f puede ser inyectiva pero no biyectiva.
f puede ser biyectiva.
Ninguna de las anteriores.
Solución
{n ∈ N/n > 5} × Q es numerable porque es el producto cartesiano de dos conjuntos numerables.
{n ∈ N/n > 5} es numerable f : {n ∈ N/n > 5} −→ N
n −→ n − 6
Es inyectiva. h(n) = h(m) =⇒ n = m
h(n) = n − 6 = h(m) = m − 6 =⇒ n = m
Es suprayectiva. ∀m, m ∈ N existe un n ∈ {n ∈ N/n > 5} tal que h(n) = m
h(n) = n − 6 = m =⇒ n = m + 6 h(n) = h(m + 6) = m + 6 − 6 = m.

{2n/n ∈ N} × R no es numerable.
   
{2n/n ∈ N}×R = n∈N {2n}×R = n∈N {2n}×R que es no numerable porque es la unión numerable
de conjuntos equipotentes con R. En efecto:
h : {2n} × R −→ R
(2n, x) −→ x
Es inyectiva. h((2n, x)) = h((2n, y)) =⇒ x = y
h((2n, x)) = x = h((2n, y)) = y =⇒ x = y
Es suprayectiva. ∀x, x ∈ R existe un y  ∈ {2n} × R tal que h(y  ) = x
h(y  ) = h((2n, y)) = y = x y  = (2n, x).
Tenemos el 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.
Si f es inyectiva, tenemos una inyección
{2n/n ∈ N} × R −→ {n ∈ N/n > 5} × Q ∼c N
{2n/n ∈ N} × R −→ N luego {2n/n ∈ N} × R serı́a numerable. Contradicción.
f : {2n/n ∈ N} × R −→ {n ∈ N/n > 5} × Q puede ser suprayectiva:

(n + 6, x) si x ∈ Q
f ((2n, x)) =
(6, 0) si x ∈ Q

Es suprayectiva. ∀y, y ∈ {n ∈ N/n > 5} × Q existe un y  ∈ {2n|n ∈ N} × R tal que f (y  ) = y

y = (m, m
m2 ) m ∈ {n ∈ N/n > 5} =⇒ m ≥ 6 =⇒ m − 6 ≥ 0
1

m1
m2 ∈Q⊆R
f ((2(m − 6), m m1 m1
m2 )) = (m − 6 + 6, m2 ) = (m, m2 ) = y
1
y  = (2(m − 6), m 1
m2 ).

5. Definimos una relación R en N como sigue: aRb ⇐⇒ a + b es par.

R no es una relación de equivalencia.

R es una relación de equivalencia y |A/R| = 1
X R es una relación de equivalencia y |A/R| = 2
R es una relación de equivalencia y |A/R| es infinito.
 Solución:
R es una relación de equivalencia ⇐⇒ R is reflexiva, simétrica y transitiva.
x R y ⇐⇒ x + y es par ⇐⇒ x + y = 2 · t
R es reflexiva ⇐⇒ ∀x ∈ N, xRx
∀x ∈ N, xRx ⇐⇒ x + x = 2x = 2 · t (con t = x)
R es simétrica ⇐⇒ ∀x, y ∈ N si xRy =⇒ yRx
∀x, y ∈ N si xRy ⇐⇒ x + y = 2 · t1 =⇒ y + x = 2 · t1 =⇒ yRx
R es transitiva ⇐⇒ ∀x, y, z ∈ N si xRy ∧ yRz =⇒ xRz

x + y = 2 · t1
∀x, y, z ∈ N si xRy ∧yRz ⇐⇒ =⇒ x+2y +z = 2·t1 +2·t2 =⇒ x+z = 2(t1 +t2 −y)
y + z = 2 · t2
=⇒ x + z = 2 · t3 =⇒ xRz (con t3 = t1 + t2 − y)

[0]R = {x|xR0} = {x|x + 0 = 2 · t para algún t ∈ N} = {x|x = 2 · t} = {0, 2, 4, . . .}

[1]R = {x|xR1} = {x|x + 1 = 2 · t para algún t ≥ 1} = {x|x = 2 · t − 1} =

= {1, 3, 5, . . .}
No hay más clases ya que todo número natural está en [0]R o en [1]R .
6. Sobre P(N) se define la relación binaria ARB ⇐⇒ A ∩ B = C, siendo C ∈ P(N) un
conjunto fijado a priori. 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
Reflexiva: ∀X XRX ⇐⇒ X ∩ X = C pero X ∩ X = X = C, luego no es reflexiva. (Sólo se cumple
para X = C).
Tampoco es antirreflexiva porque ya hemos visto que se cumple si X = C pero si X = C no es cierto.
Luego no se cumple ∀X X  RX
Luego no es relación de equivalencia ni de orden, ni parcial ni estricto.
Simétrica: ∀X, Y XRY =⇒ Y RX
XRY ⇐⇒ X ∩ Y = C =⇒ Y ∩ X = X ∩ Y = C ⇐⇒ Y RX
Transitiva: ∀X, Y, Z XRY ∧ Y RZ =⇒ XRZ
XRY ⇐⇒ X ∩ Y = C
Y RZ ⇐⇒ Y ∩ Z = C
Es falsa. Contraejemplo: C = {1, 2} X = {1, 2, 5, 7} Y = {1, 2, 3} Z = {1, 2, 5, 9}
X ∩ Y = {1, 2, 5, 7} ∩ {1, 2, 3} = {1, 2}
Y ∩ Z = {1, 2, 3} ∩ {1, 2, 5, 9} = {1, 2} pero
X ∩ Z = {1, 2, 5, 7} ∩ {1, 2, 5, 9} = {1, 2, 5} = {1, 2} = C
7. [1.5 puntos] Demuestra por inducción, indicando qué tipo de inducción usas, que para todo n ≥ 1,
n

i2i = (n − 1)2n+1 + 2
i=1

Solución
Lo demostramos por inducción simple, porque la definición sólo depende del valor anterior:
n+1 n
i=1 i2i = i=1 i2i + (n + 1)2n+1
Caso Base:
1
n = 1 S(1) ≡ i=1 i2i = 1 · 2 = 2 = 0 · 21+1 + 2 = 2 Luego se cumple.

k
(HI) S(k) ≡ i=1 i2i = (k − 1)2k+1 + 2 (Usamos inducción simple).
?
k+1
Paso Inductivo S(k + 1) ≡ i=1 i2i = (k + 1 − 1)2k+1+1 + 2 = k2k+2 + 2
k+1 k
i=1 i2i = i=1 i2i + (k + 1)2k+1 = (k − 1)2k+1 + 2 + (k + 1)2k+1 = 2k+1 (k − 1 + k + 1) + 2 =
↑
k i k+1
H.I. i=1 i2 = (k − 1)2 +2

= 2k+1 (2k) + 2 = k2k+2 + 2

  
8. [1 punto] Sea p un número primo y sean a, b ∈ Z siendo a, b ≥ 2. Si pa2 y pb3 , demuestra que pa + b
Solución
Tenemos el teorema: Si p es primo y p | x1 . . . xn con x1 . . . xn ∈ Z entonces p | xi para algún i,
1≤i≤n
 
pa2 =⇒ pa ( aplicando el teorema ) =⇒ a = p · t1
 
pb3 =⇒ pb ( aplicando el teorema ) =⇒ b = p · t2

a + b = p · t1 + p · t2 = p(t1 + t2 ) =⇒ p(a + b)
9. [3 puntos] Definimos la relación R en P(N) como:

XRY ⇐⇒ X ∩ Y = X X, Y ⊆ N

a) [1 punto] Demuestra que R es una relación de orden sobre P(N).

b) Definimos el conjunto F  = {X ∈ P(N) | |X| es impar} y consideramos el conjunto parcialmente
ordenado (F  ,R)
1) [1 punto] Estudia sus elementos extremales.
2) [1 punto] Sea S = {X ⊆ {1, 2, 3, 4, 5}||X| = 1 o |X| = 3} ⊆ F  . Estudia los elementos
extremales de S. Calcula las cotas superiores e inferiores de S y su supremo e ı́nfimo, si
existen.
Solución

a) R es una relación de orden sobre P(N).

Reflexiva: ∀X XRX ⇐⇒ X ∩ X = X Se cumple por la ley de idempotencia.
Antisimétrica: ∀X, Y XRY ∧ Y RX =⇒ X = Y
XRY ⇐⇒ X ∩ Y = X
Y RX ⇐⇒ Y ∩ X = Y
X = X ∩ Y = Y ∩ X = Y ⇐⇒ X = Y
Transitiva: ∀X, Y, Z XRY ∧ Y RZ =⇒ XRZ
XRY ⇐⇒ X ∩ Y = X
Y RZ ⇐⇒ Y ∩ Z = Y
XRZ ⇐⇒ X ∩ Z = X
X ∩ Z = (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z) = X ∩ Y = X =⇒ XRZ
↑ ↑ ↑ ↑
(X = X ∩ Y ) Asociativa (Y ∩ Z = Y ) (X ∩ Y = X)
 b) F  = {X ∈ P(N) | |X| es impar} (F  ,R) donde XRY ⇐⇒ X ∩ Y = X ⇐⇒ X = X ∩ Y ⊆ Y
1) Los elementos de la forma {n} con n ∈ N son todos minimales porque no existe un conjunto
X ∈ F  tal que X  {n}. Tendrı́a que ser X = ∅ pero |∅| = 0 y por tanto ∅ ∈ F  .

No hay mı́nimo. Y es mı́nimo si ∀X, X ∈ F  se verifica Y ⊆ X.

Ningún conjunto de la forma {n} es mı́nimo ya que si n = m ni {n} ⊆ {m}, ni {m} ⊆ {n}.

Sin embargo no hay elementos maximales.

Supongamos que tenemos un elemento maximal. Tiene que ser un elemento X ∈ F  es decir
un conjunto finito de cardinal impar. Sea X = {a1 , a2 , . . . , a2k+1 }. Evidentemente siempre
existe un conjunto Y ∈ F  tal que X ⊆ Y . Basta tomar Y = {a1 , a2 , . . . , a2k+1 , b, c} donde
b, c ∈ N b = c y b, c ∈ X. Siempre es posible encontrar estos elementos b, c ya que X es finito
y N es infinito.

2) [1 punto] Sea S = {X ⊆ {1, 2, 3, 4, 5}||X| = 1 o |X| = 3} ⊆ F  .

Elementos extremales de S. S = {{1}, {2}, {3}, {4}, {5}, {1, 2, 3}, {1, 2, 4}, . . ., {3, 4, 5}}
Los elementos extremales de S son elementos de S.

Elementos minimales:{1}, {2}, {3}, {4}, {5}. Son minimales porque no existe un conjunto
X ∈ S tal que X ⊆ {n} n ∈ {1, 2, 3, 4, 5}. Tendrı́a que ser X = ∅ pero ∅ ∈ S.

Tenemos varios minimales, luego no hay mı́nimo.

Elementos maximales: Todos los conjuntos de cardinal 3 contenidos en {1,2,3,4,5}.

Sea X = {a1 , a2 , a3 } ⊆ {1, 2, 3, 4, 5} es maximal porque no existe Y ∈ S con X  Y . Tendrı́a
que ser |Y | > 3 y no existe un elemento ası́ en S.

Tenemos varios maximales, luego no hay máximo porque tiene que ser único.

Cotas Inferiores de S. Son elementos de F  . U ∈ F  es cota inferior de S si para todo X ∈ S

se verifica U ⊆ X.
CotasInf(S) = ∅ ya que no existe un conjunto U ∈ F  tal que U ⊆ {1} . . . U ⊆ {5}. Por
tanto, este conjunto no tiene máximo y no existe el ı́nfimo de S.

Cotas Superiores de S. Son elementos de F  . U ∈ F  es cota superior de S si para todo X ∈ S

se verifica X ⊆ U .
{1, 2, 3} ⊆ U , {1, 2, 4} ⊆ U , {1, 2, 5} ⊆ U . . . {3, 4, 5} ⊆ U =⇒ {1, 2, 3, 4, 5} ⊆ U y
{1, 2, 3, 4, 5} ∈ F  aunque {1, 2, 3, 4, 5} ∈ S. Luego son cotas superiores todos los conjun-
tos U con |U | impar y tal que {1, 2, 3, 4, 5} ⊆ U
CotasSup(S) = {U ∈ F  |{1, 2, 3, 4, 5} ⊆ U, |U | impar } El mı́nimo de este conjunto es
{1,2,3,4,5} =⇒ sup(S) = {1, 2, 3, 4, 5}

10. [1.5 puntos] Sea g : Z+ −→ Z+


n si n es par
g(n) =
(n + 1)/2 si n es impar
Estudia si g es inyectiva y/o suprayectiva. En caso afirmativo demuéstralo formalmente y en caso
negativo da un contraejemplo.
Solución

No es inyectiva:
g(2) = 2 y g(3) = (3 + 1)/2 = 4/2 = 2
Es decir, existen x1 y x2 tales que g(x1 ) = g(x2 ) pero x1 = x2 .

Es suprayectiva:
∀n ∈ Z+ ∃m ∈ Z+ tal que g(m) = n
Distinguimos casos:
• Sea n par g(n) = n =⇒ m = n
• Sea n impar El m que buscamos tiene que ser impar porque si fuese par, g(m) = m que
serı́a par y, por tanto, distinto de n. m impar =⇒ g(m) = (m + 1)/2 = n =⇒ m + 1 = 2n =⇒
m = 2n − 1 entonces g(m) = g(2n − 1) = (2n − 1 + 1)/2 = 2n/2 = n