Composición de relaciones
Definición: Sean R: X ↔ Y y S :Y ↔ Z dos relaciones. La composición de R y S, que se denota como R o S, contiene los pares ( x, z ) si y sólo si existe un objeto intermedio y tal que ( x, y ) está en R y ( y, z )está en S.
Por consiguiente,
x(R oS)z =Ǝy(xRy a yRz)
Definición: Sean R: X ↔ Y y S :Y ↔ Z dos relaciones. La composición de R y S, que se denota como R o S, contiene los pares ( x, z ) si y sólo si existe un objeto intermedio y tal que ( x, y ) está en R y ( y, z )está en S.
Por consiguiente,
Esta definición implica que (x, ) está en la composición de las relaciones hermana y padre, si existe un individuo y tal que x es hermana de y e y es un padre de z. Esto es exactamente la relación tía. De esto se sigue, que la relación tía es la composición de la relación hermana y padre como hemos afirmado. En general, para determinar si (x, z) está en la relación R o S, se necesita siempre un intermediario y la hermana, en el caso de la relación tía, tal que sean válidas xRy e yRz.
Ejemplo:
Se tienen cinco personas A, B, C, D y E. C es dueño del camión llamado Machakito y E es dueño del camión llamado Imperioso. A es amigo de B y D, B es amigo de C y C es amigo de E. Sea R la relación "x es amigo de y" y sea S la relación "y es dueño del camión z"."Calcular la relación R o S.
Solución Si R es la relación "x tiene a y como amigo" y si S es la relación "y
es el dueño del camión z " entonces el par ( x, z ) está en R o S si existe un intermediario y tal que x tiene a y como amigo e y es dueño del camión z. Las relaciones R y S están dadas por
R={ (A, B), (A, D), (B, C), (C, E)}
S = {(C, Machakito), (E, Imperioso)}
Ahora bien,
R o S - {(B, Machakito), (C, Imperioso)}
B tiene acceso a un camión a través del intermediario C, que es dueño de Machakito y C tiene acceso a un camión a través de intermediario £, que es dueño de Imperioso.
La composición de dos relaciones se puede representar mediante un grafo. Sean R : X ↔ Y y S : Y ↔ Z. Ahora se dibujan todos los nodos de X a la izquierda, todos los nodos de Z a la derecha, y todos los nodos del conjunto intermediario Y en el medio. Asumimos que los miembros de X van desde xl hasta x4,, los miembros de Y van desde y1 hasta y4, y los miembros de Z van desde z1 hasta z5. De acuerdo con lo que hemos dicho antes, el par (x i, z k) está en R o S si y sólo si existe un intermediario y j. tal que hay un arco que va, desde xj. hasta yi y desde éste a z k. Por ejemplo, (x1, z4) está en R o S porque existe un arco desde x1 hasta y2, y desde éste existe un arco a z4. Por otra parte (x1, z3) no está en R o 5, porque no existe y j a través del cual x1 pueda acceder a z3. A continuación se enumeran sistemáticamente todos los pares de R o S:
(x1, z2 ) € S o R a través del intermediario y1
(x1, z1) € S o R a través del intermediario y2
(x1, z4) € S o R a través del intermediario y2
(x4, z3) € S o R a través del intermediario y3
La relación resultante entonces es
R o S = {(x1, z2), (x1, z2), (x1, z4), (x4, z3)}
La composición es una operación asociativa; esto es, si R, S y P son tres relaciones, entonces se cumple lo siguiente:
(R o S)o p = R o (S o P)
Los paréntesis se pueden eliminar, por consiguiente, en los casos que involucren la composición de varias relaciones.
Esto completa el primer paso de la demostración. Ahora intercambiamos los cuantificadores existenciales para obtener
Es fácil ver que la última expresión es lógicamente equivalente a x ((R o S) o P) w.
Por consiguiente,
La ecuación sigue ahora fácilmente.
Si SP S2 y 53 son tres relaciones, entonces, xS1 o S2 o S3 y es verdadera si y sólo si existen exactamente dos intermediarios a través de los cuales x tiene acceso a y. Esta fue esencialmente la idea de la demostración. Por lo tanto, la composición de tres relaciones da el conjunto de todos los pares (x. y) tales que x puedealcanzar, digamos, al objeto y en exactamente tres pasos.
Más generalmente, la composición de n relaciones S1, S2, …, Sn contiene el conjunto de todos los pares ( x. y) tales que x puede alcanzar a y en, exactamente, n pasos. Si R: A ↔ A es una relación a A. entonces R o R es el par de (x, y) tal que x puede alcanzar a y en exactamente dos pasos. Normalmente, uno abrevia R o R en la forma R2, R o R o R por R3, y así sucesivamente. Claramente Rn es el conjunto de los pares (x, y) tales que x puede alcanzar a y en, exactamente, n pasos.
Ejemplo: Se define
R= ((1,2), (3,4), (2, 2)}
S= {(4, 2), (2, 5), (3, 1),(1, 3)}
calcular R o S, S o R, R o (S o R), (R o S) o R, R o R, S o S y R o R o R.
Solución
RoS={(l,5), (3,2), (2,5)}
S o R= {(4, 2), (3,2), (1,4)} ≠ R o S
(R o S)oR= {(3,2)}
Ro(S oR)= {(3,2)} = (R o S) oR
R oR={(l,2),(2,2)}
S o S = {(4, 5), (3, 3), (1, 1)}
R o R o R = {(1, 2)
Si dos relaciones están dadas en forma matricial, entonces su composición puede hallarse mediante una variante de la multiplicación de matrices. Las matrices de relaciones sólo contienen los números 0 y 1. Para tratar con estas matrices en términos de la lógica, el 0 se interpreta como falso y el 1 se interpreta como verdadero. Si u y v son dos variables que son o 0 o 1, u v v es igual a 1, a menos que u y v sean ambas 0, y u /\ v es 0, a menos que u y v sean ambas 1. De hecho, u /\ v es exactamente el producto de u y v; esto es, u /\ v = vu. Además, las expresiones cuantificadas existencialmente pueden escribirse como disyunciones. En particular, si el universo consta de los individuos y 1, y 2,…,y m, entonces se tiene
Esta teoría se aplica ahora para encontrar la composición de dos relaciones R y S. Se asume que R es una relación de X a Y, con X {x1,x2,…,xn} e Y{y1,y2,…,ym}.S es una relacion de Y en Z={z 1, z 2,…,z }. Las matrices de relación de S, R y S o R se denotan como MR, MS, y MR ° S, respectivamente. Las entradas de MR, MS, y MR ° S son, respectivamente, m R i j, m S, y m R ° S i j.
Sigue que
De acuerdo con la convención precedente
Esta teoría se aplica ahora para encontrar la composición de dos relaciones R y S. Se asume que R es una relación de X a Y, con X {x1,x2,…,xn} e Y{y1,y2,…,ym}.S es una relacion de Y en Z={z 1, z 2,…,z }. Las matrices de relación de S, R y S o R se denotan como MR, MS, y MR ° S, respectivamente. Las entradas de MR, MS, y MR ° S son, respectivamente, m R i j, m S, y m R ° S i j.
Sigue que
De acuerdo con la convención precedente
