Relaciones

|
Matemáticas Discretas |
Relaciones

5.1 Conceptos Básicos

Las relaciones son muy importantes en matemáticas y sobretodo en computación, pues vienen a ser una herramienta fundamental en Bases de Datos,  Programación,  etc.;   casi en cualquier tópico de una u otra forma se utiliza el concepto de relación. El término relación es muy amplio y se puede conceptualizar en términos muygenerales, pero la idea central es muy simple y entendiendo el concepto se puede aplicar a situaciones muy diversas.

Hay relaciones que involucran elementos simples, otras donde intervienen pares, ternas, cuartetos y en general n-adas o tuplos donde n es un entero positivo.

Una relación binaria es una asociación entre elementos u objetos, generalmente de dos conjuntos arbitrarios. Una manera deformalizar el concepto y al mismo tiempo hacerlo práctico para usarse en computación es considerar una relación como un conjunto de pares ordenados. Esto se puede extender posteriormente a tuplos para definir relaciones de varios elementos.

Un concepto matemático que tiene muchas aplicaciones y que nos ayuda a entender y manejar muchos otros conceptos en computación es el de conjunto.

Lasrelaciones se pueden clasificar de acuerdo al tipo de asociación que hay en sus elementos como: uno-a-uno 1–1, uno-a-mucho 1-M, muchos-a-uno M-1 o muchos-a-muchos M-M.

M-1 Muchos-a-uno. Una relación R de A a B es: Muchos-a-uno, M-1 si existen dos pares con el mismo segundo elemento, esto es existen (x,y), (z,y) distintas en la relación.

(xA)(yB)(zA)((x,y) R (z,y) R x z)

1-MUno-a-muchos. Si existen dos pares con el mismo primer elemento distintos en la relación.

(xA)(yB)(zB)((x,y) R (x,z) R y z)

M-M Muchos-a-muchos. Si es muchos-a-uno y uno-a-muchos. O sea que hay al menos dos pares con el mismo primer elemento y también hay dos pares con el mismo segundo elemento. O sea que cumple las dos definiciones anteriores.

1–1 Uno-a-uno. Si no es muchos-a-uno niuno-a-muchos, o sea que no hay dos pares con el mismo primer elemento y no hay dos pares con el mismo segundo elemento. Esto significa que cumple las dos condiciones siguientes

(xA)( yB) (zB)((x,y)R (x,z) ; R y = z)
(xA)( yB) (zB)((x,y)R (z,y) ; R x = z)

5.1.1 Producto cartesiano

A diferencia de un conjunto en un par ordenado (a,b), importa el orden de los elementos. Si seconsideran los conjuntos A y B y formamos parejas o pares ordenados con los elementos de A como primeros elementos y los de B como segundos, se obtiene un conjunto llamado producto cartesiano. Esto es:

Definición. A x B = {(a,b) : a A, b B }

Ejemplo: A= {1,2,5}, B = {2,3}

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

5.1.2 Relación Binaria

Una relación binaria R de A a B es unsubconjunto de A x B. Los elementos de A que aparecen en la relación forman el dominio DOM(R) y los de B forman el rango RAN(R).

Notación: R A X B
DOM(R) = {x : (x,y) R }
RAN(R) = {y : (x,y) R }

Relación Inversa. La relación inversa de una relación R de A a B es la que se obtiene si invertimos el orden en las parejas.

= { (y,x) : (x,y) R }
Observamos que la relación inversaes una relación de B a A.

Ejemplos.
Si A = {a,b,c,x,y,z}, B = {1,2,3,4,5}
= {(a,2),(c,2),(x,1),(y,5),(z,5)}
= {(a,1),(a,5),(c,3),(x,2),(x,4)}
= {(a,4),(b,2),(c,5),(x,1)}
= {(a,3),((b,1),(b,5),(c,3),((c,5),(x,1),(y,4)}

Son relaciones binarias

   = {a,c,x,y,z}
= {1,2,5}
= {a,c,x}
= {1,2,3,4,5}
= {a,b,c,x}
= {1,2,4,5}
= {a,c,x,y}
= {1,3,4,5}

Y sus relacionesinversas son:

= {(2,a),(2,c),(1,x),(5,y),(5,z)}
= {(1,a),(5,a),(3,c),(2,x),(4,x)}
= {(4,a),(2,b),(5,c),(1,x)}
= {(3,a),(1,b),(5,b),(3,c),(5,c),(1,x),(4,y)}

5.1.3 Representación de las relaciones

Representación matricial
Una relación entre dos conjuntos A y B puede ser representada por una matriz binaria, que consiste en 0′s y 1′s . Asociamos cada elemento del primer conjunto A con...