Ensaro

Matemáticas Discretas

Unidad III: Relaciones y Funciones

Relación de Equivalencia
 Una relación ℜ en un conjunto A se llama relación  de equivalencia si es reflexiva, simétrica y transitiva. Ejemplo: 
 Sea A={1,2,3,4} y sea 

R  ={(1,1),  (1,2),  (1,3),  (2,1),  (2,2),  (2,3),  (3,1),          (3,2), (3,3), (4,4)}   Entonces R es una relación de EquivalenciaRelación de Equivalencia
Ejercicios:   Sea A={w, x, y ,z} determine si las relaciones      son relaciones de equivalencia. 
1 1 0 1 1 1 1 0 0 1 1 0 1 1 0 1

MR  =

ℜ = {(w,w), (w,x),  (x,w),          (x,x),  (y,w), (y,y),             (w,y), (z,w), (z,z)}  

Relación de Equivalencia
 Cualquier partición de A da lugar a una relación 

de  equivalencia.  Entonces  a  R  se  le  llamará relación de equivalencia determinada por ℘
 Si a ∈ A, entonces  a está en el mismo bloque 

que ella misma y por lo tanto a R a.

 Si  a  R  b,  entonces  a  y  b  están  en  el  mismo 

bloque, en consecuencia b R a.
 Si  a  R  b  y  b  R  c,  entonces  a,  b  y  c  deben 

estar todos en el mismo bloque de ℘y por lo  tanto a R c. 4
Matemáticas Discretas ­Semestre B­2006

Relación de Equivalencia Ejercicio:

Si {{s,u,v}, {t,w}} es una partición ℘ del conjunto    A={s,  t,  u,  v,  w},  determine  la  relación  de  equivalencia correspondiente R.

Matemáticas Discretas ­Semestre B­2006

5

Clases de Equivalencia
Sea  A  un  conjunto  no  vacío  y  R  una  relación  de  equivalencia sobre A. Para cada elemento de a ∈ A se define la Clase de Equivalencia de a, como el conjunto de todos los elementos que se relacionan  con  a  y se denota por R(a) o [a]. 

R(a) = {b ∈ A | a R b }

Matemáticas Discretas ­Semestre B­2006

6

 Clases de Equivalencia
Ejemplo: Dado A = {1, 2, 3, 4, 5, 6, 7} y sea ℜ= { (1,1),  (1,5), (1,6), (1,7), (2,3), (2,4), (2,6), (3,1), (3,5),  (3,6), (3,7), (4,3), (4,4), (4,6), (5,7), (7,7)}. Determine las clases de equivalencia. R(1) = R(3) = {1, 5, 6, 7}   R(2) = R(4) = {3, 4, 6} R(5) = R(7) = {7}
Matemáticas Discretas ­Semestre B­2006 7

Clases de Equivalencia
Teorema:  Sea ℜ una relación de equivalencia sobre un  conjunto A y sean a, b ∈ A, entonces: 1) [a] = [b] ↔ a ℜ b  2) [a] ≠ [b] →[a] ∩ [b] = ∅

Matemáticas Discretas ­Semestre B­2006

8

Conjunto Cociente
Sea  A  un  conjunto  no  vacío  y  R  una  relación  de  equivalencia sobre  A.  El  conjunto  de  todas  las  clases  de  equivalencia  de  a,  determinadas  en  A  por R se denomina Conjunto Cociente de A por R   y se denota por A/ℜ. 

A/ℜ = { [a] | a ∈ A}
                     

Matemáticas Discretas ­Semestre B­2006

9

Conjunto Cociente
 Ejemplo:

Dado A = {1, 2, 3, 4, 5, 6, 7}  ℜ=  {  (1,1),  (1,5),  (1,6),  (1,7),  (2,3),  (2,4),  (2,6),  (3,1), (3,5),  (3,6),  (3,7),  (4,3),  (4,4),  (4,6),  (5,7),  (7,7)} y las clases de equivalencia R(1) = R(3) = {1, 5, 6,  7}; R(2) = R(4) = {3, 4, 6} y R(5) = R(7) = {7} A/ℜ = {R(1), R(2), R(5)}
Matemáticas Discretas ­Semestre B­2006 10

Manipulación de Relaciones
Ya que las relaciones de A en B son subconjuntos   de  A  x  B,  dos  relaciones  de  A  en  B  se  pueden cambiar o combinar para producir otras relaciones  nuevas. Las principales operaciones incluyen:
 Relación Complementaria  Inversa  Unión   Intersección  Composición
Matemáticas Discretas ­Semestre B­2006 11

Manipulación de Relaciones
 Relación Complementaria

Sea R una relación de un conjunto A a un conjunto B.  _ El complemento de R, se denota R y se define por:  a R b  si y sólo si a ℝ b
 Relación Inversa

_Sea R una relación de un conjunto A a un conjunto B.  La inversa de R, se denota R­1 y se define por: 
Matemáticas Discretas ­Semestre B­2006

b R­1 a  si y sólo si a R b

12

Manipulación de Relaciones
 Unión

Sean R y S relaciones de un conjunto A a un conjunto  B. La unión de R y S, se denota R ∪ S y se define por:  a (R ∪ S) b  si y sólo si a R b o a S b...