Matemáticas | Órdenes parciales y celosías

Las relaciones se pueden utilizar para ordenar algunos o todos los elementos de un conjunto. Por ejemplo, el conjunto de números naturales está ordenado por la relación $\leq$ tal que para cada par ordenado $(x,y)$ en la relación, el número natural $x$ viene antes que el número natural $y$ a menos que ambos sean iguales. Formalmente, “Una relación $R$ en conjunto $A$ se denomina ordenación parcial u orden parcial si es reflexiva, antisimétrica y transitiva. Un conjunto $A$ junto con una ordenación parcial $R$ se denomina conjunto parcialmente ordenado o poset . La poset se denota como $(S,R)$ .”

Ejemplo: Muestre que la relación de inclusión $\subseteq$ es una ordenación parcial sobre el conjunto potencia de un conjunto.

Solución Como todo conjunto $S\subseteq S$ , $\subseteq$ es reflexivo. Si $S\subseteq R$ y $R\subseteq S$ entonces $R = S$ , lo que significa que $\subseteq$ es antisimétrico. Es transitivo como $R\subseteq S$ e $S\subseteq T$ implica $R\subseteq T$ . Por lo tanto, $\subseteq$ es una ordenación parcial sobre $P(S)$ , y $(P(S), \subseteq)$ es un poset.

Nota: El símbolo $\preceq$ se usa para indicar la relación en cualquier pose. La notación $a \prec b$ se utiliza para denotar $a \preceq b$ pero $a \neq b$ .

Comparabilidad: Sean $a$ y $b$ los elementos de una poset $(S, \preceq)$ , entonces $a$ y $b$ se dice que son comparables si $a \preceq b$ o $b \preceq a$ . De lo contrario, $a$ y $b$ se dice que son incomparables .

Ejemplo: en el poset $(Z^+, \mid)$ (dónde $Z^+$ está el conjunto de todos los números enteros positivos y $\mid$ es la relación de división) ¿los números enteros 3 y 9 son comparables? ¿Son 7 y 10 comparables?
Solución: 3 y 9 son comparables porque, $3 | 9$ es decir, 3 divide a 9. Pero 7 y 10 no son comparables porque $7 \nmid 10$ y $10 \nmid 7$ .

Orden Total: Es posible en un poset que por dos elementos $a$ ni $b$ ni $a\preceq b$ ni $b\preceq a$ es decir los elementos $a$ y $b$ sean incomparables. Pero en algunos casos, como el poset $(Z^+, \leq)$ , cada elemento es comparable a cualquier otro elemento.

Un poset $(S, \preceq)$ se dice totalmente ordenado si cada dos elementos de $S$ son comparables. $\preceq$ i se llama orden total . Un conjunto totalmente ordenado también se llama string.

Diagramas de Hasse: Un orden parcial, al ser una relación, se puede representar mediante un dígrafo. Pero no es necesario mostrar la mayoría de los bordes, ya que sería redundante. Por ejemplo, sabemos que todo orden parcial es reflexivo, por lo que es redundante mostrar los bucles propios en cada elemento del conjunto en el que se define el orden parcial. Cada orden parcial es transitivo, por lo que todos los bordes que denotan transitividad pueden eliminarse. Las direcciones de los bordes se pueden ignorar si se supone que todos los bordes tienen solo una dirección posible, convencionalmente hacia arriba. En general, un orden parcial en un conjunto finito se puede representar mediante el siguiente procedimiento:

Elimina todos los bucles automáticos de todos los vértices. Esto elimina todos los bordes que muestran reflexividad.
Elimine todos los bordes que están presentes debido a la transitividad, es decir, si $(a,b)$ y $(b,c)$
están en el orden parcial, luego elimine el borde $(a,c)$ . Además, si $(c,d)$ está en orden parcial, elimine el borde $(a,d)$ .
Arregle todos los bordes de manera que el vértice inicial esté debajo del vértice terminal.
Quite todas las flechas en los bordes dirigidos, ya que todos los bordes apuntan hacia arriba.

Por ejemplo, el poset $(\{1, 2, 3, 4\}, \leq)$ se convertiría en un diagrama de Hasse de la siguiente manera:

La última figura del diagrama anterior contiene información suficiente para encontrar el orden parcial. Este diagrama se llama Diagrama de Hasse .

Extremos en Posets: Los elementos de posets que tienen ciertas propiedades extremas son importantes para muchas aplicaciones.

Elementos máximos: se dice que un elemento $a$ en el poset es máximo si no hay ningún elemento $b$ en el poset tal que $a \prec b$ .
Elementos mínimos: se dice que un elemento $a$ en la poset es mínimo si no hay ningún elemento $b$ en la poset tal que $b \prec a$ .

Los elementos Maximal y Minimal son fáciles de encontrar en los diagramas de Hasse. Son los elementos superior e inferior respectivamente.
Por ejemplo, en el diagrama de hasse descrito anteriormente, «1» es el elemento mínimo y «4» es el elemento máximo. Dado que máximo y mínimo son únicos, también son los elementos más grandes y más pequeños de la poset.

Nota: Si el elemento máximo o mínimo es único, se denomina elemento mayor o menor del poset respectivamente.

Límites en Posets: A veces es posible encontrar un elemento que sea mayor o igual que todos los elementos en un subconjunto $A$ de poset $(S, \preceq)$ . Tal elemento se llama el límite superior de $A$ . Del mismo modo, también podemos encontrar el límite inferior de. Estos límites se pueden restringir aún más para obtener el límite superior mínimo y el límite inferior máximo . Estos límites son elementos que son menores o mayores que todos los demás límites superiores o inferiores, respectivamente.

Ejemplo: Encuentre el límite superior mínimo y el límite inferior máximo de los siguientes subconjuntos $\{b, c\}$ : , $\{g, e, a\}$ , $\{e, f\}$ .

Solución: Para el conjunto $\{b, c\}$
Los límites superiores son – $e, f, h, i$ . Así que el límite superior mínimo es $e$ .
Los límites inferiores son – $a$ . Así que el límite inferior más grande es $a$ .
Para el conjunto $\{g, e, a\}$
Los límites superiores son – $h$ . Así que el límite superior mínimo es $h$ .
Los límites inferiores son – $a$ . Así que el límite inferior más grande es $a$ .
Para el conjunto $\{e, f\}$
Los límites superiores son – $f, h, i$ . Así que el límite superior mínimo es $f$ .
Los límites inferiores son – $e, c, b, a$ . Así que el límite inferior más grande es $e$ .

Retículos: Un Poset en el que cada par de elementos tiene ambos, un límite superior mínimo y un
límite inferior máximo, se denomina retículo. Hay dos operaciones binarias definidas para celosías:

Unión: La unión de dos elementos es su límite superior mínimo. Se denota por $\vee$ , que no debe confundirse con la disyunción.
Encuentro: El encuentro de dos elementos es su mayor límite inferior. Se denota por $\wedge$ , que no debe confundirse con una conjunción.

Sublattice: una subred de lattice $L$ es un subconjunto $S\subseteq L$ tal que si $a,b \in S$ , y $a\vee b \in S$ .

Identidades para unirse y reunirse:

$\begin{flalign*} &\bullet\: x\wedge x = x\:&&and\: x\vee x = x \\ &\bullet\: x\wedge y = y\wedge x\:&&and\: x\vee y = y\vee x \\ &\bullet\: (x\wedge y)\wedge z = x\wedge (y\wedge z)\:&&and\: (x\vee y)\vee z = x\vee (y\vee z) \\ &\bullet\: x\wedge (y\vee x) = x\:&&and\: x\vee (y\wedge x) = x \\ \end{flalign*}$

Las leyes distributivas pueden o no ser ciertas para una red:

$x \wedge (y\vee z) = (x\wedge y) \vee (x\wedge z)$
$x \vee (y\wedge z) = (x\vee y) \wedge (x\vee z)$

Nota: Un retículo se llama retículo distributivo si se cumplen las leyes distributivas.

Pero las leyes semidistributivas son válidas para todas las redes:

$x \wedge (y\vee z) \geq (x\wedge y) \vee (x\wedge z)$
$x \vee (y\wedge z) \leq (x\vee y) \wedge (x\vee z)$

Dos propiedades importantes de los retículos distributivos:

En cualquier retícula distributiva $a\wedge y = a \wedge x$ y $a\vee y = a \vee x$ juntos implican que $x = y$ .
Si $a\wedge x = O$ y $a\vee x = I$ , donde $O$ y $I$ son los elementos mínimo y máximo de la red, entonces se dice que $a$ y $x$ son un par complementario. $O$ y $I$ son un par trivialmente complementario.

retícula complementada: Supongamos que L es una retícula acotada (con 0 y 1), y a∈L(a pertenece a L). Un complemento de a es un elemento b∈L tal que :

a∧b=0 y a∨b=1.

Observación: Los complementos pueden no existir. Si L es una string no trivial, entonces ningún elemento (aparte de 0 y 1) tiene un complemento. Esto también muestra que si a es un complemento de un elemento no trivial b, entonces ayb forman una antistring.

Un elemento en una red acotada se complementa si tiene un complemento.
Una red complementada es una red acotada en la que todos los elementos se complementan.

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2007, Pregunta 26
2. GATE CS 2006, Pregunta 4
3. GATE CS 2005, Pregunta 9
4. GATE CS 2004, Pregunta 73
5. GATE CS 2015 Conjunto-1, Pregunta 44

Referencias:

Conjunto parcialmente ordenado – Wikipedia
Lattices – Wikipedia

Este artículo es una contribución de Chirag Manwani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta