matematicas discretas

5.3 Relaciones De Equivalencia

(Cerraduras,

Clases De Equivalencia y Particiones)




Cerradura de una relación
Definición. Sea R una relación en un conjunto A. Unacerradura 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 Ren 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 anteriores es muy simple.

Teorema: Sea Runa 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 ∪ In, donde In es lamatriz identidad de orden |A|.
Msim(R) = [a ij], donde a ji = 1 si a ij = 1 en MR.

La Matriz identidad In de orden n es:

{$ {(1,…,0), (vdots, ddots, vdots), (0,…,1)] $}

O sea que para lograrla cerradura reflexiva debemos 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.

Cierre de equivalenciaPara calcular el cierre de equivalencia de una relación binaria R sobre un conjunto A:

Calcularemos primero su cierre reflexivo, ρ(R)

Sobre el resultado calcularemos el cierre simétrico,σ(ρ(R))

finalmente el cierre transitivo del resultado anterior, τ (σ(ρ(R)))



Clases de Equivalencia

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