PR Actico 8: Relaciones (2 Parte) .: Matem Atica Discreta I - 2019 - 2 Semestre

Matemática Discreta I - 2019 - 2do semestre
Práctico 8: Relaciones (2da Parte).

Ref. Ref. Grimaldi 7.3 y 7.4
Relaciones de equivalencia
Ejercicio 1 Sea n un entero positivo. Definamos la relación ≡ en Z, llamada congruencia módulo n,

en la forma:
a ≡ b si a − b es divisible por n.
a. Pruebe que ≡ es una relación de equivalencia.
b. Demuestre que a ≡ b ⇐⇒ a y b dan el mismo resto al ser divididos por n.
c. Describa el conjunto cociente Z/ ≡ cuando n = 3, 2, 1.
d. Pruebe que |Z/ ≡ | tiene n elementos.
Ejercicio 2 Para cada n ∈ N ∪ {0} sea Rn el número de relaciones de equivalencia diferentes que
pueden definirse en un conjunto dado con n elementos. Para cada n, i ∈ N sea S(n, i) el número de
Stirling del segundo tipo. Pruebe que:
a. Para todo n ∈ N ∪ {0} se cumple Rn+1 = C0n Rn + C1n Rn−1 + · · · + Cnn R0 .
b. Para todo n ∈ N se cumple, Rn = S(n, 1) + S(n, 2) + · · · + S(n, n).
Ejercicio 3 En cada uno de los siguientes casos, pruebe que R es una relación de equivalencia en A
y describa el conjunto cociente A/R:
a. A = Z y aRb si a2 = b2 .
b. (Parcial 2000) A = Z y aRb si a2 y b2 dan el mismo resto al dividirlos por 5.
c. A = Z y aRb si a4 y b4 dan el mismo resto al dividirlos por 5.
d. A = R2 y vRw si existe a ∈ R no nulo tal que w = av.
Ejercicio 4 (1er parcial junio de 2017 Ej5) Hallar la cantidad de relaciones de equivalencia sobre
{0, 1, . . . , 7} tales que #[0] = 2 y #[1] = 4. Opciones: A) 60; B) 120; C) 180; D) 240.
Ejercicio 5 (Parcial 2000)

Sea M el conjunto de todas las matrices reales n × n. Pruebe que la relación ∼ en M definida por:
A ∼ B ⇔ existe P ∈ M invertible tal que B = P AP −1
es de equivalencia. Halle la clase de la matriz nula y la clase de la matriz identidad.
1
Relaciones de orden
Ejercicio 6 Sea A = {a, b, c}, calcular la cantidad de relaciones de orden que hay sobre A.
Ejercicio 7
a. Halle el número de relaciones de equivalencia en {1, 2, 3, 4} que contienen a la relación {(1, 2); (3, 4)}.
b. Ídem para relaciones de orden.
Ejercicio 8 Sea A = {1, 2, ..., 100}. ¿Qué hay más, relaciones de equivalencia o de orden en A?
Ejercicio 9 Para ensamblar cierto producto hay que realizar las 11 tareas T1 , T2 , . . . , T11 en el siguiente
orden parcial cuyo diagrama de Hasse se muestra en la Figura 1 (a). Escriba una lista de instrucciones de
4 3 2
5 6
7 8
10 11 9
(a) (b)
Figura 1:
modo tal que, al ejecutarlas según la lista, el resultado final sea el producto correctamente ensamblado.
Ejercicio 10 Un empleado de un centro de cómputos, tiene que ejecutar 10 programas P0 , P1 , . . . ,

P9 que, debido a las prioridades, están restringidos a las siguientes condiciones: P9 > P7 , P2 ; P7 > P6 ;
P6 > P4 ; P2 > P8 , P5 ; P5 > P3 , P0 ; P8 > P3 , P4 ; P3 , P4 , P0 > P1 ; donde, por ejemplo, Pi > Pj significa
que el programa Pi debe realizarse antes que el programa Pj . Determine un orden de ejecución de estos
programas de modo que se satisfagan las restricciones.
Ejercicio 11 ¿Cuáles de los diagramas de Hasse de la Figura 1 (b) representa un retı́culo?
Ejercicio 12 Demuestre que si A es un conjunto finito y ≤ es un orden en A entonces A tiene algún

elemento maximal y alguno minimal. Demuestre también que si (A, ≤) es un retı́culo (látice) y A es
finito entonces A tiene mı́nimo y máximo. ¿Es cierto alguno de estos resultado si A es infinito? (en
caso afirmativo dé una demostración y en caso negativo un contraejemplo).
2
Ejercicio 13 Muestre que en un conjunto con 61 personas, o bien hay una sucesión de 13 personas
cada una de las cuales desciende de la siguiente, o bien hay un grupo de 6 personas ninguna de las
cuales es descendiente de alguna otra.
Ejercicio 14 Para cada uno de los órdenes (A, ≤) siguientes, dibuje el diagrama de Hasse y determine
si se trata de un retı́culo:
a. A = {1, 2, 3, 4, 12} y ≤ es el orden de divisibilidad (x ≤ y sii y es múltiplo de x).
b. A es el conjunto de todos los subconjuntos de {1, 2, 3} y ≤ es la inclusión ⊆.
Ejercicio 15 Sea A un conjunto y R una relación transitiva y reflexiva en A. Considere la relación en

A definida por S = R ∩ R−1 . Pruebe que S es una relación de equivalencia y que
[a]T [b] si aRb
define una relación de orden en el conjunto cociente A/S.
Ejercicios Complementarios
Ejercicio 16 Hallar la cantidad de relaciones de equivalencia R sobre el conjunto A = {0, . . . , 9} con

# [0] = 5 y # [2] = 3.
Ejercicio 17 Hallar la cantidad de relaciones de equivalencia R sobre el conjunto A = {0, . . . , 7} con

# [4] = 2, (1, 5) ∈ R, (2, 5) ∈ R y al menos hay tres clases de equivalencia.
Ejercicio 18 (2do parcial 2006)

Sea (C, R) un conjunto parcialmente ordenado con un mı́nimo m y tal que todo subconjunto no vacı́o
posee supremo. Sea f : C −→ C creciente, es decir, tal que x R y implica f (x) R f (y). Se pide
a. Demostrar que existe el supremo de S = {x : x R f (x)}. Llamémosle p.

b. Demostrar que para todo x ∈ S, se cumple que f (x) R f (p).
c. Justificar los cuatro pasos marcados con ∗1 , ∗2 , ∗3 y ∗4 .
∗1 2∗ ∗
3 4∗
∀x ∈ S, f (x) R f (p) =⇒ f (p) es cota superior de S =⇒ p R f (p) =⇒ f (p) ∈ S =⇒ f (p) = p.
Ejercicio 19 (Del 1er parcial 2001)

Se considera el siguiente diagrama de Hasse correspondiente a un orden parcial R definido en el conjunto
A = {a, b, c, d, e, f, g, h}. Indique cuáles de las siguientes afirmaciones es correcta:
a. (A, R) es un retı́culo.
3
a
b c
d e f g
b. El elemento a es un máximo; g y f son minimales.

c. Existen exactamente 7 cadenas de cardinal 3, una de las cuales es {a, b, h}.
Ejercicio 20 (del 2do parcial 2009)

Definimos una relación en I = {2, 3, 4, 5, ..., 100, 101}:
xRy si y = x2 − 1 o si y = x.
a. La relación es de orden parcial y admite al menos 26 anticadenas con 4 elementos.

b. La relación es de orden total.
c. La relación no es de orden parcial.
d. La relación es de orden parcial y admite una anticadena con 90 elementos, y una cadena con 4
elementos.
e. La relación es de orden parcial y admite una anticadena con 91 elementos.
Ejercicio 21 (Ej1 2do examen 2001)

Sea R una relación binaria sobre un conjunto con 3 elementos, cuya matriz de 0s y 1s es:
 
1 1 1
x 1 y 
 
z w 1
¿Cuáles de las siguientes afirmaciones es correcta?:
a. R es una relación de equivalencia si y solo si x = y = z = w = 1.

b. Si R es un retı́culo entonces y + w ≥ 1.
c. Para cualquier valor de x, y, z y w la relación R es necesariamente un orden parcial.
Ejercicio 22 Sea A el conjunto de naturales n mayores que 1 que dividen a 60. Sea R la relación
en A definida por: aRb si a divide a b. ¿Es R es un orden parcial? ¿total? ¿retı́culo? Halle todos los
elementos maximales y minimales de (A, R). ¿Cuál es el cardinal más grande de una cadena en (A, R)?
¿Y el de una anticadena? ¿Cuántas cadenas de largo 2 hay?

PR Actico 8: Relaciones (2 Parte) .: Matem Atica Discreta I - 2019 - 2 Semestre

Cargado por

Copyright:

Formatos disponibles

PR Actico 8: Relaciones (2 Parte) .: Matem Atica Discreta I - 2019 - 2 Semestre

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

PR Actico 8: Relaciones (2 Parte) .: Matem Atica Discreta I - 2019 - 2 Semestre

Cargado por

Copyright:

Formatos disponibles

Matemática Discreta I - 2019 - 2do semestre

Práctico 8: Relaciones (2da Parte).

Ejercicio 1 Sea n un entero positivo. Definamos la relación ≡ en Z, llamada congruencia módulo n,

b. Para todo n ∈ N se cumple, Rn = S(n, 1) + S(n, 2) + · · · + S(n, n).

b. (Parcial 2000) A = Z y aRb si a2 y b2 dan el mismo resto al dividirlos por 5.

c. A = Z y aRb si a4 y b4 dan el mismo resto al dividirlos por 5.

d. A = R2 y vRw si existe a ∈ R no nulo tal que w = av.

Ejercicio 5 (Parcial 2000)

A ∼ B ⇔ existe P ∈ M invertible tal que B = P AP −1

es de equivalencia. Halle la clase de la matriz nula y la clase de la matriz identidad.

b. Ídem para relaciones de orden.

Ejercicio 10 Un empleado de un centro de cómputos, tiene que ejecutar 10 programas P0 , P1 , . . . ,

Ejercicio 11 ¿Cuáles de los diagramas de Hasse de la Figura 1 (b) representa un retı́culo?

Ejercicio 12 Demuestre que si A es un conjunto finito y ≤ es un orden en A entonces A tiene algún

a. A = {1, 2, 3, 4, 12} y ≤ es el orden de divisibilidad (x ≤ y sii y es múltiplo de x).

b. A es el conjunto de todos los subconjuntos de {1, 2, 3} y ≤ es la inclusión ⊆.

Ejercicio 15 Sea A un conjunto y R una relación transitiva y reflexiva en A. Considere la relación en

[a]T [b] si aRb

define una relación de orden en el conjunto cociente A/S.

Ejercicio 16 Hallar la cantidad de relaciones de equivalencia R sobre el conjunto A = {0, . . . , 9} con

Ejercicio 17 Hallar la cantidad de relaciones de equivalencia R sobre el conjunto A = {0, . . . , 7} con

Ejercicio 18 (2do parcial 2006)

a. Demostrar que existe el supremo de S = {x : x R f (x)}. Llamémosle p.

Ejercicio 19 (Del 1er parcial 2001)

b. El elemento a es un máximo; g y f son minimales.

Ejercicio 20 (del 2do parcial 2009)

a. La relación es de orden parcial y admite al menos 26 anticadenas con 4 elementos.

Ejercicio 21 (Ej1 2do examen 2001)

¿Cuáles de las siguientes afirmaciones es correcta?:

a. R es una relación de equivalencia si y solo si x = y = z = w = 1.

También podría gustarte