En el estudio de las relaciones matemáticas, el cierre de una relación consiste en extender dicha relación mediante la cantidad mínima de elementos necesaria para satisfacer una propiedad específica. Hablamos más comúnmente de cierre reflexivo, simétrico o transitivo. El cierre transitivo es, por definición, la relación transitiva más pequeña que contiene a la relación original.
Conceptos fundamentales de los cierres de relación
Cada cierre cumple una función distinta al suplementar una relación con los pares necesarios:
- Cierre Reflexivo: Se añaden pares (a,a) para cada elemento del conjunto para hacer la relación reflexiva.
- Cierre Simétrico: Se añade el par inverso (b,a) para cada par (a,b) existente.
- Cierre Transitivo: Se añade cada par que sigue de la transitividad. Si (a,b) ∈ R y (b,c) ∈ R, entonces (a,c) debe estar presente.
Ejemplo comparativo
Consideremos el conjunto A = {1, 2, 3} y la relación R = { (1,2), (2,3) }.
| Tipo de cierre | Resultado |
|---|---|
| Cierre reflexivo | { (1,2), (2,3), (1,1), (2,2), (3,3) } |
| Cierre simétrico | { (1,2), (2,1), (2,3), (3,2) } |
| Cierre transitivo | { (1,2), (2,3), (1,3) } |
Cálculo del cierre transitivo
Para ilustrar el proceso, sea A = {1, 2, 3, 4} y S = { (1, 2), (2, 3), (3, 4) } la relación sucesora en A. Para calcular S⁺, observamos por inspección que (1, 3) debe estar en S⁺, ya que (1, 2) y (2, 3) están en S. En general, se deduce que si (a, b) ∈ S y (b, c) ∈ S, entonces (a, c) ∈ S⁺. Esta condición es el requisito de membresía para que el par (a, c) esté en la composición S².
S⁺ contiene por lo menos S ∪ S². Sin embargo, la relación S ∪ S² no siempre es transitiva. Por ejemplo, (1, 4) no es un elemento de S ∪ S², pero (1, 3) ∈ S² y (3, 4) ∈ S. Por lo tanto, la composición S³ produce (1, 4), el cual debe estar en S⁺. Este proceso debe continuarse hasta que la relación resultante sea transitiva; si A es finito, el cierre transitivo se obtendrá en un número finito de pasos.
Lea también: Guía para una Reunión de Cierre de Auditoría Exitosa
Algoritmos y matrices
Dejar R ser una matriz de relaciones sobre un conjunto finito. Podemos utilizar el hecho de que en la aritmética booleana, T + T = T. Cada multiplicación matricial duplica el número de términos que se han agregado a la suma. Para calcular R⁺ usando este algoritmo, no es necesario realizar más que ⌈log₂n⌉ multiplicaciones matriciales. Es común visualizar el cierre transitivo mediante grafos dirigidos, ya que indica cuántas maneras están interconectados los elementos. Las computadoras utilizan el cierre transitivo en algoritmos para el análisis de redes, siendo una herramienta crucial en matemáticas para validar pruebas y algoritmos complejos.
Lea también: Ejemplos de Cierre Contable
Lea también: Cierre de Auditoría: Proceso Detallado
tags: #cierre #transitivo #ejercicios #resueltos