Relaciones Cerradura

Tema 2.3

En matemáticas y en computación las relaciones de equivalencia juegan un papel muy importante, en la mayoría de las estructuras matemáticas que manejamos la igualdad es en relidad una equivalencia, como por ejemplo en fracciones.

En muchas ocasiones una relación no cumple alguna de las propiedades de equivalencia, pero hay relaciones que la incluyen y que sí cumplen la propiedad. De todas las relaciones la menor posible se llama su 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’ = 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:
(∀ R’ reflexiva) (A ⊆ R’ ⊆ ref( R )) ⇒ R’ = ref( R )

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.

Teorema: Sea R una relación en A y M_R su matriz asociada. La cerradura reflexiva y la cerradura simétrica de R son únicas y se pueden obtener mediante las matrices siguientes

M_{ref( R )} = M_R ∪ I_n, donde I_n es la matriz identidad de orden |A|.

M_{sim( R )} = [a _ij], donde a _ji = 1 si a _ij = 1 en M_R.

La Matriz identidad I_n de orden n es:

O 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.

Ejemplos: Sección anterior.

Para la cerradura transitiva es un procedimiento un poco más complicado Cerradura Transitiva.