![Page 1: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/1.jpg)
1
RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si
verifica las propiedades reflexiva, antisimétrica y transitiva.
Un conjunto parcialmente ordenado ( A, R ) es un par formado
por un conjunto A y una relación de orden R definida en él.
Los elementos a y b del conjunto ordenado (A, R) se dicen
comparables si a R b o b R a.
(A, R) es un conjunto totalmente ordenado si dos elementos
cualesquiera de A son comparables.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 2: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/2.jpg)
2
Ejemplos 1) (N, ) es un conjunto totalmente ordenado.
a b existe n tal que b = a + n
2) (N, ), donde indica la relación de divisibilidad, es un conjunto
parcialmente ordenado.
a b existe n tal que b = a n
3) Sea Dn = { z / z divide a n }
(Dn, ), donde indica la relación de divisibilidad, es un conjunto
parcialmente ordenado.
4) ((S), ) es un conjunto parcialmente ordenado.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 3: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/3.jpg)
3
DIAGRAMAS DE HASSE (Helmut Hasse, 1898 1979) 1. El diagrama de Hasse de un conjunto ordenado finito es una
representación del mismo en la que cada elemento se representa
por un punto del plano.
2. Si a R b se dibuja a por debajo de b y se une a con b por
medio de un segmento.
3. Finalmente se suprimen los segmentos que corresponden a la
propiedad transitiva, es decir, si a R b y b R c se suprime el
segmento correspondiente a a R c.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 4: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/4.jpg)
4
ELEMENTOS CARACTERÍSTICOS Sea ( A, ) un conjunto ordenado.
mA es maximal de A si no existe x A tal que m x.
m A es minimal de A si no existe x A tal que x m.
mA es máximo de A si x A, x m.
m A es mínimo de A si x A, m x.
El máximo de A, se nota I y se llama elemento unidad.
El mínimo de A, se nota O y se llama elemento cero.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 5: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/5.jpg)
5
Sea S un subconjunto no vacío del conjunto ordenado ( A, ).
c A es cota superior de S si x S, x c.
cA es cota inferior de S si x S, c x.
S está acotado si tiene una cota superior y una cota inferior.
s A es supremo (o mínima cota superior) de S si es cota
superior de S y cota superior c de S se tiene que s c.
i A es ínfimo (o máxima cota inferior) de S si es cota inferior
de S y cota inferior c de S se tiene que c i.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 6: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/6.jpg)
6
Ejercicio Representar el diagrama de Hasse del conjunto ordenado (D48, |) y
hallar los maximales y minimales, las cotas superiores e inferiores, el
supremo, el ínfimo, el máximo y el mínimo (si los hay) del
subconjunto A = {2, 3, 4, 6, 12} en el conjunto ordenado (D48,|).
Solución
cotas superiores de A = {12, 24, 48}
cota inferior de A = {1}
supremo de A = {12}, ínfimo de A = {1}
maximal de A = {12}, minimales de A = {2, 3}
máximo de A = {12} y no existe mínimo de A.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 7: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/7.jpg)
7
Definición Si ( A, R ) y ( B, S ) son dos conjuntos ordenados, en el conjunto
producto AB se pueden definir dos relaciones de orden:
Orden producto: ( a, b ) Prod ( c, d ) a R c y b S d
Orden lexicográfico:
( a, b ) Lex ( c, d ) a c y a R c a = c y b S d. Si ( A, R ) y ( B, S ) son dos conjuntos totalmente ordenados,
(AB, Lex ) es totalmente ordenado.
(AB, Prod ) no es necesariamente totalmente ordenado.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 8: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/8.jpg)
8
Ejemplo Sean (A = {1, 2, 3}, R) y (B = {, , , }, S) conjuntos ordenados
según los diagramas de Hasse siguientes
entonces
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 9: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/9.jpg)
9
Ordenación topológica Si (A, P ) es un conjunto finito ordenado, entonces existe un orden
total (A, T ) que lo contiene, es decir, si a P b entonces a T b.
Demostración Sean a1 elemento minimal en A, a2 elemento minimal en A {a1}, … , ai minimal en A {a1, a2, … , ai1}, … Como A es finito, en un número finito de pasos se obtiene un orden total para los elementos de A:
a1 T a2 T … T ai T … Tan
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 10: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/10.jpg)
10
RETÍCULOS Definición A) Un conjunto ordenado ( L, ) es un retículo si
para todo par de elementos a, b L existen
sup { a, b } L e inf { a, b } L.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 11: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/11.jpg)
11
Ejemplos 1) (N, ) es un retículo.
Sup {a, b} = máx {a, b} inf {a, b} = mín {a, b}
2) (N, ), donde indica la relación de divisibilidad, es un retículo.
Sup {a, b} = mcm {a, b} inf {a, b} = mcd {a, b}
3) Sea Dn = { z / z divide a n }
(Dn, ), donde indica la relación de divisibilidad, es un retículo.
Sup {a, b} = mcm {a, b} inf {a, b} = mcd {a, b}
4) ((S), ) es un retículo.
Sup {A, B} = A B inf {A, B} = A B
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 12: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/12.jpg)
12
5) Si ( A, R ) y ( B, S ) son retículos, entonces
( AB, Prod ) es retículo
sup Prod {(a, b), (c, d)} = (sup R { a, c }, sup S { b, d })
inf Prod {(a, b), (c, d)} = (inf R { a, c }, inf S { b, d })
( AB, Lex ) es retículo
sup Lex {(a, b), (c, d)} = ( sup R { a, c }, inf S { b, d }), si a c
( a, supS { b, d } ), si a = c
inf Lex {(a, b), (c, d)} = ( inf R { a, c }, supS { b, d }), si a c
( a, infS { b, d } ), si a = c
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 13: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/13.jpg)
13
Definición B) Un retículo es una terna ( L, , ) donde L es un conjunto y
, son dos operaciones binarias definidas en L que cumplen
las siguientes propiedades:
1. idempotente : a a = a , a a = a
2. conmutativa : a b = b a , a b = b a
3. asociativa : (a b) c = a (b c) , (a b) c = a (b c)
4. absorción : a (a b) = a, a (a b) = a.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 14: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/14.jpg)
14
Proposición Las dos definiciones anteriores son equivalentes:
a b sup { a, b } a b = inf { a, b }
La relación entre las operaciones y el orden es:
a b a b b a b a
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 15: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/15.jpg)
15
Definiciones Un retículo L es acotado si posee elemento máximo y mínimo.
Se designa por 1 al elemento máximo y por 0 al mínimo.
1 es el elemento neutro para : x 1 = x, x L
0 es el elemento neutro para : x 0 = x, x L Un retículo ( L, , ) es distributivo si a, b, c L se cumple:
a ( b c ) ( a b ) ( a c )
a ( b c ) ( a b ) ( a c )
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 16: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/16.jpg)
16
Ejemplos 1) (Dn , ) es retículo acotado y distributivo n . 2) Los siguientes retículos acotados no son distributivos ya que
a ( b c ) ( a b ) ( a c )
Teorema Un retículo (L, , ) es no distributivo si y sólo si contiene a uno de
los dos retículos del ejemplo anterior 2).
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 17: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/17.jpg)
17
Definiciones Sea ( L, , ) un retículo acotado. a L se dice que a’ L es complementario de a si
a a’ = 1 a a’ = 0 Un retículo acotado L es complementario si todos sus elementos
poseen complementario.
Ejemplos 1) ((S), ) es retículo acotado, distributivo y complementario.
2) (Bn={0, 1}n, PROD) es retículo acotado, distributivo y
complementario.
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 18: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/18.jpg)
18
3) (D , ) es retículo acotado, distributivo y complementario.
4) (D , ) es acotado y distributivo, pero no es complementario.
5) Los siguientes retículos acotados, no distributivos, son
complementarios, pero el complementario del elemento c no es único.
´ , ´ , ´ ´ , ´ , ´
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez
![Page 19: RELACIONES DE ORDEN - Academia Cartagena99 · RELACIONES DE ORDEN Definiciones Una relación R en un conjunto A es una relación de orden si verifica las propiedades reflexiva, antisimétrica](https://reader031.vdocumento.com/reader031/viewer/2022011819/5e9ca92b4b02b82761643b6c/html5/thumbnails/19.jpg)
19
Teorema Sea ( L, , ) un retículo acotado y distributivo. El complementario de cada elemento, si existe, es único. Definición Un álgebra de Boole es un retículo acotado, distributivo y
complementario.
George Boole (1815 1864), en “Las leyes de la verdad” (1854)
utiliza el álgebra para tratar expresiones de lógica proposicional.
Claude Shannon (1916 2001), en su tesis doctoral demostró
cómo utilizar las leyes de la lógica para diseñar circuitos (1938).
Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez