Relacion Simetrica

1. Relaciones Simétricas
Geovanni Forero charry
Estudiante de ing. De sistemas

2. Relación simétrica
Una relación binaria sobre un conjunto ,
es simétrica cuando se da que si un
elemento está relacionado con otro
mediante , entonces ese otro también
está relacionado con el primero.
Es decir,

En tal caso, decimos que cumple con la
propiedad de simetría.
La aplicación de cualquier relación sobre
un conjunto , se representa con el
par ordenado( , ).

3. La relación = es simétrica, mientras
que < no lo es. Generalmente, se
tiene lo siguiente:
Definición1:Una relación R sobre un
conjunto X es simétrica si, para
todo .x e y perteneciente a X, xRy
implica yRx. Por consiguiente,
R es simétrica vxvy(xRy
≡
=>yRx)

4. La relación hermano es simétrica porque, si .x es
un hermano de y. entonces y es un hermano
de x. En el conjunto de los seres humanos, la
relación hermano varón es un ejemplo de
relación.no simétrica. Si x es varón mientras que
y es hembra, entonces .x puede ser hermano
varón de y, pero y, ciertamente, no puede ser
hermano varón de x. Sin embargo, sobre el
conjunto de los varones, la relación hermano
varón es simétrica. La relación de similitud sobre
el conjunto de los triangulos en un plano es
reflexiva y simétrica.
La relación < es definitivamente no simétrica. De
hecho, < es un ejemplo de una relación
antisimétrica, como indica la siguiente definición:

5. Definición1.1:
Una relación R sobre X es
antisimétrica si, para todo y=x, xRy
excluye a yRx. En otras palabras, si
se alcanzan xRy e yRx, entonces
x=y. Por consiguiente,
R es antisimétrica
vxvy(xRy
≡
ΛyRx=>x =y)

6. Ejemplo
Un ejemplo de relación antisimétrica
es la relación de subconjunto. De
hecho, si A y B son dos conjuntos, y
si A es un subconjunto de B y B es
un subconjunto de A, entonces A=
B. En el caso de que una relación
sea no reflexiva, la Definición1.1
significa que xRy excluye a yRx.

7. Figuras
(a) Distribuida
(b) Anillo
(c) Estrella

8. Por ejemplo
la relación "madre de" es antisimétrica porque “x es
madre de y" excluye a "y es madre de x". La relación
"ama", tal que "x ama a y" no es ni simétrica ni
antisimétrica. Existen amores no correspondidos, como
indican muchas novelas y poemas.
En el digrafo de una relación simétrica, todos los arcos
son bidireccionales; esto es, si existe un arco dirigido
desde x a y, existe también un arco en la dirección
opuesta. Un ejemplo de tal digrafo está dado por la red
de tipo estrella mostrada en la Figura 1.c Cuando
representamos una relación simétrica, es frecuente
dibujar sólo un arco simple entre dos nodos
cualesquiera, y este arco representa ambas
direcciones. Entonces suelen omitirse las flechas. Si se
hace esto, la figura resultante ya no es un grafo
dirigido, puesto que no existen direcciones, sino un
grafo no dirigido o simplemente un grafo.

9. Si una relación es antisimétrica, entonces ningún arco
tiene un compañero que vaya en la dirección opuesta.
La red de tipo anillo de la Figura 1.b es un ejemplo de
relación antisimétrica. Algunas relaciones no son ni
simétricas ni antisimétricas. Un ejemplo está dado por
la Figura1.a. En este caso, existe un arco que es
bidireccional, mientras que los restantes arcos son
unidireccionales.
Si MR= [mij] es la matriz de una relación, entonces
mij = mji si y sólo si la matriz es simétrica. Esto
significa que la matriz MR debe ser simétrica con
respecto a la diagonal. Una matriz es antisimétrica si y
sólo si mij= 1 hace necesario que mji= 0. Esto es
ligeramente más difícil de descubrir. Las siguientes
matrices ilustran las nociones de simetría y
antisimetría. Observe que en rela­ciones antisimétricas
tanto mij como mji pueden ser 0.

10. Simétrica Antisimétrica
101 001
010 010
100 010
Ninguna de las dos
101
000
111

11. Relación Transitiva
Una relación binaria R sobre un conjunto
A es transitiva cuando se cumple:
siempre que un elemento se relaciona con
otro y éste último con un tercero,
entonces el primero se relaciona con el
tercero.
Esto es:

Una relación R es transitiva si: a R b y b
R c se cumple a R c.
La propiedad anterior se conoce como
transitividad.

12. Ejemplos
La relación binaria "menor que" en los enteros es
transitiva:
Si y entonces .
Así, puesto que 2 < 5 y 5 < 7, la transitividad implica
que 2<7.
En general las relaciones de orden (ser menor, mayor,
igual, menor o igual, mayor o igual) son transitivas.
La relación binaria "divide a" en los enteros también es
transitiva. Denotando por a | b a la expresión "a divide
a b":
Si y entonces .

13. Ejemplos
Dado que 3|12 (3 divide a 12) y 12|48 (12 divide
a 48), la transitividad establece que 3|48 (3
divide a 48).
Sin embargo, no todas las relaciones binarias son
transitivas. La relación "no es subconjunto" no es
transitiva. Por ejemplo, si X = {1,2,3},
Y={2,3,4,5}, Z={1,2,3,4}. Entonces
Se cumple y pero no se cumple
puesto que X es subconjunto de Z.
Otro ejemplo de relación binaria que no es
transitiva es "ser la mitad de": 5 es la mitad de
10 y 10 es la mitad de 20, pero 5 no es la mitad
de 20.

14. Transitividad
Si .x es más alto que y, e y es más
alto que z, inmediatamente
concluimos que .x es más alto que z.
Similarmente, si x es un antepasado
de y, e y es un antepasado de z,
entonces .x tiene que ser un
antepasado de z. Finalmente, si x = y,
e y = z, entonces x = z. Todos estos
argumentos dependen de la
transitividad, una propiedad que se
define como sigue:

15. Definición:
Una relación R sobre X es transitiva
si, para todo x, y, z en X, siempre
que xRy e yRz, entonces xRz. Esto
es,
R es transitiva VxVyVz(xRy yRz
≡
=>xRz)

16. Se cuenta la relación más alto que, la relación
antepasado y la relación igualdad. Además, la
relación < es transitiva porque x < y, e y < z
implica x < z. Finalmente, la relación subconjunto
sobre conjuntos es transitiva porque si A C B y si
B C C entonces A C C.
En muchos casos, x = y, e y = z se abrevia en la
forma x = y = z. Se puede utilizar una notación
similar para otras relaciones transitivas. Por
ejemplo, x < y < z significa realmente que x < y,
e y < z. En el caso de la relación subconjunto, se
escribe A C B C C para expresar A C B y B C C.
Entre los ejemplos de relaciones transitivas

17. Por consiguiente
una relación es transitiva si y sólo si
todos los pares de objetos que
pueden ser alcanzados a través de
un intermediario pueden también
ser alcanzados directamente. La
relación R2 entonces, tiene que ser
un subconjunto de R. Por lo tanto,
una relación R es transitiva si y sólo
si R2 C R. Esto se puede aprovechar
para demostrar la transitividad.

18. Relaciones 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:

19. (V R’ reflexiva) (A C R’ C 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:
(V R’ reflexiva) (A C R’ C ref( R )) => R’ =
ref( 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:
(V R’ reflexiva) (A C R’ C ref( R )) => R’ =
ref( R )

20. La cerradura 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 anterores es muy
simple.

21. 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 se pueden obtener
mediante las matrices siguientes
Mref( R ) = MR U In, donde In es la
matriz identidad de orden |A|.
Msim( R ) = [a ij], donde a ji = 1 si
a ij = 1 en MR.

22. La Matriz identidad In de orden n es:
 1 ... 0

⋮ ⋱ ⋮
0 ... 1
sea que para lograr la cerradura
reflexiva debmos agregar 1′s en la
diagonal, para la cerradura
simétrica debemos agregar 1′s en
luagres simétricos a la diagonal
principal donde existan 1′s.