Orden parcial

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

CAPITULO 7 ORDEN PARCIAL ORDEN PARCIAL - RETICULAS
OBJETIVOS A. GENERALES  Dar razones teóricas y fundamentales por que se deben estudiar el orden parcial, las retículas.  Presentar la información abstracta pertinente del álgebra de Boole para tratar las retículas. B. ESPECIFICOS  Resolver problemas sobre Ordenparcial - Retículas.

 Presentar el dominio Algebra de Bool en las retìculas.  Estudiar las técnicas de orden lexicograficas.  Estudiar el orden topológico.
Definición: Dados dos conjuntos no vacíos A y B donde R : A→B donde

R ⊂ A × B entonces daremos algunas de las relaciones importantes:
RELACIONES DE ORDEN Las relaciones se clasifican en: • • • Relaciones de orden: Una relación R enun conjunto A es una relación de orden si es transitiva y antisimétrica. Relaciones de Cuasiorden: Una relación R en un conjunto A es una relación de cuasiorden si es reflexiva y transitiva. Relaciones de Orden Parcial: Una relación R en un conjunto A es una relación de orden Parcial si es reflexiva, antisimétrica y transitiva

Ejemplo 1: Sean A una colección de subconjuntos de un conjunto S y ⊆la  relación de inclusión de conjuntos. Entonces  es un orden parcial A.  en Ejemplo 2: Una relación R de divisibilidad definida es un orden parcial en Z+ , el conjunto de los enteros positivos. Ejemplo 3: La relación < en Z+ no es un orden parcial, pues no es reflexiva. Observación: Si R es un orden parcial sobre el conjunto A en el que está definida, entonces diremos que A es un conjuntoparcialmente ordenado, y lo denotamos por (A, R).

Lic. Guillermo Mas Azahuanche

309

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Ejemplo 4: Respecto a los ejemplos (1) y (2), (A, ⊆) y (Z+, R) son conjuntos parcialmente ordenados. • Relaciones de Orden Total: Una relación R en un conjunto A es una relación de orden Total si es transitiva, antisimétrica yde tricotomía.

1. R es reflexiva en un conjunto A, si para todo a ∈ A existe el par (a,a) ∈ R
es decir a R a, para cualquier “a” є A. R es reflexiva si cada uno de sus

elementos a ∈ A esta relacionado consigo mismo. La Matriz booleana de una relación reflexiva debe tener “1” en toda su diagonal principal en la matriz.
2. R es antisimétrica en un conjunto A, si en todos los casos que a R by b R a

se tiene que a = b, ∀ a, b que ∈ A. Es decir si a ≠ b, (a R b) 3. Una relación R es transitiva :

y (b R a). /

si ∀ a, b, c ∈ A / a R b ∧ b R c ⇒ a R c.
Si esta condición no se cumple, la relación R no es Transitiva.
4. Sea A un conjunto y R(A) una relación binaria definida en A. Diremos que la

relación R(A) satisface en A la ley de tricotomía si solo sí en forma excluyentese tiene; ∀ x , y ∈ A se cumple una y sólo una de las siguientes proposiciones: ó x = y ó ( x , y ) ∈ R ó

( y , x )∈ R

Un conjunto ordenado es un par formado por un conjunto A y una relación de orden R definida en él, es decir, el par (A,R). Por ejemplo: (N, ≤ ), (N, ½ ),
(Dn, ½ ), donde con ½ indicamos la relación de divisibilidad.

Los elementos a y b del conjunto ordenado (A, R) sedicen comparables si a R b ó b R a. Ya hemos expuesto que una relación R en un conjunto A es un Orden Parcial si R es Reflexiva, Antisimétrica y Transitiva. El conjunto A, junto con el orden parcial R es un conjunto parcialmente ordenado, denotado como (A,R). Definamos un ejemplo: Sea R el conjunto de todas las relaciones de equivalencia en un conjunto A, como R consta de sub-conjuntos de AxA, R es unconjunto parcialmente ordenado bajo el orden parcial de contencion de conjuntos. Si R y S son relaciones de equivalencia en A,

Lic. Guillermo Mas Azahuanche

310

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Es decir

R ⊆ S ⇔

x R y ⇒ x S y

, ∀

x, y ∈ A.

Contraejemplo:

La relación “ 1 , se puede descomponer en sus factores primos...