ejercicios

X1

(r elementos)

X2

(r elementos) ….…..

Xk

(r elementos)

X

Facultad de Ingeniería de Sistemas Matemática Discreta Ejemplo Es sencillo verificar que la relación R = {(a,a), (b,b), (c,c)} sobre X = {a,b,c} es reflexiva, simétrica y transitiva. Así, R es una relación de equivalencia. Las clases de equivalencia son [a]={a}, [b]={b}, [c]={c}.

Ejemplo Sea X ={ 1,2,…;10}. Definimos x R y para indicar que 3 divide a x – y. Es sencillo verificar que la relación R es reflexiva, simétrica y transitiva. Así, R es una relación de equivalencia sobre X. Se determinarán los miembros de las clases de equivalencia. La clase de equivalencia [1] consiste en todas las x con x R 1. Entonces 1 = {x є X |divide x-1 } = { 1,4,7,10 }.De manera similar, [2] = { 2, 5, 8 }, [3] = { 3, 6, 9 }. Estos tres conjuntos son una partición de X. Observe que [1]= [4]= [7]= [10], [2]= [5]=[8], [3]=[6]=[9]. Para esta relación, equivalencia es “tiene el mismo residuo al dividir entre 3”.Esta sección se cierra con la prueba de un resultado especial que se necesitará más adelante. La prueba se ilustra en la figura

|X|= rkPrueba del Teorema

|X|= rkPrueba del Teorema

Teorema Sea R una relación de equivalencia en un conjunto finito X. Si cada clase de equivalencia tiene r elementos, existen |X|/r clases de equivalencia.Demostración: Sean X1 , X2 , ….., Xk las distintas clases de equivalencia. Como estos conjuntos hacen una partición de X.

|X|= |X1|+ |X2|+ …. + |Xk|= r + r +…… + r = kr y se deriva la conclusión.Sugerencias para resolver problemasUna relación de equivalencia es una relación reflexiva, simétrica y transitiva. Para probar que una relación es de equivalencia, es necesario verificar que estas tres propiedades se cumplen. Una relación de equivalencia en un conjunto X crea una partición de X en subconjuntos (“Crear una partición” significa que cada x en X pertenece a exactamente uno de los subconjuntos de la partición.) Los subconjuntos que forman la partición se determinan de la siguiente manera. Elija x 1

є X. Encuentre el conjunto, denotado por [x1], de todos los elementos relacionados con x1. Elija otro elemento x2 є X que no esté relacionado con x1. Encuentre el conjunto [x2] de todos los elementos relacionados con x2. Continúe de esta forma hasta que todos los elementos de X estén asignados a un conjunto. Los conjuntos [x1] se llaman clases de equivalencia. La partición es [x1], [x2], …Los elementos de [xi.] son equivalentes en el sentido de que todos están relacionados. Por ejemplo, la relación R, definida por x R y si x y y son del mismo color, particiona el conjunto en subconjuntos donde cada subconjunto contiene los elementos que son todos del mismo color. Dentro de un subconjunto, los elementos son equivalentes en el sentido de que todos son de mismo color.

Julián Sotomayor Isaí Flores Javier Díaz Percy Figueroa

Facultad de Ingeniería de Sistemas Matemática Discreta En la digráfica de una relación equivalente, una clase de equivalencia es la subgráfica más grande de la digráfica original que tiene la propiedad de que para cualesquiera vértices v y w en G, existe una arista dirigida de v a w.Una partición de un conjunto da lugar a una relación de equivalencia. Si x1, …, xn es una partición del conjunto X y se define x R y si para alguna i, x y y pertenecen ambos a x i, entonces R es una relación de equivalencia sobre X. Las clases de equivalencia resultan ser x1 , …., xn. Así, “relación de equivalencia” y “partición de un conjunto” son diferentes puntos de vista de la misma situación. Una relación de equivalencia sobre X da lugar a una partición, y una partición de X da lugar a una relación de equivalencia.

EjerciciosEn los ejercicios 1 al 8, determine si la relación indicada es una relación de equivalencia en { 1, 2, 3, 4, 5}. Si la relación es una relación de equivalencia. (En los ejercicios 5 al 8, { 1, 2, 3, 4, 5 }.)1. { (1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1) }2. { (1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1), (3,4), (4,3) }3. { (1,1), (2,2), (3,3), (4,4) }4. { (1,1), (2,2), (3,3), (4,4), (5,5), (1,5), (5,1), (3,5), (5,3), (1,3), (3,1) }5. { (x,y) |1≤x≤5 y 1≤y≤5 }6. { (x,y) |4 divide a x-y }7. { (x,y) |3 divide a x+y }8. { (x,y) |x divide a 2-y }En los ejercicios 9 al 14, determine si la relación indicada es una relación de equivalencia en el conjunto de todas las personas.9. { (x,y) |x y y son de la misma altura }10. { (x,y) |x y y en algún momento han vivido en el mismo país }11. { (x,y) |x y y son tienen el mismo nombre }12. { (x,y) |x es más alto que y }13. { (x,y) |x y y tienen los mismos padres }14. { (x,y) |x y y tienen el mismo color de pelo }En los ejercicios 15 al 20, liste los miembros de la relación de equivalencia en { 1, 2, 3, 4 } definida por la partición dada. Además, encuentre las clases de equivalencia [1],[2],[3] y [4].15. { { 1,2}, {3,4} }16. { {1}, {2}, {3,4} }17. { {1}, {2}, {3}, {4} }18. { {1,2,3}, {4} } 19. { {1,2,3,4} }20. { {1}, {2,4}, {3} }En los ejercicios 21 al 23, sea X={1,2,3,4,5}, Y={3,4} y C={1,3}. Defina la relación R en P(X), el conjunto de todos los subconjuntos de X, como A R B si A U Y = B U Y.21. Demuestre que R es una relación de equivalencia.22. Liste los elementos de [C], la clase de equivalencia que contiene a C.23. ¿Cuántas clases de equivalencia diferentes hay ?24. Sea X = { San Francisco, Pittsburg, Chicago, San Diego, Filadelfia, Los Ángeles }. Defina una relación R sobre X como x R y si x y y están en el mismo estado.a) Demuestre que R es una relación de equivalencia.


S

y

x

(0,1) (1,1)

(1,0)(0,0)

Facultad de Ingeniería de Sistemas Matemática Discreta b) Liste las clases de equivalencia de X.c) Demuestre que si R es una relación de equivalencia sobre X, entonces dominio R = rango R = X.25. Si una relación de equivalencia tiene sólo una clase de equivalencia, ¿Cómo debe verse la relación?26. Si R es una relación de equivalencia en un conjunto X y [X] = [R], ¿Cómo debe verse la relación?27. Listando los pares ordenados, dé un ejemplo de una relación de equivalencia en {1,2,3,4,5,6} que tiene exactamente cuatro clases de equivalencia.28. ¿Cuántas relaciones de equivalencia hay en el conjunto {1,2,3}?29. Sea X = {1,2, …, 10}. Defina una relación R sobre X x X como (a,b) R (c,d) si a + d = b + c.a) Demuestre que R es una relación de equivalencia sobre X x X.b) Liste un miembro de cada clase de equivalencia en X x X. 30. Sea X = {1,2, …, 10}. Defina una relación R sobre X x X como (a,b) R (c,d) si ad = bc.a) Demuestre que R es una relación de equivalencia sobre X x X.b) Liste un miembro de cada clase de equivalencia en X x X. c) Describa la relación R en términos familiares.31. Sea R una relación reflexiva y transitiva sobre X. Demuestre que R ∩ R-1 es una relación de equivalencia sobre X.32. Sean R1 Y R2 relaciones de equivalencia sobre X.a) Demuestre que R1 ∩ R2 es una relación de equivalencia sobre X.b) Describa las clases de equivalencia de R1 ∩ R2 en términos de las clases de equivalencia de R1 y las clases de equivalencia de R2.33. Suponga que S es una colección de subconjuntos de un conjunto X y X = U S. (No se supone que la familia S sea disjunta por pares). Defina x R y de manera que para algún conjunto S є S, ambas x y y están en S. ¿Es R necesariamente reflexiva, simétrica y transitiva?34. Sea S un cuadrado unitario que incluye el interior, como se muestra en la figura que sigue.

35. Defina la relación R en S por (x,y) R (x’, y’) si (x = x’ y y = y’) o (y = y’ y x= 0 y x’ = 1) o (y = y’ y x= 1 y x’ = 0).a) Demuestre que R es una relación de equivalencia en S.b)Si los puntos en la misma clase de equivalencia se engomaran, ¿cómo describiría la figura que se forma?


Facultad de Ingeniería de Sistemas Matemática Discreta 36. Sea S un cuadrado unitario que incluye el interior (como en el ejercicio 35). Defina una relación R’ en S por (x,y) R’ (x’,y’) si (x = x’ y y = y’) o (y = y’ y x= 0 y x’ = 1) o (y = y’ y x= 1 y x’ =0) o (x = x’ y y= 0 y y’ = 1) o (x = x’ y y= 1 y y’ =0). SeaR = R’ U {((0,0), (1,1)), ((0,1), (1,0)), ((1,0), (0,1)), ((1,1), (0,0))} a) Demuestre que R es una relación de equivalencia en S.b) Si los puntos en la misma clase de equivalencia se engomaran, ¿cómo describiría la figura que se forma?37. Sea f una función de X a Y. Defina una relación R sobre X por x R y si f(x) = f(y). Demuestre que R es una relación de equivalencia sobre X.38. Sea f una función característica en X. Defina la relación R sobre X por x R y si f(x) = f(y). De acuerdo con el ejercicio anterior, R es una relación de equivalencia. ¿Cuáles son las clases de equivalencia?39. Sea f una función de X a Y. Sea S = { f-1({y}) | y є Y }. Demuestre que S es una partición de X. Describa una relación una relación de equivalencia que dé lugar a esta partición.40. Sea R una relación de equivalencia en un conjunto A. Defina una función f de A al conjunto de clases de equivalencia de A mediante la regla f(x) = [x]. ¿Cuándo se tiene f(x) = f(y)?41. Sea R una relación de equivalencia en el conjunto A. Suponga que g es una función de A a un conjunto X que tiene la propiedad de que si x R y, entonces g(x) = g(y). Demuestre que h([x]) = g(x) define una función del conjunto de clases de equivalencia de A a X. [ Lo que debe probarse es que h asigna de manera única un valor a [x]; es decir, si [x] = [y], entonces g(x) = g(y)].42. Sea X el conjunto de sucesiones con dominio finito. Define una relación R sobre X como s R t si |dominio s|= |dominio t| y, si el dominio de s es { m, m+1, …., m+k} y el dominio de t es { n, n+1, .., n+k }, sm+i=tn+i para i=0, … , k.a) Demuestre que R es una relación de equivalencia.b) Explique en palabras que significa que dos sucesiones en X sean equivalentes bajo la relación R.c) Como una sucesión es una función, una sucesión es un conjunto de pares ordenados. Dos sucesiones son iguales si los dos conjuntos de pares ordenados son iguales. Compare las diferencias entre las dos sucesiones equivalentes en X y las dos sucesiones iguales en X.Sea R una relación en un conjunto X. Definaρ(R) = R U { (X,X) | x є X}σ(R) = R U R-1

Rn = R o R o R o…o R (nR’s)τ(R) = U { Rn | n = 1, 2,….}.La relación τ(R) se llama cerredura transitiva de R.43. Para las relaciones R1 y R2 del ejercicio 38, sección 3.1, encuentre ρ(Ri), σ(Ri), τ(Ri), y τ(σ(ρ(Ri))) para i = 1, 2.44. Demuestre que ρ(R) es reflexiva.45. Demuestre que σ(R) es simétrica. 46. Demuestre que τ(R) es transitiva.47. Demuestre que τ(σ(ρ(R))) es una relación de equivalencia que contiene a R.48. Demuestre que τ(σ(ρ(R))) es la relación de equivalencia más pequeña sobre X que contiene a R; es decir, demuestre que si R’ es una relación de equivalencia sobre X y R’ es una relación de equivalencia sobre X y R’ ⊇ R, entonces R’ ⊇ τ(σ(ρ(R))).Rincón de solución de problemas – Relaciones de equivalenciaProblema


Facultad de Ingeniería de Sistemas Matemática Discreta Responda a las siguientes preguntas para la relación R definida sobre el conjunto de cadenas de 8 bits por s1 R s2 , siempre que los primeros 4 bits de s1 y s2 coincidan.a) Demuestre que R es una relación de equivalencia.b) Liste un miembro de cada clase de equivalencia.c) ¿Cuántas clases de equivalencia hay?Resumen de la técnicas de solución de problemas

Liste los elementos que están relacionados. Calcule algunas clases de equivalencia, es decir, liste todos los elementos relacionados con

un elemento específico. Resulta útil resolver los incisos de un problema en un orden diferente que el indicado en el

enunciado del problema. Para demostrar que una relación específica R es una relación de equivalencia, vaya a las

definiciones. Pruebe que R es reflexiva, simétrica y transitiva verificando directamente que R satisface la definición de éstas.

Si el problema es contar el número de elementos que satisfacen alguna propiedad y el número es suficientemente pequeño, basta dar una lista de los elementos y contarlos.

Solución:a) Se cumple que R es reflexiva, transitiva y simétrica por lo tanto es una relación de equivalencia.b)

00000000 00010000 00100000 00110000 01000000 01010000 01100000 01110000 10000000 10010000 10100000 10110000 11000000 11010000 11100000 11110000

es una lista con un miembro de cada clase de equivalencia.c) Existen 16 clases de equivalencia.Matrices de relacionesUna matriz es una manera conveniente de representar una relación R de X a Y. Se puede usar en la computadora para analizar una relación. Se etiquetan los renglones con elementos X, y se etiquetan las columnas con elementos de Y. El elemnto en el renglón x y la columna y se hace igual a 1 si xRy, y a 0 de otra manera, llamándose matriz de relación R (relativa al orden de X y Y).

Ejemplo La matriz de la relación R = { (1,b), (1,d), (2,c), (3,c), (3,b), (4,a) } de X= {1, 2, 3, 4} a Y= {a, b, c, d} respecto a los órdenes 1, 2, 3, 4 y a, b, c, d es

a b c d

1234(0 1 0 10 0 1 001

10

1 00 0

)Ejemplo La matriz de la relación R del ejemplo 3.3.1 relativa a los órdenes 2, 3, 4, 1 y d, b, a, c es


Facultad de Ingeniería de Sistemas Matemática Discreta

d b a c

2341(0 0 0 10 1 0 101

01

1 00 0

)Es evidente que la matríz de una relación de X a Y es dependiente de los órdenes de X y Y.


Documents

ejercicios