Tema 4 Relaciones

Conoce y aplica las operaciones y propiedades de los conjuntos y relaciones para la resolución de problemas reales.
�

1. Tema: Relaciones
• Una relación es una
correspondencia entre dos
elementos de dos conjuntos
con ciertas propiedades.

2. Aplicación de las relaciones
Relaciones
Bases de
datos
Estructura
de datos
Redes
Autómatas
y
lenguajes

3. Definición de Relación “R”
• Dados dos conjuntos no vacíos A y B, una relación R es un
conjunto de pares ordenados en donde el primer elemento “a”
está relacionado con el segundo elemento “b” por medio de
cierta propiedad o característica.
• La relación se indica como aRb:
R= {(a,b) | a ∈ A y b ∈ B}

4. Producto Cartesiano
• El producto cartesiano de los conjuntos A y B, que se denota con
A x B es la combinación de todos los elementos del conjunto A
con todos los elementos del conjunto B.
• Ejemplo:
– Sean los conjuntos:
• A = {1, 2, 3}
• B = {a, b}

5. Producto cartesiano (Cont.)
• El producto cartesiano de A x B contiene todos los pares ordenados que resultan de relacionar todos los elementos del
conjunto A con todos los elementos del conjunto B.
A B






A x B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}
1

2

3
a

b

6. Relación binaria
• Se llama relación binaria porque sus elementos porque sus
elementos son pares ordenados que se forman a partir de
dos conjuntos.
• Es una de las relaciones más importantes en la computación
ya que se representan por medio de una matriz, tabla o
gráfica.

7. Relación Binaria (cont.)
• En toda relación de pares ordenados no vacía se tienen dos
conjuntos:
– El dominio de R (Dom (R)): es el conjuntos de todos los primeros
elementos de los pares de una relación.
– El codomino de R (Cod (R)): es el conjunto que está formado por los
segundos elementos de los pares de la relación R.

8. Ejemplo
• Sean los conjuntos:
– A = {2, 4, 5, 6, 7, 11}
– B = {b | b ∈ Z; 1< b < 10 } B={1,2,3,4,5,6,7,8,9,10}

Considérese que aRb si y sólo si b es divisible entre a. Por lo tanto los elementos de la relación son:

R = {(2,2), (2,4), (2,6), (2,8), (2,10), (4,4), (4,8), (5,5), (5,10), (6,6), (7,7)}

Dom(R) = { 2, 4, 5, 6, 7}
Cod(R) = {2, 4, 5, 6, 7, 8, 10}

9. Matriz de una relación
• Si A y B son dos conjuntos finitos con m y n elementos, respectivamente y R es
una relación de A en B, entonces es posible representar a R como una matriz MR
=[mij] cuyo elementos se definen como:
1 si (a, b) ∈ R
mij =
0 si (a, b) ∈ R

10. Ejemplo
• A = {1 , 2, 3, 4, 5}
• B = { 1, 2, 3, 4, 5, 6, 7}
• Sea la relación R=AàB tal que:
R = {(1,2), (1,3) (2,2), (2,5), (3,2), (3,7), (4,2), (4,5), (5,6)}

Los elementos del conjunto A representan las filas.
Los elementos del conjunto B representan las columnas.
Filas
Columnas

11. Ejemplo (Cont.)
R = {(1,2), (1,3) (2,2), (2,5), (3,2), (3,7), (4,2), (4,5), (5,6)}


1 2 3 4 5 6 7
1 0 1 1 0 0 0 0
2 0 1 0 0 1 0 0
3 0 1 0 0 0 0 1
4 0 1 0 0 1 0 0
5 0 0 0 0 0 1 0
MR =
Elementos
Conjunto
B
Elementos
Conjunto
A
Relación

12. Propiedades de la Relaciones
Propiedades
Reflexiva
Irreflexiva
Simétrica Asimétrica
Antisimétrica

13. Relación Reflexiva
• Una relación es reflexiva cuando todo elemento de un
conjunto A está relacionado consigo mismo, esto es, cuando
se cumple que aRa para todo elemento de A.
Sean A=B={1, 2, 3, 4} y

R= {(1,1), (1,3), (2,2), (3,2), (3,3), (4,3), (4,4)}

14. Relación Reflexiva :: Ejemplo
R= {(1,1), (1,3), (2,2), (3,2), (3,3), (4,3), (4,4)}


1 2 3 4
1 1 0 1 0
2 0 1 0 0
3 0 1 1 0
4 0 0 1 1
MR =

15. Relación irreflexiva
• Una relación es irreflexiva cuando ningún elemento del conjunto A esta
relacionado consigo mismo ((a, a) ∈ R). En este caso la matriz de la relación
deberá contener únicamente ceros en la diagonal. Si la diagonal de la matriz
tiene ceros y unos, la relación correspondiente no es ni reflexiva ni irreflexiva.
Sean A=B={1, 2, 3, 4} y

R= {(1,3), (1, 4), (2,4), (3,2), (4,3)}

16. Relación Irreflexiva :: Ejemplo
R= {(1,3), (1, 4), (2,4), (3,2), (4,3)}


1 2 3 4
1 0 0 1 1
2 0 0 0 1
3 0 1 0 0
4 0 0 1 0
MR =

17. Relación Simétrica
• Se dice que una relación R: AàB es simétrica cuando (a,
b) ∈ R y (b, a) ∈ R. Si (a, b) esta en la relación pero (b, a)
no, entonces la relación no es simétrica.
Sean A=B={1, 2, 3, 4} y

R= {(1,1), (1,2), (1,4), (2,1), (2,3), (2,4), (3,2), (3,4), (4,1) (4,2) (4,3)}

18. Relación simétrica :: Ejemplo
R= {(1,1), (1,2), (1,4), (2,1), (2,3), (2,4), (3,2), (3,4), (4,1) (4,2) (4,3)}


1 2 3 4
1 1 1 0 1
2 1 0 1 1
3 0 1 0 1
4 1 1 1 0
MR =

19. Relación Asimétrica
• Una relación R de A en B es asimétrica si cuando (a, b) ∈
R entonces (b, a) ∈ R, además de que ningún elemento
deberá estar relacionado consigo mismo; esto significa que la
diagonal de la matriz deberá contener solamente ceros.

20. Relación Asimétrica :: Ejemplo
R= {(2,1), (3,2), (4,1) (4,2) (4,3)}


1 2 3 4
1 0 0 0 0
2 1 0 0 0
3 0 1 0 0
4 1 1 1 0
MR =

21. Relación Antisimétrica
• Es relación es antisimétrica cuando uno de los pares
colocados simétricamente no están en la relación, lo cual
significa que (a, b) ∈ R o bien que (b, a) ∈ R. En este caso
la diagonal del a matriz no es importante, ya que pueden
estar o no relacionados los elementos con ellos mismos.

22. Relación Antisimétrica (Cont.)
• En la matriz de la relación siguiente, cuando menos uno de
los pares simétricos de la relación es 0, lo cual significa que
(a, b) R o bien que (b, a) a R. En la diagonal debe haber
ceros y unos, también puede haber pares de ceros colocados
simétricamente y por lo tanto es una relación antisimétrica.

23. Relación Antisimétrica :: Ejemplo
R= {(1, 3), (2,2), (2, 3), (2,4), (4,3)}


1 2 3 4
1 0 0 1 0
2 0 1 1 1
3 0 0 0 0
4 0 0 1 0
MR =

24. Relaciones de Equivalencia
• Una relación de equivalencia es aquella que tiene las tres
propiedades: reflexiva, simétrica y transitiva.
• Las clases de equivalencia son conjuntos que contienen a todos
los elementos b ∈ B y que están relacionados con a ∈ A. Los
elementos del primer conjunto se encierran entre corchetes, de
forma que una clase de equivalencia se puede representar como:
[a] = { b | b ∈ B, aRb}

25. J Extra Help J
1. ¿Las relaciones se pueden representar a través de grafos? Si/No ¿Por qué?
2. Si tengo una relación con el conjunto A = {1, 2, 3, 4, 5,} y el conjunto B = {a, b,
c}, ¿podría representar la relación A à B a través de una matriz para poder
determinar que tipo de relación es? Si/No ¿Por qué?

Valor por pregunta: 2 puntos

26. Bibliografía
1. Jiménez, J. (2008). “Matemáticas para la computación”.
(2da. Ed.). México: Alfaomega.
2. Johnsonbaugh, R. (2005). “Matemáticas Discretas”. (6ta.
Ed.). México: Pearson Educación. Rosen, H. (2004).
3. “Matemática Discreta y sus aplicaciones". (5ta. Ed.). Edición.
España: McGrawHill.
4. Universidad Autónoma de México.( 2006) Matemáticas IV
(Matemáticas Discretas). México.
Disponible desde Internet en: http://fcaenlinea.unam.mx/
apuntes/interiores/docs/98/6/mate_4.pdfn [Con acceso el 4
de enero de 2010].