Lista 5 de Matemáticas Discretas

Iván Giovanny Mosso Garcı́a

IPN-ESCOM

Instrucciones.- Enviar al correo tareasigmg@[Link] las soluciones a los problemas del 1, 2, 3,

8, 9, 10, 11, 13 y 14 escritos a mano, en un solo archivo en formato PDF, a más tardar el martes 14
de juniol. Entregar en equipos de 3 a 7 personas. Utilizar hojas de reciclaje, o escribir por ambos lados,
o hacer uso de algún aplicación para apuntes a [Link] la resolución de un ejercicio pueden utilizar
todos hechos vistos en clase y los anteriores anteriores al que esté en cuestión. Colocar portada con el
nombre de los integrantes. El asunto del correo debe ser Lista5 1AM1 o Lista2 1BM1 según corresponda
su grupo. .

1. Para cada uno de los siguientes aspectos computacionales defina tres conjuntos A, B, C y dos rela-
ciones R de A en B y S de B en C. Determine a que relaciones repesentarian S ◦ R y R−1 . Por
ejemplo, en un teléfono movil podemos definir a A como el conjunto de los contactos, B el conjunto
de los números telefónicos y C el conjunto de las localidades de memoria, entonces aRb si a tiene
el número b, bSc b está almacenado en la localidad c, luego aS ◦ Rc si algún número de a está
almacenado en la localidad c, y bR−1 a si el número b es propiedad de a.
a) Una red social.
b) Un servicio de streaming de música.
c) Un sistema operativo.

2. Sea R una relación de A en B. Sea aR0 b la relación de A en B donde aR0 b si a 6 Rb, es decir si a
no está relacionada con b a través de R. Demuestre que (R0 )−1 = (R−1 )0 .
Demostración.- Tenemos que R es una relación de A en B, luego R0 es una relación de A en B
y R−1 es una relación de en , entonces (R0 )−1 es una relación y es una
relación B en A.
Ahora b(R0 )−1 a ssi R0 ssi a 6 Rb ssi b 6 R−1 ssi . 

3. Sea A = {1, 2, 3, 4}, B = {a, b, c, d, e} y C = {α, β, γ}. Considere las siguientes relaciones
R ⊆ A × B, donde R = {(1, b), (1, c), (2, c), (3, a), (3, e), (4, a), (4, b), (4, d), (4, e)},
S ⊆ B × C, donde S = {(a, β), (a, γ), (b, γ), (c, β), (e, α), (e, β)},
T ⊆ A × A, donde T = {(1, 3), (2, 2), (2, 3), (2, 4), (3, 1), (4, 1), (4, 4)},
U ⊆ B × B, donde U = {(a, a), (a, e), (b, c), (c, b), (d, a), (d, b), (d, e), (e, a), (e, e)},
V ⊆ C × C, donde V = {(α, γ)}.
Encuentre

a) R−1
b) S ◦ R
c) R−1 ◦ S −1
d ) R−1 ◦ R
e) (R ◦ T )−1
f ) V ◦ (S ◦ R)

1
 2

g) V ◦ (S ◦ U)
h) (U ◦ R) ◦ T
4. Sea A = {1, 2, 3, 4}, B = {a, b, c, d, e}, C = {α, β, γ, δ}. Considere las siguientes relaciones.
a) f ⊆ A × B, donde f = {(1, b), (2, c), (3, a), (3, e), (4, d), (4, e)}
b) g ⊆ B × C, donde g = {(a, β), (b, γ), (c, β), (d, β), (e, β)}
c) h ⊆ A × A, donde h = {(1, 3), (2, 2), (4, 4)}
d ) k ⊆ C × B, donde k = {(α, a), (β, b), (γ, c), (δ, d)}
e) l ⊆ A × C, donde l = {(1, α), (2, δ), (3, γ), (4, β)}
f ) m ⊆ A × C, donde m = g ◦ f
g) n ⊆ C × A, donde n = f −1 ◦ g −1
Determine para cada relación si es o no función, en caso de no ser función justifique el porqué.
En caso de ser función, determine si es inyectiva, suprayectiva y/o biyectiva, justifique para las
propiedades que no se cumplan.

5. Sean f : A → B y g : B → C. Complete las demostraciones de las siguientes proposiciones.

a) Si f −1 es función, entonces f −1 es biyectiva.
Demostración.- Primero recordemos que que si f es función, entonces f −1 es función ssi
f es . Ahora supongamos que f −1 es función. Luego (f −1 )−1 ssi
. Como (f −1 )−1 = y f es función, entonces (f −1 )−1 es , se
sigue que . 

b) Si f es biyectiva, entonces f −1 ◦ f = idA .

Demostración.- . Entonces f −1 es una función de en .
Sea a ∈ A. Sea b ∈ B tal que f (a) = . Luego (f −1 ◦ f )(a) = f −1 ( ) = f −1 ( )=
= idA ( ). Por lo tanto . 

c) Si g ◦ f es inyectiva, entonces f es inyectiva.

Demostración.- . Sean tales que
f (a1 ) = f (a2 ) por probar que a1 = . Tenemos que = g(f (a2 )), es decir
(g ◦ f )( )= . Como g ◦ f es , entonces . 

d ) Si g ◦ f es suprayectiva, entonces g es suprayectiva.

Demostración.-

e) Si f y g son biyectivas, entonces g ◦ f es biyectiva.

Demostración.-

6. De un ejemplo discreto finito, uno discreto infinito y uno continuo de lo que se pide.
a) f función pero f −1 no función.
b) f función inyectiva pero f −1 no función.
c) f función suprayectiva pero f −1 no función.
d ) f y g no funciones pero g ◦ f función.

IPN-ESCOM IGMG
 3

e) f función inyectiva pero g ◦ f función no inyectiva.

f ) g función suprayectiva pero g ◦ f función no suprayectiva.
g) f fucnión no suprayectiva, g función no inyectiva pero g ◦ f función biyectiva.
7. De acuerdo al ejercicio anterior, ¿cuáles de las recı́procas de las proposiciones del problema 5 son
falsas?.

8. Para los siguientes incisos considere a R una relación en A. Determine si la relación es o no es

reflexiva, irreflexiva, simétrica, antisimétrica y/o transitiva. Determine si es o no de equivalencia.
De si es de orden parcial, orden total, orden parcial estricto o orden total estricto. Justifica tus
respuestas.

a) Si A = {1, 2, 3, 4, 5} y aRb cuando a + b < 6.

b) Si A = Z y aZb cuando a2 = b2 .
c) Si X es un conjunto, A = P(X) y CRD cuando C ⊆ D.
d ) Si A es un conjunto de proposiciones y pRq si p ⇔ q.
e) Si A = Z y aRb cuando ab ≥ 0 y a | b

9. Sea A = {1, 2, 3, 4, 5, 6, 7}. Sean

R = {(1, 2), (1, 3), (2, 3), (3, 3), (3, 4), (4, 2), (5, 6), (7, 6)},

S = {(2, 6), (3, 5), (4, 3), (4, 2), (5, 1), (6, 5), (7, 1)},
√
−T = {(1, 5), (1, 7), (2, 1), (2, 3), (4, 6), (4, 7), (5, 3), (7, 7)}
relaciones en A. Encuentre

a) clr (R), cls (R) y clt (R);

b) clr (S), cls (S) y clt (S);
√ √ √
c) clr ( −T ), cls ( −T ) y clt ( −T );
d ) clr (cls (S));
e) clr (clt (S));
f ) cls (clt (clr (R)));
√
g) clt (cls (clr ( −T )));

10. Considere al conjunto A y la relación S como en el ejercicio 2. Sea ≺ = clt (S). Determine el diagrama
de nivel de la relación de orden, identifique los minimales y maximales, en su caso determine si alguno
es máximo o mı́nimo.
11. Considere al conjunto A y la relación R como en el ejercicio 2. Sea V = clt (cls (clr (R))). Encuentre
A/V.
12. Sea A = {f : R → R}, es decir, A es el conjunto de todas las funciones reales. Sea R una relación
en A dada por f Rg si f − g es continua. Demuestre que R es de equivalencia. Investigue cual serı́a
la clase de equivalencia de la función f (x) = x.
13. Encuentre los inversos multiplicativos para los elementos que lo tengan en Z/5Z, Z/7Z y Z/15Z.

14. Calcule el residuo de la división

a) entre 1251 y 5.
b) entre 7250 y 9.
c) entre 6101 − 399 y 11.
d ) entre 525 + 840 y 17.

IPN-ESCOM IGMG
 4

15. Suponga que tenemos un número desconocido de cajas pero sabemos que cuando se agrupan en
colecciones de siete sobran tres, en colecciones de cinco sobran dos y en colecciones de tres sobra
una. ¿Cuál es la cantidad mı́nima posible de cajas?
16. Suponga que tenemos un número desconocido de cajas pero sabemos que cuando se agrupan en
colecciones de cuatro sobran tres, en colecciones de quince sobra una y en colecciones de trece
sobran cinco. ¿Cuál es la cantidad mı́nima posible de cajas?

IPN-ESCOM IGMG