MA265 Árboles no dirigidos [Respuestas]

Matemática Discreta • Retículas Unidad 2: E structuras de orden, álgebra de Boole. Orientación de la semana 06 ANTES: GNP: (Lunes 05 a miércoles 07 de mayo ) Aprendizaje autónomo Autorreflexivo AAA2: Funciones booleanas , este tema será evaluado en 3 partes (Antes , durante y después) 1 2 4 Asistencia con el AAD Subir sus dos ejercicios antes de la sesión acordada con el AAD en aula . Durante: EAAA2: ( miércoles 07 a viernes 09 de mayo) Sin Sumadi Después: EAAA2 con evidencia ( sábado 10 hasta el domingo 11 de mayo) Sin Sumadi 3 Talleres Exposición grupal del avance del proyecto Sesión 6.1 (Segundo entregable hasta el domingo 10 de mayo) Evaluación Remedial EU1 ( Sábado 10 de mayo desde las 00:00 horas hasta las 23:50 horas) Control virtual 2 de entrenamiento ( Del sábado 10 a las 00:00 horas al domingo 11 de mayo a las 23:50 horas) Logro de la sesión Al finalizar la sesión, estarás preparado para: Determinar si una relación de orden parcial es una retícula. Además, de identificar los diferentes tipos de retículas. Bibliografía • Profesores UPC – Libro digital – Retículas y Algebras Booleanas • Johnsonbaugh R. (2005). Matemáticas Discretas, sexta edición. Editorial Pearson, México. • Epp S. (2012). Matemáticas discretas con aplicaciones . México, D.F. Cengage Learning. Bibliografía textos de consulta. Bibliografía Multimedia https://bit.ly/3fC29Pr 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. • MCS({ a , b }) = a  b es llamada unión de a y b . • MCI({ a , b }) = a  b es llamada conjunción de a y b . a b d c Es retícula Nota: para verificar que es retícula, solo debemos tomar los vértices no comparables a b f c No es retícula e d Ejemplo 01: Ejemplo 02: Definición Subretículas Sea ( L ,  ) una retícula. Un subconjunto no vacío S de L es una subretícula de L si: a  b  S y a  b  S siempre que a  S y b  S. 𝑺 𝟏 = 𝒂, 𝒃, 𝒄, 𝒅 sí es una subretícula de L 𝑺 𝟐 = 𝒂, 𝒃, 𝒄, 𝒈 no es una subretícula de L Definición. Ejemplo: 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 a b d c Retícula acotada Retícula no acotada 1 2 3 4 Teorema . Sea L = { a 1 , a 2 , ... , a n } una retícula finita, entonces L es acotada. Una retícula L está acotada si tiene un elemento máximo 1 y un elemento mínimo 0. Ejemplo: Definición: Retícula 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 ) a b f c e d Definición: Retícula distributiva Ejemplo: No es una retícula distributiva, pues: 𝑐 ∨ (𝑒 ∧ 𝑑) ≠ (𝑐 ∨ 𝑒) ∧ (𝑐 ∨ 𝑑) Retícula distributiva No son retículas distributivas la retícula diamante y la retícula pentágono: a e d b c Retículas no distributivas Por lo tanto, una retícula NO SERÁ distributiva si contiene a alguna de esas retículas (diamante o pentágono). a e c b d