Clausura transitiva

Clausura transitiva

La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original. La clausura transitiva de una relación R\, se denotada CT(R)\,. En otras palabras, CT(R)\, es la relación binaria que verifica:

  1. R\subseteq CT(R)
  2. CT(R)\, es transitiva
  3. Si R'\, es una relación transitiva tal que R\subseteq R', entonces CT(R)\subseteq R'

Nótese que si R\, es transitiva, entonces CT(R)=R\,. Dada cualquier relación siempre existe su clausura transitiva.

Existencia y descripción

La clausura transitiva de una relación binaria siempre existe, es decir, dada cualquier relación binaria esta puede extenderse hasta que la relación extendida sea transitiva. Además la clausura transitiva que denotaremos aquí mediante \mathcal{R}_{CT} admite una caracterización muy sencilla:

(1) x\mathcal{R}_{CT}y \Rightarrow \quad \exists z_1\dots \exists z_n: x\mathcal{R}z_1 \land \dots \land z_n\mathcal{R}y

Definiendo las potencias de \mathcal{R} inductivamente:

(2) \begin{matrix} \mathcal{R}^2=\mathcal{R}\times\mathcal{R} := \{(x,y)|\exists z:x\mathcal{R}z \land z\mathcal{R}y \} \\ \dots \\ \mathcal{R}^{n+1}= \mathcal{R}\times\mathcal{R}^n \end{matrix}

La clausura transitiva se puede caracterizar como la unión generalizada:

(3) \mathcal{R}_{CT} = \bigcup_{i \in \mathbb{N}} \mathcal{R}^i

Cómo calcularla algorítmicamente

  • Si una relación \mathcal{R} ya es una relación transitiva, entonces es su propia clausura transitiva.
  • En cambio, si \mathcal{R} no es transitiva, su clausura transitiva puede hallarse usando la representación de la relación como matriz booleana. Dada la relación \mathcal{R} sobre un conjunto de n elementos \{a_1,\dots,a_n\}, la matriz booleana asociada a la relación viene dada por:

B_\mathcal{R} = [b_{ij}]\quad \land \quad b_{ij} = \begin{cases} 1 & \mbox{si}\ a_i\mathcal{R}a_j\\ 0 & \mbox{si}\ \lnot a_i\mathcal{R}a_j \end{cases}

Una vez calculada se examina en qué caso de los siguientes estamos:

  1. Se encuentran las potencias de B_\mathcal{R} (B_\mathcal{R}^2, B_\mathcal{R}^3,..., B_\mathcal{R}^k, etc.)
  2. Si B_\mathcal{R}^k es la relación total o producto cartesiano, no se buscan más potencias y esa es la Clausura Transitiva.
  3. Si B_\mathcal{R}^k es la matriz nula, entonces la CT(\mathcal{R}) es la unión generalizada (3).
  4. Si B_\mathcal{R}^k es igual a alguna potencia anterior, entonces no se buscan más potencias y la CT(\mathcal{R}) es idéntica que en el punto anterior.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Clausura — puede referirse a: Cierre, por oposición a apertura o inauguración (especialmente en los actos solemnes). Clausura monástica o conventual. Matemáticas En matemáticas, la clausura o cerradura se refiere al mínimo conjunto que es cerrado bajo una… …   Wikipedia Español

  • Clausura de relación — En matemática, sea una relación R sobre un conjunto A, la clausura o cierre de R es la menor relación que contiene a R y cumple con una propiedad dada. Tales propiedades pueden ser la transitividad, reflexividad o simetría, en cuyo caso la… …   Wikipedia Español

  • Clausura reflexiva — Sea R una relación binaria aplicada sobre un conjunto A, la clausura reflexiva o cierre reflexivo de , denotada , es la relación reflexiva más pequeña aplicada sobre que contiene a . En otras palabras, es …   Wikipedia Español

  • Clausura simétrica — Sea R una relación binaria aplicada sobre un conjunto A, la clausura simétrica o cierre simétrico de R, denotada CS(R), es la relación simétrica más pequeña aplicada sobre A que contiene a R. En otras palabras, CS(R) es la relación binaria que… …   Wikipedia Español

  • Conjunto parcialmente ordenado — En matemáticas, especialmente en teoría del orden, un conjunto parcialmente ordenado (o poset, del inglés partially ordered set) es un conjunto equipado con una relación binaria de orden parcial. Ésta formaliza el concepto intuitivo de orden,… …   Wikipedia Español

  • Grafo acíclico dirigido — Un DAG simple. En ciencias de la computación y matemáticas un grafo acíclico dirigido (o gráfico dirigido acíclico) conocido como DAG por sus siglas en inglés, es un grafo dirigido que no tiene ciclos; esto significa que para cada vértice v, no… …   Wikipedia Español

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • Cierre — El término cierre puede referirse a: Diversos conceptos de la teoría de conjuntos Cierre o clausura simétrica Cierre o clausura de relación Cierre o clausura transitiva Cierre o clausura reflexiva Cierres o acoplamientos mecánicos Cierre eclair,… …   Wikipedia Español

  • Diagrama de Hasse — Saltar a navegación, búsqueda Elementos de P( P( P(P({})))) en Diagrama de Hasse. En matemáticas, un diagrama de Hasse es una representación …   Wikipedia Español

  • Relación bien fundada — En teoría de conjuntos, una relación bien fundada sobre una clase X es una relación binaria R sobre X tal que todo subconjunto no vacío de X tiene un elemento R mínimo; esto es: Para todo subconjunto no vacío S de X, hay un elemento m en S tal… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”