Unidad 5

 RELACIONES

Una relación es una correspondencia entre dos elementos de dos conjuntes con ciertas propiedades. En computación las relaciones se utilizan en bases de datos, estructuras de datos, redes, autómatas y lenguajes. Por ejemplo se pueden guardar datos personales de un trabajador: número de control registro federal de causantes, puesto ocupado, antigüedad y salario, entre otros. Para relacionar los datos de este archivo con otra información, se establece el campo relación y las reglas que permitirán la búsqueda y asignación de información.

Elementos de una relación

La definición de relación es la siguiente: 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 esta 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}

Una relación es una tabla que muestra la correspondencia de unos elementos con respecto a otros; por ejemplo la relación entre maestros y las materias que imparte cada uno, cumple con las características de relación por lo que se puede representar de la siguiente manera:

Maestro 

Materia 

Jorge 

Sistemas digitales 

Domingo 

Lenguajes algorítmicos 

Ignacio 

Estructuras de datos 

Jorge 

Graficación 

Raymundo 

Programación II 

Manuel 

Sistemas operativos 

Ezequiel 

Sistemas digitales 

En este caso se tiene que:

A = {x | x es un maestro}

B = {y | y es una materia de la carrera de ingeniería en sistemas computacionales}

E = {(Jorge, Sistemas digitales), (Jorge, Graficación), (Domingo, Lenguajes algorítmicos), (Ignacio, Estructuras de datos), (Raymundo, Programación II), (Manuel, Sistemas operativos), (Ezequiel, Sistemas digitales)}

Se entiende que el conjunto A está integrado por todos los maestros, aunque no aparezcan en la relación, y que el conjunto B también tiene más materias que las que se consideran en la tabla anterior. 

En términos de relación se dice que Jorge está relacionado con Sistemas digitales y Graficación, y que Ignacio está relacionado con Estructuras de datos.

Las relaciones se forman si se cumple cierta proposición, esa proposición puede ser textual, como en el caso anterior (“Imparten la materia”), pero también puede ser planteada en lenguaje matemático.

Ejemplo Sean los conjuntos

A = {a | a ϵ Z; 10 < a < 30}

B = {b | b ϵ Z+; b < 20}

y sea R una relación de A en B, en donde el elemento a ϵ A es divisible entre 13 y b ϵ B es primo.

Como resultando se obtiene la siguiente relación:

R = {(13, 2), (13, 3), (13, 5), (13, 7), (13, 11), (13, 13), (13, 17), (13, 19), (26, 2), (26, 3), (26, 5), (26, 7), (26, 11), (26, 13), (26, 17), (26,19)}

Hay que observar que las relaciones también se pueden representar como un conjunto de pares ordenados, en donde el elemento a € A está relacionado con el segundo elemento b € B, por medio de cierta condición establecida. En este caso la condición es que el primer elemento de los pares ordenados sea un entero entre 10 y 30, divisible entre 13, y el segundo elemento es un entero positivo primo, menor o igual a 20. Otra forma de representar de este conjunto es:

R = {(a, b) | a ϵ Z, b ϵ Z+; a es divisible entre 13; 10 < a < 30; b es primo; b ≤ 20}

Si los elementos de un conjunto se pueden relacionar, se dice que los conjuntos que integran la relación están ordenados y a la relación se le llama “relación de orden” en el conjunto.

5.1.1 PRODUCTO CARTESIANO

El producto cartesiano de los conjuntos A y B, que se denota como A x B. es la combinación de todos los elementos del conjunto A con todos los elementos del conjunto B. En teoría de conjuntos equivale al conjunto universo.

Una relación R de A en B (R: A —> B) es un subconjunto del producto cartesiano A x B. Si R c A x B y (a, b) ϵ R, entonces a su vez el producto cartesiano también es una relación.

Ejemplo: Sean los conjuntos

A = {1, 2, 3} y B = {a, b}

El producto cartesiano 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, como se muestra en la siguiente figura:

A B

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

5.1.2 Relación binaria

En matematicas, una relación binaria es una relacion matematica R entre los elementos de dos conjuntos A y B. Una relación de este tipo se puede representar mediante pares ordenados.

No siempre los elementos de la relación son pares ordenados, ya que pueden tener más de dos elementos como en el siguiente caso:

R = {(a, 1, Δ), (a, 2, □), (b, 1, Δ), (c, 3, □), (c, 2, Δ)}

Aquí la relación está formada por tercias de elementos pertenecientes a los conjuntos A = {a, b, c}, B = (1, 2, 3} y C = {□, Δ}. En este caso se trata de una relación terciaria y no binaria, ya que los elementos no son pares ordenados sino tercias.

En toda relación de pares ordenados no vacía se tienen dos conjuntos: el dominio de R (Dom(R)), que es el conjunto de todos los primeros elementes de los pares de una relación el cual es un subconjunto del conjunto A (Dom(R) c A), y el codominio de R (Cod(R)), conjunto que está formado por los segundos elementos de los pares de la relación R y que también es un subconjunto de B (Cod(R) cB).

Ejemplo Sean los conjuntos

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

A = {2, 4, 5, 6, 7, 11} y B = {b | b ϵ Z; 1 ≤ b ≤ 10}

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}

5.1.3 REPRESENTACIÓN DE RELACIONES MATRIZES CONJUNTO, GRAFOS DIAGRAMAS DE FLECHAS

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] cuyos elementos se definen como:

1 si (a, b) ϵ R

0 si (a, b) ∉ R

Ejemplo 6.4. Sean los conjuntos

A = {1, 2, 3, 4, 5} y B = {1, 2, 3,4, 5, 6, 7}

y 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)}

Esta relación se puede representar en forma de matriz como sigue:

1 2 3 4 5 6 7 

Los elementos del conjunto A se representan como filas y los del conjunto B como columnas. Se coloca un 1 si el par ordenado se encuentra en la relación y un 0 en caso contrario.

La representación matricial es muy importante ya que se presta para llevar a cabo las operaciones entre relaciones, sobre todo cuando se tienen relaciones muy grandes.

Grafo de una relación

Es posible representar una relación por medio de una gráfica integrada por nodos y flechas, y a este tipo de grafica se le conoce como “grafo dirigido” de R. Para hacer un grafo solo se tienen que colocar los elementos de los conjuntos A y B como nodos, y la relación que existe entre los elementos se indica por medio de una flecha que va del elemento del conjunto A al elemento del conjunto B con el que está relacionado.

Los grafos pueden ser de dos tipos: "dirigidos”, en el que los nodos están relacionados por medio de una flecha que indica la relación, o “no dirigidos”, como el siguiente grafo en el que no existe direccionamiento:

Los grafos no dirigidos tienen mucha aplicación tanto en el área de la

Computación como en los sistemas de comunicación, ya que por medio de un grafo no dirigido es posible representar una red carretera, una red telefónica, una red de computadoras, una red de redes y un árbol, entre otros.

En un grafo no dirigido la relación es en ambos sentidos (se considera que las líneas tienen cabezas de flecha en ambos extremos), por lo que no es necesaria la flecha.

Representación De Relaciones Usando Conjuntos 

Un conjunto es una colección de objetos considerada como un objeto en sí. Los objetos de la colección pueden ser cualquier cosa: personas, números, colores, letras, figuras, etc. Cada uno de los objetos en la colección es un elemento o miembro del conjunto. Por ejemplo, el conjunto de los colores del arcoíris es:

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}

Un conjunto suele definirse mediante una propiedad que todos sus elementos comparten. Por ejemplo, para los números naturales, si consideramos la propiedad de ser un número primo, el conjunto del número primo es:

P = {2, 3, 5, 7, 11, 13,…}

Un conjunto queda definido únicamente por sus miembros y por nada más. En particular el orden en el que se representen estos es irrelevante. Además, cada elemento puede aparecer de manera idéntica una sola vez, esto es, no puede haber elementos totalmente idénticos repetidos. Por ejemplo:

S = {Lunes, Martes, Miércoles, Jueves, Viernes} = {Martes, Viernes, Jueves, Lunes, Miércoles}

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta} = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta, Naranja}

Los conjuntos pueden ser finitos o infinitos. El conjunto de los número naturales es infinito, pero el conjunto de los planetas en el sistema solar es finito (tiene ocho elementos).

Los conjuntos son un concepto básico, en el sentido de que no es posible definir los en términos de nociones más elementales, por lo que su estudio puede realizarse de manera informal, apelando a la intuición y a la lógica. Por otro lado, son el concepto fundamental de la matemática: mediante ellos puede formularse el resto de objetos matemáticos, como los números y las funciones, entre otros. 

Representación De Relaciones Usando Diagramas De Flechas 

Una forma de representar el producto cartesiano es el diagrama de flechas.

Escriba los elementos de a y los elementos de b en dos discos disyuntos, y luego dibuje una flecha de” a e a “ en ” b e b” cada vez que a este relacionado con b.

5.2 PROPIEDADES DE LAS RELACIONES

Relación reflexiva

Una relación es reflexiva cuando todo elemento de un conjunto A esta relacionado consigo mismo, esto es, cuando se cumple que aRa para todo elemento de A. Una característica de este tipo de relación es que su matriz correspondiente contiene unos en toda su diagonal principal y los elementos restantes de la matriz pueden ser unos o ceros, como se muestra en el siguiente ejemplo.

Sean A = B = {1, 2, 3, 4} y

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

Relación irreflexiva

Se dice que 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 reflexiva ni irreflexiva.

En el siguiente ejemplo se tiene la matriz de una relación que solo contiene ceros en su diagonal, por lo tanto esta es una relación irreflexiva ya ningún elemento está relacionado consigo mismo.

Sean A = B = {1, 2, 3, 4} y

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

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) está en la relación pero (b, a) no, entonces la relación no es simétrica.

En el siguiente ejemplo la matriz de esta relación tiene unos o ceros en los pares colocados simétricamente, esto es, si (a, b) ϵ R entonces (b, a) ϵ R. Pero si (a, b) ∉ R entonces (b, a) ∉ R.

La condición de simetría se debe de cumplir para todos los pares colocados simétricamente, y una forma rápida de saber si la relación es simétrica es comparar la matriz de la relación con su transpuesta: si son iguales entonces se concluye que la relación R es simétrica.

Como en el siguiente ejemplo se tiene que MR ≠ MR_1 entonces se concluye que la relación R no es simétrica:

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 de la relación deberá contener solamente ceros.

En relación con los pares simétricos de la siguiente matriz hay que observar que si uno de ellos vale 1, su simétrico debe valer 0. Por otro lado, la diagonal debe tener solamente ceros, lo cual indica que ningún elemento está relacionado consigo mismo.

Los pares colocados simétricamente pueden ser pares de ceros, pero nunca pares de unos.

Relación antisimétrica

Una relación es antisimetrica cuando uno de los pares colocados simétricamente no está en la relación, lo cual significa que (a, b) ∉ R o bien (b, a) ∉ R. En este caso la diagonal de la matriz no es importante, ya que pueden estar o no relacionados los elementos con ellos mismos.

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 (b, a) ∉ R. En la diagonal puede haber ceros o unos, y también puede haber pares de ceros colocados simétricamente y por lo tanto es una relación antisimetrica.

Relación transitiva

Una relación de A en B tiene la propiedad de ser transitiva si cuando aRb y bRc entonces existe el par aRc.

En la matriz de la siguiente relación se tiene (2, 3) y (3, 4), entonces existe (2, 4). También se tiene (3,1) y (1, 3), entonces (3, 3). De esta forma se deben de revisar todos los posibles pares para ver si se cumple la transitividad.

Luego de llevar a cabo la tabulación correspondiente se concluye que la relación anterior no es transitiva, ya que debe tener los pares ordenados encontrados a continuación:

(1. 3), (3, 1) => (1, 1)*

(2, 2), (2, 4) => (2, 4)

(3, 1), (1, 3) => (3. 3)

(4, 3), (3, 1) => (4, 1)*

(1, 3), (3, 3) => (1, 3)

(2, 3), (3, 1) => (2, 1)*

(3, 3), (3, 1) => (3, 1)

(4, 3), (3, 3) => (4, 3)

(1. 3), (3, 4) => (1, 4)*

(2, 3), (3, 3) => (2, 3)

(3, 3), (3, 3) => (3, 3)

(4, 3), (3, 4) => (4, 4)*

(2, 2), (2, 2) => (2, 2)

(2, 3), (3, 4) => (2, 4)

(3, 3), (3, 4) => (3, 4)

(2, 2), (2, 3) => (2, 3)

(2, 4), (4, 3) => (2, 3)

(3, 4), (4, 3) => (3, 3)

Sin embargo, le faltan los 5 elementos marcados con asterisco (*), para que cumpla con la propiedad de transitividad, pero aunque solo le faltara uno esto sería suficiente para que no fuera transitiva. También es común que se obtengan elementos repetidos, por ejemplo (2,4) aparece dos veces, pero en este caso solamente se considera uno de ellos y los demás se descartan.

Propiedad 

Condición 

Reflexiva 

aRa, Ɐ a ϵ A 

Irreflexiva 

(a, a ) ∉ R , Ɐa ϵ A 

Simétrica 

Cuando (a, b) ϵ R entonces (b, a) ϵ R, o bien Cuando (a, b) ∉ R entonces (b, a) ∉ R.

Asimétrica 

Cuando (a, b) ϵ R entonces (b, a) ∉ R. Además si a = b (a, a) ∉ R. 

Antisimetrica 

(a, b) ∉ R o bien (b, a) ∉ R.

La diagonal no es importante en este caso. 

Transitiva 

Si (a, b) ϵ R y (b, c) ϵ R; entonces (a, c) ϵ R.

5.3 RELACIONES DE EQUIVALENCIA CLASES DE EQUIVALENCIA Y PARTICIONES 

Una relación de equivalencia es aquella que tiene las tres propiedades: Reflexiva, simétrica y transitiva. Por otro lado, una relación de equivalencia tiene clases de equivalencia y estas forman particiones. Una partición es un subgrafo completo.

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 indicar como

[a] = {b | b ϵ B, aRb}

Una partición es un conjunto de clases de equivalencia (conjunto de conjuntos) con las siguientes propiedades:

a) Deberán estar contenidos todos los elementos del conjunto A.

b) La intersección entre las clases de equivalencia deberá ser vacía.

Mas formalmente se puede indicar como:

λ = {[a] | a ϵ A, la intersección entre clases de equivalencia es vacía}

Cerradura

En algunas ocasiones una relación no cumple alguna de las propiedades de equivalencia, pero hay relaciones que la incluyen y que si cumplen la propiedad. De todas las relaciones la menor posible se llama Cerradura.

Definición.- Sea R una relación en un conjunto A.

Una cerradura reflexiva ref (R) de R en A es la "menor" relación que la incluye y que es reflexiva, con símbolos: (≤R' reflexiva) (A ≤ R' ≤ ref(R)) ⇒ R' = ref(R))

Una cerradura simétrica sim(R) de R en A es la "menor" relación que la incluye y que es simétrica con símbolos: (∀R' reflexiva) (A ≤ R' ≤ ref(R)) ⇒ R' = sim(R))

Una cerradura transitiva trans (R) de R en A es la "menor" relación que la incluye y que es transitiva, con símbolos: (∀R' reflexiva) (A ≤ R' ≤ ref(R)) ⇒ R' = trans(R))

La cerradura transitiva reflexiva y la cerradura simétrica de una relación es muy simple de encontrar, solamente se le agregan los pares necesarios de una forma directa. Cuando conocemos la matriz asociada a la relación, la forma de encontrar las cerraduras anteriores es muy simple.

Teorema: Sea R una relación en A y MR su matriz asociada. La cerradura reflexiva y la cerradura simétrica de R son únicas y pueden obtener mediante las matrices siguientes Mref(R) MRUIn, donde In es la matriz identidad de orden │A│.

Msim(R) = [aij], donde aji = 1 si aji = 1 en MR 

La matriz identidad de orden n es: 

Ósea que para lograr la cerradura reflexiva debemos agregar 1's en la diagonal, para la cerradura simétrica debemos agregar 1's en lugares simétricos a la diagonal principal donde existan.

Clases de Equivalencia

Sea R una relación de equivalencia sobre un conjunto A. Para cada a ∈ A, llamaremos clase de equivalencia de a, al conjunto formado por todos los elementos de A que estén relacionados con él. La notaremos [a], es decir, [a] = {x ∈ A: xRa}

Obsérvese que la clase de equivalencia de un elemento a nunca es vacía, ya que la reflexividad de R implica que a ∈ [a].

Al conjunto de los elementos del conjunto A que están relacionados con él se llama clase de equivalencia. 

Particiones

Sea X un conjunto. P es una partición de X si y sólo si: ø ∉ P UP = A

Los conjuntos de P son disyuntos 2 a 2, es decir, si s1, s2 ∈ P y s1 ≠ s2 entonces s1 ∩ s2 = ø

Observe que si P es una partición de X, entonces todo elemento de X está en uno y sólo un elemento S ∈ P no y sólo un elemento e modo que parte a en conjuntos disyuntos. Por ejemplo, el conjunto de barriles propuesto al comienzo de la sección es una partición del conjunto de mangos. Otro ejemplo de una partición es de la división política de un país: El país (visto como un conjunto de personas) se parte en estados o departamentos no vacíos disyuntos entre sí.

5.4 FUNCIONES INYECTIVA, SUPRAYECTIVA, BIYECTIVA

Una función f: A àB se llama uno a uno (o inyectiva) si a cada elemente distinto del conjunto A le corresponde un elemento distinto del conjunto B, esto es, para todo a, a' ∈ A si f(a) = f(a') implica que a = a'.

Una función f: A àB se llama sobre (o suprayectiva) si el conjunto de los segundos elementos de los pares ordenados de la función es igual al conjunto B, dicho de otra forma, es sobre si Cod (f) = B.

Cuando una función es uno a uno y sobre (o biyectiva), se dice que f tiene una correspondencia uno a uno.

Ejemplo. En la siguiente figura se ilustran los conceptos de función inyectiva, suprayectiva y biyectiva.

Considérese que los puntos de la izquierda son los elementos del conjunto A, que los puntos de la derecha son los elementos del conjunto B, y que la relación entre ambos conjuntos es la indicada por las flechas.

En esta figura hay que observar que todos los elementos del conjunto A están relacionados en todos los casos que se muestran, independientemente del tipo de función de que se trate; si no fuera de esta manera no se trataría de funciones ya que no se estaría cumpliendo la primera condición de la definición de funciones.

5.5 APLICACIONES DE LAS RELACIONES Y LAS FUNCIONES EN LA COMPUTACIÓN

Las relaciones tienen muchas aplicaciones y en particular las que se presentan a continuación en el área de la computación.

Una lista enlazada es una relación

Sea A un vector de dimensión N que contiene nombres de personas, los cuales fueron colocados de acuerdo con el orden en que llegan, y sea P otro vector de las mismas dimensiones para guardar la dirección del siguiente nombre. Además se considera una variable X que guarda la posición en donde inicia la tabla de nombres.

a) Si el orden en que llegan los nombres es “María”, “Juan”, “Ana’

“Pedro”, "Jaime”, ¿cuál es el valor de la variable X y como quedarían los vectores A y P?

Solución de (a)

Considérese que la variable que indica el inicio de la lista es X = * y que los arreglos A y P están vacíos, como se muestra en la siguiente tabla:

Al llegar el primer nombre los arreglos quedan de la siguiente manera:

La variable X = 1 indica que el primer nombre de la lista está en la posición del arreglo A. El * en P indica que ya no hay más nombres y ahí termina la lista.

Cuando llega el segundo nombre los arreglos tienen la siguiente información:

Como el nombre de Juan se coloca alfabéticamente antes que María, ahora la variable que indica el inicio de la lista apunta a la posición de ese nombre X = 2. En esa misma posición pero para el arreglo P, se coloca el número 1 que indica que la posición del siguiente nombre a recorrer está en la posición número'1 del arreglo A y el * en P significa que ahí termina la lista.

Al agregar los nombres de Ana, Pedro y Jaime, los arreglos quedan como se muestra a continuación:

Hay que observar que al colocar la información de esta forma es posible recorrerla en orden alfabético, permitiendo con ello un acceso más rápido.

Aplicación de las funciones

Cada uno de los lenguajes conocidos como Java, C++, Pascal y Basic, tienen funciones integradas al lenguaje como sin(x), abs(x), sqrt(x), mod(x, y) y pziN x), entre otras. Además, en cada uno de los lenguajes es posible crear funciones con características especiales que las funciones estándar no tienen, pero que se consideran necesarias ya sea porque se usan con mucha frecuencia, porque permiten dar claridad al código o porque hacen compactos los programas. Por ejemplo, si las funciones y = x3- 1, potencia = ab se usan frecuentemente en un programa, se pueden crear de la siguiente manera:

Función y(x: real): real Función potencia (a, b: entero): entero 

Inicio Inicio

y: = xA3 – 1 potencia: = a^b

retornar y retornar potencia

Fin fin

Una vez creadas las funciones, simplemente se les pasa el valor o valores por medio de los parámetros que están entre paréntesis y de esa manera se obtiene el resultado. Por ejemplo: 

Imprimir y (2) El resultado que imprime es 7(23 - 1)

r: = potencia (2, 3) El resultado obtenido es r = 8(23)

Algunos lenguajes usan la palabra “Función” y otros no, pero a todas las funciones se les da un nombre (en los casos anteriores es y y potencia), ya que el nombre de la función actúa como variable en la cual se almacena el resultado de la función.