EXAMEN de Matemática Discreta y Lógica Matemática
(Febrero 2016) Modelo 1
NOMBRE:
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 2 horas y media.
Cada una de las ocho primeras preguntas es tipo test y tiene una única respuesta correcta. Cada
pregunta respondida correctamente puntuará 0,75 puntos. Cada pregunta respondida incorrectamente
puntuará -0,25 puntos. Las preguntas sin contestar puntuarán 0 puntos.
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. Si A 6= ∅ y B 6= ∅, entonces:
(A \ B) ∪ (A ∩ B) = ∅ (A \ B = A − B)
(A \ B) ∩ (A ∩ B) 6= ∅
X (A \ B) ∩ (A ∩ B) = ∅
(A \ ∅) ∪ (B \ ∅) = A
Solución
A\B = A∩B Conmutativa Asociativa Asociativa
↓ ↓ ↓ ↓
(A \ B) ∩ (A ∩ B) = (A ∩ B) ∩ (A ∩ B) = (B ∩ A) ∩ (A ∩ B) = B ∩ (A ∩ (A ∩ B)) =
= B ∩ ((A ∩ A) ∩ B) = B ∩ (A ∩ B) = B ∩ (B ∩ A) = (B ∩ B) ∩ A = ∅ ∩ A = ∅
↑ ↑ ↑ ↑
Idempotente Conmutativa Asociativa B ∩ B = ∅
2. Dados a, b, c ∈ Z tales que a|c y b|c y m.c.d.(a, b) = 1 entonces
X a·b c
a · b c sólo si a y b son primos.
a · b c sólo si a + b es primo.
a·b 6| c
Solución.
Si mcd(a, b) = 1, =⇒ existen m, n ∈ Z m · a + n · b = 1.
Si a | c =⇒ c = a · t1
Si b | c =⇒ c = b · t2
Multiplicamos m · a + n · b = 1 por c =⇒ c = m · a · c + n · b · c =⇒ c = m · a · (b · t2 ) + n · b · (a · t1 ) =
a · b(m · t2 + n · t1 ) =⇒ a · b | c.
3. ¿Cuál de las tres definiciones de la función f : N → N es la definición recursiva correcta?
f (0) = 0; f (n) = 3f (n − 2) (n ≥ 2)
f (0) = 0; f (n) = 3f (n − 1) + 2f (n − 2) (n ≥ 2)
X f (0) = 0; f (2n) = 4f (n) (n ≥ 1); f (2n + 1) = 4f (n) + 3 (n ≥ 0)
Ninguna lo es.
Solución
Tanto en el primer caso como en el segundo f (1) no está definido.
La tercera definición si es correcta pues n < 2n si n ≥ 1 y n < 2n + 1 si n ≥ 0.
f (0) = 0
f (1) = f (2 · 0 + 1) = 4f (0) + 3 = 3
f (2) = f (2 · 1) = 4f (1) = 4 · 3 = 12
f (3) = f (2 · 1 + 1) = 4f (1) + 3 = 4 · 3 + 3 = 15
f (4) = f (2 · 2) = 4f (2) = 4 · 12 = 48
..
.
4. Sean f : A −→ B una función inyectiva y fˆ : P(A) −→ P(B) definida como:
fˆ(X) = {f (x) | x ∈ X}
Indica la respuesta correcta:
fˆ puede no ser inyectiva ni suprayectiva.
X fˆ es inyectiva pero puede no ser suprayectiva.
fˆ no es inyectiva pero puede ser suprayectiva.
fˆ es siempre biyectiva.
Solución
Vamos a demostrar que fˆ es inyectiva:
Si fˆ(X) = fˆ(Y ) =⇒ X = Y
fˆ(X) = {f (x) | x ∈ X} = fˆ(Y ) = {f (y) | y ∈ Y }
Vamos a demostrar que X ⊆ Y y Y ⊆ X.
Sea x ∈ X =⇒ f (x) ∈ fˆ(X) = fˆ(Y ) =⇒ f (x) = f (y) para algún y ∈ Y. Como f es inyectiva,
x = y luego x = y ∈ Y , es decir X ⊆ Y .
Sea y ∈ Y =⇒ f (y) ∈ fˆ(Y ) = fˆ(X) =⇒ f (y) = f (x) para algún x ∈ X. Como f es inyectiva,
y = x luego y = x ∈ X, es decir Y ⊆ X.
f no tiene por qué ser suprayectiva:
A = {1, 2} B = {a, b, c} y sea f : A −→ B definida por f (1) = a; f (2) = b
Si Y = {c} no existe X ⊆ A tal que fˆ(X) = {c} En efecto:
Como f es inyectiva se cumple: |X| = n =⇒ |fˆ(X)| = n
X = {x1 , x2 , . . . , xn } se verifica xi 6= xj si i 6= j y al ser f inyectiva =⇒ f (xi ) 6= f (xj ))
Si existiera X con fˆ(X) = {c} tendrı́a que ser X = {x1 } =⇒ fˆ(X) = {f (x1 )} = {c} =⇒ f (x1 ) = c
lo que es imposible porque f no es suprayectiva y no existe x tal que f (x) = c.
5. Sea f : N → P(N), podemos afirmar que:
X f no puede ser suprayectiva.
f no puede ser inyectiva.
f no puede ser total.
No tenemos información suficiente para conocer la respuesta correcta.
Solución.
Aplicando la segunda parte del siguiente teorema:
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.
si f fuese suprayectiva P(N) tendrı́a que ser numerable y sabemos que no lo es, luego f no puede ser
suprayectiva.
Además si definimos f : N −→ P(N) como f (n) = {n} es una función total e inyectiva.
6. Sea C la familia de conjuntos definida como:
C = {{n ∈ N | n ≥ m} | m ∈ N, m ≤ 5}
Indica la respuesta correcta:
S
X C es un conjunto finito y C = N.
S
C es un conjunto infinito numerable y C = N.
S
C es un conjunto finito y C = P(N).
S
C es un conjunto infinito numerable y C = P(N).
C = {{n ∈ N | n ≥ m} | m ∈ N, m ≤ 5}
Sea Am = {n ∈ N | n ≥ m} m ≤ 5 =⇒ m = 0, 1 . . . 5
A0 = {n ∈ N | n ≥ 0}
A1 = {n ∈ N | n ≥ 1}
..
.
A5 = {n ∈ N | n ≥ 5}
C = {A0 , A1 , . . . , A5 }
C = 5i=1 Ai = A0 ∪ · · · ∪ A5 = {n ∈ N | n ≥ 0} = N
S S
7. Sea N+ = N \ {0}. Definimos la función f : N+ −→ N+ tal que:
1 si n = 1
f (n) =
número de factores primos distintos que tiene n si n > 1
Sea X = {1, 2, 3, 4} y sea R ⊆ X × X la relación binaria definida por xRy ⇔ f (x) < y, ∀x, y ∈ X.
Indica la respuesta correcta:
R es reflexiva.
R es antirreflexiva.
X R es conexa.
Ninguna de las anteriores.
Solución.
f (1) = 1
f (2) = 1
f (3) = 1
f (4) = 1
Reflexiva: ∀x xRx ⇐⇒ f (x) < x pero f (1) ≮ 1 ⇐⇒ 1 6 R 1, luego no es reflexiva.
(∀x 6= 1 f (x) = 1 < x ya que x ≥ 2 =⇒ xRx ∀x ≥ 2)
Antirreflexiva: ∀x x 6 R x ⇐⇒ f (x) ≮ x
Contraejemplo x = 2 f (2) = 1 < 2 ⇐⇒ 2R2 Luego no es antirreflexiva.
Conexa: ∀x, y x 6= y =⇒ xRy ó yRx
∀x∀y (y ≥ 2 =⇒ f (x) < y =⇒ xRy)
Si y = 1 =⇒ ∀x x ≥ 2 =⇒ f (x) = 1 ≮ 1 =⇒ x 6 R 1 pero en este caso f (1) = 1 < x =⇒ 1Rx
8. Dado el siguiente diagrama de Hasse, indica la respuesta correcta.
x w y
e
v
c b d
a
⊓(e, x) = b y ⊔(d, v) = y. (⊓(e, x) = inf (e, x)) ⊔(d, v) = sup(d, v))
⊓(e, x) = b y ⊔(d, v) = z.
X ⊓(e, x) = c y ⊔(d, v) = y.
⊓(e, x) = c y ⊔(d, v) = z.
Solución.
CotasInf ({e, x}) = {c, a} =⇒ max(CotasInf ({e, x}) = max({c, a}) = c
CotasSup({d, v}) = {y, z} =⇒ min(CotasSup({d, v}) = min({y, z}) = y
9. [1,5 puntos] Sea A = {1, 2, 3, 4, 5} y B = {3, 4}. Definimos la relación R en P(A) como:
XRY ⇐⇒ B ∪ X = B ∪ Y, X, Y ⊆ A
a) Demuestra que R es de equivalencia sobre P(A).
b) Determina la clase de equivalencia de {1, 3}.
Solución
a) Reflexiva: ∀X XRX ⇐⇒ B ∪ X = B ∪ X, X ⊆ A que se cumple, luego es reflexiva.
Simétrica: ∀X, Y XRY =⇒ Y RX
XRY ⇐⇒ B ∪ X = B ∪ Y =⇒ B ∪ Y = B ∪ X ⇐⇒ Y RX. Luego es simétrica.
Transitiva: ∀X, Y, Z XRY ∧ Y RZ =⇒ XRZ
XRY ⇐⇒ B ∪ X = B ∪ Y Y RZ ⇐⇒ B ∪ Y = B ∪ Z =⇒ B ∪ X = B ∪ Y = B ∪ Z luego
XRZ. Luego es transitiva.
b) [{1, 3}]R = {X ⊆ A|XR{1, 3}} = {X ⊆ A|B ∪ X = B ∪ {1, 3}} = {X ⊆ A|B ∪ X = {3, 4} ∪ {1, 3} = {1, 3, 4}}
[{1, 3}]R = {X ⊆ A|B ∪ X = {1, 3, 4}}
Se tiene que cumplir B ∪ X = {1, 3, 4}. Además sabemos que X ⊆ B ∪ X = {1, 3, 4} y
1 ∈ B ∪ X, 1 6∈ B =⇒ 1 ∈ X Luego los posibles valores de X son:
X = {1, 3} {3, 4} ∪ {1, 3} = {1, 3, 4}
X = {1} {3, 4} ∪ {1} = {1, 3, 4}
X = {1, 4} {3, 4} ∪ {1, 4} = {1, 3, 4}
X = {1, 3, 4} {3, 4} ∪ {1, 3, 4} = {1, 3, 4}
[{1, 3}]R = {X ⊆ A|B ∪ X = {1, 3, 4}} = {{1, 3}, {1}, {1, 4}, {1, 3, 4}}
10. [1 punto] Sea f : R → R una función biyectiva. Estudia si la función g : R → R definida como
g(x) = 2f (x) + 3 es biyectiva o no. En caso afirmativo demuestralo formalmente y en caso negativo da
un contraejemplo.
Solución
Vamos a demostrar que g es inyectiva:
Si g(x) = g(y) =⇒ x = y
g(x) = 2f (x) + 3 = g(y) = 2f (y) + 3 =⇒ 2f (x) = 2f (y) =⇒ f (x) = f (y) =⇒ x = y al ser f
inyectiva.
g es suprayectiva:
∀z ∈ R ∃x ∈ R tal que g(x) = z
Se tiene que cumplir:
z−3
g(x) = 2f (x) + 3 = z =⇒ f (x) = ∈ R Como f es suprayectiva existe x0 ∈ R tal que
2
z−3 z − 3
f (x0 ) = Luego g(x0 ) = 2f (x0 ) + 3 = 2 + 3 = (z − 3) + 3 = z
2 2
11. [1,5 puntos] Demostrar por inducción que ∀n ≥ 0 se verifica an = 3 + n(n − 1)2 donde:
a0 = 3
an = an−1 + 3(n − 1)2 − n + 1 si n ≥ 1
Solución:
Base: a0 = 3 = 3 + 0(0 − 1)2 = 3 Luego se cumple.
Paso Inductivo S(1), . . . , S(k) =⇒ S(k + 1)
(Aplicamos inducción simple porque la definición recursiva de an depende sólo de an−1
(HI) S(k) ≡ ak = 3 + k(k − 1)2
?
S(k + 1) ≡ ak+1 = 3 + (k + 1)k 2
H.I. ak = 3 + k(k − 1)2
↓
ak+1 = ak + 3(k + 1 − 1)2 − (k + 1) + 1 = 3 + k(k − 1)2 + 3k 2 − k = 3 + k(k 2 − 2k + 1) + 3k 2 − k =
= k(k 2 ) − 2k 2 + k + 3k 2 − k = 3 + k(k 2 ) + k 2 = 3 + k 2 (k + 1)
