Aplicaciones de Funciones booleanas[Diapo]

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 De finición y representación de un CPO CONTENIDO Unidad N°4: Estructuras de orden y Diagrama de Hasse 4.1 Definición y representación de un conjunto parcialmente ordenado  Estructuras de orden  Relación de orden parcial  Elementos comparables y orden lineal  Diagrama de Hasse UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Estructuras de orden Introducción Para obtener un grado en alguna especialidad de ingeniería en la UPC, un estudiante debe aprobar un conjunto específico de cursos requeridos, algunos deben aprobarse antes de que se puedan iniciar otros. Dada la estructura de los prerrequisitos del programa, uno podría preguntarse cuál es el número mínimo de periodos que se necesita para cumplir con los requisitos del grado, o cuál es el máximo números de cursos que se pueden llevar en el mismo periodo, o si hay una secuencia en la que un estudiante de tiempo parcial pueda tomar uno de los cursos por periodo. Más adelante en esta sección, mostramos cómo se representa la estructura de los requisitos previos del programa como una relación de orden parcial lo que hace relativamente fácil responder a dichas preguntas. Relación de orden parcial Una relación R en un conjunto A es un orden parcial si R es:  R eflexiva (   R )  A ntisimétrica ( R  R - 1   ) y  T ransitiva ( R 2  R ) Notación Si R es una relación de orden parcial:  ( A, R ) denota a un conjunto parcialmente ordenado.  ( A, R )  ( A ,  ). Definición Sean ( A ,  ) y ( B ,  ) conjuntos parcialmente ordenados: Se define el orden parcial en A  B , denotado por  , como sigue: ( a , b )  ( a ’, b ’)  a  a ’ en A y b  b ’ en B. Este orden es llamado el Orden Parcial Producto. Ejemplo Sea “|” la relación “divide” sobre el conjunto A de enteros positivos: a esta relacionado con b ⟺ a | b Es decir, b = k a para algún entero k Demuestre que “ | ” es una relación de orden parcial en A . Solución | es reflexiva Se debe demostrar que para todo 𝑎 ∈ 𝐴 , 𝑎|𝑎 Suponga que 𝑎 ∈ 𝐴 , entonces 𝑎 = 1. 𝑎 , así 𝑎|𝑎 por definición de divisibilidad. UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 | es antisimétrica Se debe demostrar que para todo 𝑎, 𝑏 ∈ 𝐴 , si 𝑎|𝑏 y 𝑏|𝑎 entonces 𝑎 = 𝑏 Si 𝑎|𝑏 ⟹ 𝑏 = 𝑘 1 𝑎 , si 𝑏|𝑎 ⟹ 𝑎 = 𝑘 2 𝑏 con 𝑘 1 , 𝑘 2 enteros luego 𝑏 = 𝑘 1 𝑎 = 𝑘 1 𝑘 2 𝑏 ⟹ 𝑘 1 𝑘 2 = 1 ⟹ 𝑘 1 = 𝑘 2 = 1 así 𝑎 = 𝑘 2 𝑏 = 1. 𝑏 ⟹ 𝑎 = 𝑏 | es transitiva Se debe demostrar que para todos 𝑎, 𝑏, 𝑐 ∈ 𝐴 , sí 𝑎|𝑏 y 𝑏|𝑐 entonces 𝑎|𝑐 Si 𝑎|𝑏 ⟹ 𝑏 = 𝑘 1 𝑎 y 𝑏|𝑐 ⟹ 𝑐 = 𝑘 2 𝑏 con 𝑘 1 , 𝑘 2 enteros luego 𝑐 = 𝑘 2 𝑘 1 𝑎 y 𝑘 1 𝑘 2 = 𝑘 ⟹ 𝑐 = 𝑘𝑎 así 𝑎|𝑐 Puesto que | es reflexiva, antisimétrica y transitiva, | es una relación de orden parcial Elementos comparables Si ( A ,  ) es un conjunto parcialmente ordenado, los elementos a , b  A, son comparables si: a  b o b  a Ejemplo Sea “|” la relación “divide” sobre el conjunto 𝐴 = {2; 3; 4; 6; 12} : a esta relacionado con b ⟺ a | b Entonces: | = {(2; 2), (2; 4), (2; 6), (2; 12), (3; 3), (3; 6), (3; 12), (4; 4), (4; 12), (6; 6), (6; 12), (12; 12)}  4 y 12 son comparables, porque (4; 12) ∈ |  4 y 6 no son comparables, porque (4; 6) ∉ |, (6; 4) ∉ | Orden lineal Si cada par de elementos en un conjunto parcialmente ordenado A es comparable, se dirá que A es un conjunto linealmente ordenado, y el orden parcial es un orden lineal. Ejemplo Sea R la relación “divide” sobre el conjunto 𝐴 = {2; 4; 8; 16} : a esta relacionado con b ⟺ a | b Entonces: 𝑅 = {(2; 2), (2; 4), (2; 8), (2; 16), (4; 4), (4; 8), (4; 16), (8; 8), (8; 16), (16; 16)}  R es un orden lineal, porque cualquier par de elementos de A, están relacionados (son comparables). UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 Diagrama de Hasse Sea A un conjunto finito y ( A , R ) un conjunto parcialmente ordenado. El diagrama de Hasse se obtiene…