MA265 Árboles no dirigidos [Libro]

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Retículas y Álgebras booleanas CONTENIDO Unidad N°4: ESTRCUTURAS DE ORDEN Y ÁLGEBRA DE BOOLE 4.3 Retículas y Álgebras booleanas ▪ Propiedades ▪ Retícula acotada ▪ Retícula distributiva ▪ Retícula complementada UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Retículas y Álgebras booleanas Retículas Una retícula es un conjunto parcialmente ordenado ( L ,  ) tal que cada subconjunto { a , b } de dos elementos tiene una mínima cota superior y una máxima cota inferior . Notación • 𝑀𝐶𝑆({𝑎, 𝑏}) = 𝑎 ∨ 𝑏 es llamada unión de a y b . • 𝑀𝐶𝐼({𝑎, 𝑏}) = 𝑎 ∧ 𝑏 es llamada conjunción de a y b . Ejemplo 1 Nota: para verificar que es retícula, solo debemos tomar los vértices no comparables. Definición Sea ( L ,  ) una retícula. Un subconjunto no vacío S de L es una sub-retícula de L si: a  b  S y a  b  S siempre que a  S y b  S. Ejemplo 2 𝑆 1 = {𝑎, 𝑏, 𝑐, 𝑑} sí es una subretícula de L 𝑆 2 = {𝑎, 𝑏, 𝑐, 𝑔} no es una subretícula de L UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 Propiedades Sea L una retícula. Entonces para todo a y b en L : • a  b = b si y solo si a  b • a  b = a si y solo si a  b • a  b = a si y solo si a  b = b • a  a = a ; a  a = a (Idempotencia) • a  b = b  a ; a  b = b  a (Conmutativa) • a  ( b  c ) = ( a  b )  c ; a  ( b  c ) = ( a  b )  c (Asociativa) • a  ( a  b ) = a ; a  ( a  b ) = a (Absorción) Retícula acotada Una retícula L está acotada si tiene un elemento máximo I y un elemento mínimo 0. Ejemplo 3 Teorema Sea L = { a 1 , a 2 , ... , a n } una retícula finita, entonces L es acotada. Retícula distributiva Una retícula L es distributiva si para cualesquiera elementos a , b y c en L , se tiene: a  ( b  c ) = ( a  b )  ( a  c ) a  ( b  c ) = ( a  b )  ( a  c ) UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 Ejemplo 4 Retícula complementada Complemento Sea L una retícula acotada con elemento máximo I y elemento mínimo 0, y sea a  L . Un elemento a’  L es un complemento de a , si: a  a’ = I y a  a’ = 0. Definición Una retícula L es complementada si está acotada y si todo elemento en L tiene complemento. Teorema Sea L una retícula distributiva acotada. Si un elemento tiene complemento, este es único. Observación: Si L es una retícula acotada y tiene un elemento con más de un complemento, entonces L no es distributiva. Ejemplo 5 La siguiente retícula es complementada debido a que cada elemento tiene complemento. Además del teorema anterior, esta retícula no es distributiva, pues tiene elementos con más de un complemento (de la tabla los elementos b , c , d y e tienen dos complementos) No es una retícula distributiva, pues: 𝑐 ∨ (𝑒 ∧ 𝑑) ≠ (𝑐 ∨ 𝑒) ∧ (𝑐 ∨ 𝑑) Elemento Complemento a f b c , e c b , d d c , e e b , d f a UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 5 Ejemplo 6 En el conjunto D 90 , formado por los divisores de 90, definimos: 𝑎 | 𝑏 ↔ 𝑎 es divisor de b. a) Justifique, por qué la relación 𝑅 es una retícula. b) Halle la MCI y la MCS de {6, 15}. c) Halle la MCI y la MCS de {9, 10}. d) Si 𝑎 y 𝑏 son dos divisores de 90, ¿qué representa la MCI de { 𝑎 , 𝑏 } ? e) Si 𝑎 y 𝑏 son dos divisores de 90, ¿qué representa la MCS de { 𝑎 , 𝑏 } ? f) Determine el complemento de los siguientes elementos: 5, 6, 9, 15 y 90. Solución 𝐷 90 = {1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90} a) Cada subconjunto de dos elementos de D 90 tiene MCS y MCI (Realice el diagrama de Hasse). b) MCI = 3, MCS = 30. c) MCI = 1, MCS = 90. d) Representa el MCD (𝑎, 𝑏) . e) Representa el MCM (𝑎, 𝑏) . f) MCD (5, 𝑥) = 1 y MCM (5, 𝑥) = 90 → 𝑥 = 18 . MCD (6, 𝑥) = 1 y MCM (6, 𝑥) = 90 → 6 no tiene complemento. MCD (9, 𝑥) = 1 y MCM (9, 𝑥) = 90 → 𝑥 = 10 . MCD (15, 𝑥) = 1 y MCM (15, 𝑥) = 90 → 15 no tiene complemento. MCD (90, 𝑥) = 1 y MCM (90, 𝑥) = 90 → 𝑥 = 1…