MA265 Sesión 7.1 Retículas [Diapo]

Matemática Discreta Profesores MA265 Ejercicios de Relaciones de Orden Parcial 1. Sea 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓} y R una relación sobre el conjunto A, cuyos elementos se muestran abajo: 𝑅 = {(𝑎, 𝑎), (𝑎, 𝑐), (𝑎, 𝑑), (𝑏, 𝑏), (𝑏, 𝑑), (𝑐, 𝑐), (𝑑, 𝑑), (𝑒, 𝑎), (𝑒, 𝑏), (𝑒, 𝑐), (𝑒, 𝑑), (𝑒, 𝑒), (𝑓, 𝑏), (𝑓, 𝑑), (𝑓, 𝑓)} a) ¿R es una relación de orden parcial? Justifique su respuesta. b) En caso de que R sea una relación de orden parcial, trace su diagrama de Hasse c) ¿Los elementos e y d son comparables? Justifique su respuesta. d) ¿Los elementos a y b son comparables? Justifique su respuesta. 2. Sea A = {a, b, c, d, e} y S una relación sobre el conjunto A, cuya representación matricial se indica: 𝑀 𝑆 = [ 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1] a) Verifique que S es una relación de orden parcial. b) Trace el diagrama de Hasse del conjunto parcialmente ordenado (A, S). 3. Sea 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓} y R una relación de orden parcial definida sobre el conjunto A, cuyo diagrama de Hasse se muestra a la derecha: a) Determinar R en notación de conjuntos. b) ¿Los elementos b y e son comparables? Justifique su respuesta. c) ¿Los elementos a y f son comparables? Justifique su respuesta. d) Si el diagrama de Hasse representa la relación de orden parcial “x divisor de y” para los números 30, 15, 6, 5, 3, 1, identificar los valores de a, b, c, d, e y f respectivamente. 4. Sea el conjunto 𝐴 = {1, 2, 4, 8, 16} . Sea R una relación en A definida por: 𝑥𝑅𝑦 ⟺ 𝑥 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑜𝑟 𝑑𝑒 𝑦 a) Determine los elementos de la relación R. b) ¿Es R un orden parcial? Justifique su respuesta. c) ¿Es R un orden lineal? es decir, ¿es el conjunto A un conjunto linealmente ordenado? Justifique su respuesta. d) ¿Los elementos 8 y 2 son comparables? e) Trace el Diagrama de Hasse del conjunto parcialmente ordenado (A, R). a R b f e d Matemática Discreta 2 Profesores MA265 5. El siguiente dígrafo representa la relación R definida en el conjunto A = {a, b, c, d, e}. a) Verifique que R es una relación de orden parcial. b) Trace el diagrama de Hasse del conjunto parcialmente ordenado (A, R). 6. Sea 𝐴 = {𝜙, {1}, {3}, {1, 2}, {1, 3}} . Sea R la relación en A definida por: 𝑥𝑅𝑦 ⟺ 𝑥 ⊆ 𝑦 a) Encuentre los elementos de la relación R. b) ¿Es R un orden parcial? Justifique su respuesta. c) ¿Es R es un orden lineal? es decir, ¿es el conjunto A un conjunto linealmente ordenado? Justifique su respuesta. d) Trace el diagrama de Hasse del conjunto parcialmente ordenado (A, R). 7. Sea 𝐴 = {𝑎; 𝑏; 𝑐; 𝑑; 𝑒; 𝑓} y R una relación sobre el conjunto A, cuya representación matricial es: 𝑀 𝑅 = [ 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1] a) ¿R es una relación de orden parcial? Justifique su respuesta. b) En caso de que R sea una relación de orden parcial, trace su diagrama de Hasse. 8. Sea 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔} y R una relación sobre el conjunto A, cuya matriz se muestra abajo: a) ¿R es una relación de orden parcial? Justifique su respuesta. b) En caso de que R sea una relación de orden parcial, trace su diagrama de Hasse c) ¿Los elementos c y b son comparables? Justifique su respuesta. d) ¿Los elementos a y d son comparables? Justifique su respuesta. 𝑀 𝑅 = 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔 [ 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1] a b d e c Matemática Discreta 3 Profesores MA265 9. Sea P el conjunto de todas las personas en el mundo y se define una relación R sobre P como sigue: Para todo 𝒙 𝑹 𝒚 ⟺ 𝒙 no tiene más edad que 𝒚 . Verifique que R es una relación de orden parcial. 10. En el conjunto D 6 formado por los divisores positivos de 6: a) Verifique que (D 6 , | ) es una relación de orden parcial. b) Trace su diagrama Hasse. 11. Sea P la potencia de un conjunto. a) Demuestre que (P ({a, b, c}), ⊆ ) es una relación de orden parcial. b) Trace su diagrama de Hasse. c) ¿es un orden lineal? 12. En el conjunto D n…