Estructuras Discretas

UNIVERSIDAD CENTROOCIDENTAL ’LISANDRO ALVARADO’ DECANATO DE CIENCIAS Y TECNOLOG´ IA ´ DEPARTAMENTO DE MATEMATICAS

ESTRUCTURAS DISCRETAS

Por: Ronald Guti´rrez e

CAP´ ITULO 3: RELACIONES Comenzaremos con la definici´n formal de relaci´n, as´ como los concepo o ı tos de dominio, rango y relaci´n inversa, pasaremos luego al estudio de las o relaciones compuestas y las relaciones en unconjunto

0.1.

Relaciones binarias

Definici´n 0.1.1 Sean X, Y conjuntos. Una relaci´n de X en Y es un o o subconjunto R del producto cartesiano XxY . El conjunto X en este caso se llama conjunto de partida de la relaci´n R y al conjunto Y se le llama o conjunto de llegada de la relaci´n R o Ejemplo 0.1.1 Si X = {1, 2, 3} y Y = {1, 3, a, 4}. Entonces XxY = {(1, 1), (1, 3), (1, a), (1, 4), (2, 1),(2, 3), (2, a), (2, 4), (3, 4), (3, 3), (3, a), (3, 4)} Por lo tanto 1. ∅ 2. XxY 3. R = {(1, 1), (1, 4), (2, 1)} 4. S = {(1, 1), (1, 3), (2, a), (3, 4)} son relaciones de X en Y Notemos por otro lado que Y xX = {(1, 1), (1, 2), (1, 3), (3, 1), (3, 2), (3, 3), (a, 1), (a, 2), (a, 3), (4, 1), (4, 2), (4, 3)} as´ que {(1, 1), (a, 1), (4, 1)} (por ejemplo) es una relaci´n de Y en X, pero ı o no unarelaci´n de X en Y (casualmente {(1, 1), (1, 3)} es relaci´n de Y en o o X y de X en Y ) Observaci´n 0.1.1 Sea R una relaci´n de X en Y : o o 1. Si X = Y , en lugar de decir que R es una relaci´n de X en X, diremos o que R es una relaci´n en X o 2

2. Si (x, y) ∈ R, escribiremos a menudo xRy, que se lee ’x esta relacionado con y, seg´n la relaci´n R’ u o Definici´n 0.1.2 Sea R una relaci´n de X enY . Definimos como: o o 1. dominio de R, denotado por dom(R), al conjunto dado por dom(R) = {x ∈ X/xRy, para alg´n y ∈ Y } u 2. rango de R, denotado por rang(R), al conjunto dado por dom(R) = {y ∈ Y /xRy, para alg´n x ∈ X} u En otras palabras en el dominio (rango) de una relaci´n R, esta foro mado por todos aquellos puntos del conjunto de partida (llegada) que aparecen en la primera (segunda)componente de los elementos de la relaci´n R o 3. relaci´n inversa de R, denotado por R−1 , a la relaci´n de Y en X o o dada por R−1 = {(y, x) ∈ Y xX/xRy, } Ejemplo 0.1.2 Consideremos las relaciones R = {(1, 1), (1, 4), (2, 1)} y S = {(1, 1), (1, 3), (2, a), (3, 4)} del ejemplo anterior. Entonces 1. dom(R) = {1, 2}, dom(S) = {1, 2, 3} 2. rang(R) = {1, 4}, rang(S) = {1, 3, a, 4} 3. R−1 = {(1, 1), (4,1), (1, 2)}, S −1 = {(1, 1), (3, 1), (a, 2), (4, 3)} Teorema 0.1.1 Sea R una relaci´n de X en Y . Entonces o 1. dom(R) = rang(R−1 ) 2. dom(R−1 ) = rang(R) 3. (R−1 )−1 = R ´ ´ REPRESENTACION GRAFICA DE RELACIONES Veremos tres formas de representar g´ficamente una relaci´n a o

3

´ 1. REPRESENTACION CARTESIANA Para obtener una representaci´n cartesiana de una relaci´n se dibuja o o un planotomando como abscisas los elementos del conjunto de partida y como ordenadas el conjunto de llegada. En el plano obtenido se marcan los pares ordenados que conforma la relaci´n o Generalmente este tipo de representaci´n es muy util cuando los cono junto de partida y llagada son subconjuntos de R Ejemplo 0.1.3 Si X = {1, 2, 3}, Y = {−1, 0, a, b}, y R es la relaci´n o de X en Y dada por R = {(1, −1),(1, a), (3, 0), (3, a)} Entonces la representaci´n cartesiana de R viene dada por o

4

´ 2. REPRESENTACION MATRICIAL La representaci´n matricial se usa cuando los conjuntos de partida y de o llegada son finitos y con pocos elementos. Se asigna a cada elemento del conjunto de partida una fila y a cada elemento del conjunto de llegada una columna. Si (x, y) est´ en la relaci´n R, en laintersecci´n de la fila a o o que corresponda a x con la columna que corresponda a y, escribiremos 1; en caso contrario escribiremos 0. A la matriz resultante se le llama matriz de la relaci´n R, denotada por MR o Ejemplo 0.1.4 Si X = {1, 2, 3}, Y = {−1, 0, a, b}, y R es una relaci´n o de X en Y dada por R = {(1, −1), (1, a), (3, 0), (3, b), (3, a)} Entonces MR viene dada por  1 0 1 0 MR =  0 0 0 0  0 1...