TCOM 500 M7 Flip Book

Módulo 7: Relaciones

Contenido 7.1 Par Ordenado y el Producto Cartesiano Un par ordenado es un conjunto de dos elementos donde cada uno de los elementos ocupa una posición fija. El primero ocupa la posición de x y el segundo ocupa la posición de y. Este par ordenado se denota por (x, y). Hay que recordar que (x, y) ≠ (y, x). 7.1.1 Propiedades del Par Ordenado Veamos las propiedades del par ordenado: (x, y) = (y, x) x = y (x, y) = (m, n) x = m ˄ y = n Ejemplo: Identidades que son verdaderas • (2, n) = (2, m) m = n • (m, 2) = (3, n) m = 3 y n = 2 • (x + 4, 7) = (2x – 1, 3y + 4) x = 5 e y = 1 • (2 – m, 5 – n) = (n + 2, m + 5) m es igual al inverso aditivo de n 7.1.2 Concepto Producto Cartesiano Sean A y B conjuntos diferentes del vacío; el producto cartesiano de A y B (AxB) es el conjunto formado por todas las parejas ordenadas. AxB = {(x, y) /x ∈ ������ ˄ ������ ∈ ������} En general AxB ≠ BxA 7.1.3 Propiedades del Producto Cartesiano Veamos las tres propiedades del Producto Cartesiano con algunos ejemplos. • AxB = BxA A = B • (x, y) ∉ AxB x ∉ A ˅ y ∉ B • A ≠ B y AxB ≠ Ø → AxB ≠ BxA Ejemplo: A = {2, 3, 5} y B = {2, 4}; determinar AxB y BxA Solución:

AxB = {(2, 2), (2, 4), (3, 2), (3, 4), (5, 2), (5, 4)} BxA = {(2, 2), (2, 3), (2, 5), (4, 2), (4, 3), (4, 5)} 7.1.4 Representación Gráfica del Producto Cartesiano Existen varias formas de representar los pares ordenados y producto cartesiano. En primer lugar, tenemos uno de los más conocidos, el plano cartesiano. Este está compuesto por dos líneas, una horizontal y la otra vertical. Por lo general la línea horizontal es el eje de x y la vertical el eje de y. Este forma cuatro regiones conocidas como cuadrantes y se utiliza para representar geométricamente el conjunto RxR. This Photo by Unknown Author is licensed under CC BY-SA-NC Ejemplo: Dado los conjuntos A = {1, 2, 3, 5} y B = {1, 2}; determine AxB y represente en el plano cartesiano. Solución: AxB = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (5, 1), (5, 2)} Su representación geométrica:

La segunda forma de representar el producto cartesiano y sus relaciones lo son los diagramas sagitales. Este consiste en figuras geométricas cerradas que se denominan diagramas de Euler-Venn, donde cada elemento se une con flechas. Ejemplo: Represente AxB utilizando diagramas sagitales. A = {1, 4} y B = {2, 3, 5}. 7.2 Relaciones de Conjuntos Sean A y B conjuntos finitos y si R es un subconjunto del producto cartesiano (AxB) de tal forma que los elementos en x de A cumplen la propiedad respecto a los elementos en y de B, se dice que R es una relación que se define A en B. Por lo tanto, R: A→B al que xRy o (x, y)∈R. De igual forma podemos decir que x de A esta relacionado con y de B. Ejemplo: A = {1, 2, 3, 4}, B = {2, 3, 4} y R: A→B; determine R Solución: R = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} 7.2.1 Relación Binaria Dado cualquier par de elementos de un conjunto que cumplen o no una propiedad determinada se dice que se establece una relación binaria. La relación R es definida en A: R ⸦ AxA, R: A→A A esta relación le podemos llamar “relación binaria en A”. Este tipo de relación es de gran importancia en aplicaciones de computadoras y matemáticas aplicadas. Ejemplo: A = {1, 2, 3, 4} y las relaciones: R1: menor o igual que en A R2: múltiplo en A R3: ser cuadrado de en A

R1, R2 y R3 son subconjuntos de AxB, determine cada relación y calcule la unión, la intersección y el complemento de R1 y R2; además la diferencia y la diferencia simétrica entre R2 y R3. Solución: AxB = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)} R1 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} R2 = {(1, 1), (2, 1), (3, 1), (4, 1), (4, 2)} R3 = {(1, 1), (4, 2)} R1 ∪ R2 = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4), (2, 1), (3, 1), (4, 1), (4, 2)} R1 ∩ R2 = {(1, 1)} R’1 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} R’2 = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 3), (4, 4)} R2 ⨁ R3 = {(1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)} R2 – R3 = {(2, 1), (3, 1), (4, 1)} R3 – R2 = {} 7.2.2 Representación Gráfica Relaciones Binarias En el ámbito tecnológico hacemos la representación gráfica mediante dígrafos. Los dígrafos representan las relaciones de manera gráfica y son muy semejantes a los diagramas sagitales; sin embargo, se diferencian, en que los dígrafos se usan para representar relaciones binarias definidas en un solo conjunto y los elementos van unidos con flechas. Para dibujar un dígrafo escriba el elemento correspondiente al conjunto, los cuales se llaman vértices o nodos. Trace una flecha de un vértice a otro, a la que se denomina arco. Cuando un elemento relacionado con otro elemento del conjunto, este se dirige mediante una flecha que va hacia el mismo elemento, lo cual se llama lazo o bucle. Ejemplo:

R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 1)} R2 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} Represente mediante dígrafos las relaciones R1 y R2 Solución: Dígrafo R1 dígrafo R2 7.2.3 Conjuntos Dominio de una Relación Sean A y B conjuntos cualesquiera y R una relación definida de A en B; el dominio de una relación R, es el conjunto formado por todas las x o todos los primeros elementos. D(R) = {x|xRy} Ejemplo: A = {1, 2, 4, 7} y B = {1, 2, 4, 16}; la relación está definida por R: A→B, raíz cuadrada. Determine el D(R) Solución: R = {(1, 1), (2, 4), (4, 16)} D(R) = {1, 2, 4} 7.2.4 Conjunto Imágenes de Relación Sean A y B conjuntos cualesquiera y R una relación definida de A en B; la imagen de una relación R, es el conjunto formado por todas las y o todos los segundos elementos. Im(R) = {y|xRy} Ejemplo: A = {1, 2, 4, 7} y B = {1, 2, 4, 16}; la relación está definida por R: A→B. Determine el Im(R) Solución: R = {(1, 1), (2, 4), (4, 16)}

Im(R) = {1, 4, 16} 7.2.5 Matrix Relacional Es un tipo de matriz dispersa que se utiliza para representar relaciones binarias. Dados dos conjuntos finitos A = {a1, a2, a3, …, an-1, am} de m elementos y B = {b1, b2, b3, …, bn-1, bn} de n elementos; sea R una relación de A en B. La relacion R se puede representar en una matriz de m*n elementos que se denomina “matriz racional” que se abreviara MR y se define por: MR = [mij], con mij = {01,,������������������������ (������, ������) ∈ ������ (������, ������) ∉ ������ Ejemplo: A = {2, 4, 5, 6, 7} B = {2, 3, 4, 5, 6} R→A = {(2, 2), (2,4), (2, 6), (4, 4), (5, 5), (6, 6)} Solución: Esto representa una matriz 5 x 5 así que construimos una así: 10101 00100 00010 00001 [0 0 0 0 0] Donde veamos que hubo la relación colocamos un 1 y el resto de los espacios un 0. (2, 2): representa (a1, b1); donde a son las filas y b las columnas. Por tal razón, se coloca uno en el primer espacio. (2, 4): representa la primera fila tercera columna, colocamos un uno. ⋮ Así sucesivamente con cada par ordenado de R. 7.3 Propiedades de las Relaciones Las relaciones cumplen con ciertas propiedades como he visto en otros temas a lo largo del curso. Estas propiedades están directamente ligadas al desarrollo de aplicaciones computacionales y matemáticas aplicadas. Sea A un conjunto finito cualquiera y R: A→A una relación, entonces se tienen las siguientes propiedades.

7.3.1 Relación Reflexiva Una relación R definida en A es reflexiva si todos los elementos de A están relacionados consigo mismo. En otras palabras, si todos los elementos de A forman parejas ordenadas en R con componentes iguales. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (4, 4), (5, 5), (6, 6), (7, 7)} Solución: La mayoría de estas propiedades que vamos a ver se resuelven usando la matriz relacional. Construyamos la matriz 5 x 5 y si nos queda una diagonal se cumple la propiedad. (2, 2): representa a1, b1 (4, 4): representa a2, b2 (5, 5): representa a3, b3 (6, 6): representa a4, b4 (7, 7): representa a5, b5 10000 01000 00100 00010 [0 0 0 0 1] Así que vemos que se formó una diagonal y por lo tanto cumple. 7.3.2 Relación anti-reflexiva Una relación R definida en A es anti-reflexiva si ninguno de los elementos de A está relacionados consigo mismo. En otras palabras, no hay elementos de A formando parejas ordenadas en R con componentes iguales. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(4, 5), (2, 4), (5, 2), (6, 7), (7, 6)} Solución: Podemos observar que no hay una relación entre los elementos; pero lo vamos a comprobar si al hacer la matriz no queda un 1 en la diagonal. Podemos ubicar cada par ordenado colocando los elementos arriba de cada columna y al lado de cada fila y trazar donde conectan. 24 5 6 7

01000 2 00100 4 10000 5 00001 6 [0 0 0 1 0] 7 Así que vemos que no se formó una diagonal y por lo tanto cumple. 7.3.3 Relación no Reflexiva Una relación R definida en A es no reflexiva si algunos de los elementos de A no están relacionados consigo mismo. En otras palabras, no todos los elementos de A forman parejas ordenadas en R con componentes iguales. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (4, 4), (5, 6), (6, 5), (7, 7)} Solución: Podemos observar que hay una relación entre algunos elementos; pero lo vamos a comprobar si al hacer la matriz solo quedan algunos 1 en la diagonal. 24 5 6 7 10000 2 01000 4 00010 5 00100 6 [0 0 0 0 1] 7 Así que vemos que la diagonal no se formó por completo y por lo tanto cumple. 7.3.4 Relación Simétrica Una relación R definida en A es simétrica cuando todas las parejas de la relación tienen su recíproco. En otras palabras, los elementos x, y de A se cumple si xRy, entonces yRx. Ejemplo:

A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (6, 4), (5, 6), (6, 5), (4, 6)} Solución: Podemos observar que todas las parejas de R tienen su reciproco. 24 5 6 7 10000 2 00010 4 00010 5 01100 6 [0 0 0 0 0] 7 Si doblamos la matriz por la diagonal principal los 1 van a coincidir. 7.3.5 Relación Antisimétrica Una relación R definida en A es antisimétrica cuando ninguna pareja de la relación tiene su recíproco. En otras palabras, los elementos x, y de A se cumple si (x, y) ∈R entonces (y, x)∉R; pero si (x, y) ∈R y (y, x) ∈R, entonces x = y. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (6, 4), (5, 6), (6, 2), (4, 5), (7, 7)} Solución: Podemos observar que ninguna pareja de R tienen su reciproco. 10000 00100 00010 11000 [0 0 0 0 1] Si doblamos la matriz por la diagonal principal ningún 1 va a coincidir. 7.3.6 Relación no Simétrica Una relación R definida en A es no simétrica cuando algunas parejas de la relación son simétricas o tienen su recíproco y otras no la tienen. En otras palabras, no todas las parejas de R cumplen si (x, y) ∈R entonces (y, x)∉R. Ejemplo:

A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (5, 4), (5, 6), (6, 5), (7, 7)} Solución: Podemos observar que algunas parejas de R tienen su reciproco. 10000 00000 01010 00100 [0 0 0 0 1] 7.3.7 Relación Transitiva Una relación R definida en A es transitiva cuando un elemento este relacionado siempre con un segundo y este con un tercero, entonces el primero este relacionado con el tercero. En otras palabras, siempre que x, y, z sean elementos de A, se cumple si (x, y) ∈R y (y, z)∈R, entonces (x, z) ∈R. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (4, 4), (5, 4), (5, 6), (6, 5), (4, 5), (4, 6), (5, 5), (7, 7), (6, 6)} Solución: Veamos la matriz que corrobora que es transitiva. 10000 01110 01110 00110 [0 0 0 0 1] 7.3.8 Relación no Transitiva Una relación R definida en A es no transitiva cuando un elemento esté relacionado con un segundo y este con un tercero, pero el primero no está relacionado con el tercero. En otras palabras, hay elementos x, y, z de A, que cumplen algunas si (x, y) ∈R y (y, z)∈R, entonces (x, z) ∉ R. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (4, 4), (5, 4), (5, 6), (6, 5), (4, 5), (4, 6)}

Solución: Veamos la matriz que comprueba que el tercer elemento no está relacionado. 10000 01100 01010 01100 [0 0 0 0 0] 7.3.9 Relación de Equivalencia Una relación R definida en A es de equivalencia si es reflexiva, simétrica y transitiva. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (4, 4), (5, 5), (6, 6), (7, 7), (2, 4), (4, 2), (2, 5), (5, 2), (2, 6), (6, 2), (2, 7), (7, 2), (4, 5), (5, 4), (5, 6), (6, 5), (6, 7), (7, 6), (4, 6), (4, 7), (6, 4), (7, 4), (5, 7), (7, 5)} Solución: Veamos que la matriz todos son 1, por lo tanto, se cumplen las condiciones. 11111 11111 11111 11111 [1 1 1 1 1] 7.3.10 Relación de Orden Estricto Una relación R definida en A es de orden estricto si R es antisimétrica y transitiva. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 4), (2, 5), (2, 6), (2, 7), (4, 5), (5, 6), (6, 7), (5, 7)} Solución: Verificamos la misma construyendo la matriz y viendo que cumpla ambas condiciones. 00000 10000 11000 10100 [1 0 1 1 0] 7.3.11 Relación de Orden Parcial Una relación R definida en A es de orden parcial si R es reflexiva, antisimétrica y transitiva, pero no hay relación entre algunos elementos de A. Ejemplo: A = {2, 4, 5, 6, 7}

R: A→A = R = {(2, 2), (4, 4), (5, 5), (6, 6), (7, 7), (2, 4), (2, 5), (2, 6), (4, 5), (5, 6), (6, 7), (4, 6)} Solución: Compruebe la respuesta haciendo la matriz. 10000 11000 11100 11110 [0 0 0 1 1] 7.3.12 Relación de Orden Total Una relación R definida en A es de orden total si R es reflexiva, antisimétrica y transitiva. Ejemplo: A = {2, 4, 5, 6, 7} R: A→A = R = {(2, 2), (4, 4), (5, 5), (6, 6), (7, 7), (2, 4), (2, 5), (2, 6), (2, 7), (4, 5), (5, 6), (6, 7), (4, 6), (4, 7), (5, 7)} Solución: Compruebe la respuesta haciendo la matriz. 10000 11000 11100 11110 [1 1 1 1 1] 7.3.13 Relación Inversa Sea A un conjunto cualquiera y R una relación definida en A por {(x, y)∈AxA/xRy}; entonces, la relación inversa denotada por R-1 se define por el conjunto {(x, y)∈AxA/xRy}. Ejemplo: A = {6, 12, 18, 24} y R una relación definida en A por: R = {(6, 6), (12, 12), (18, 18), (24, 24), (6, 12), (6, 18), (6, 24), (12, 24)} Solución: R-1 = {(6, 6), (12, 12), (18, 18), (24, 24), (12, 6), (18, 6), (24, 6), (24, 12)}