Estudiante

Solo disponible en BuenasTareas
  • Páginas : 9 (2180 palabras )
  • Descarga(s) : 7
  • Publicado : 20 de mayo de 2010
Leer documento completo
Vista previa del texto
Departamento de Matemática Aplicada. Facultad de Informática. UPM.

MATEMÁTICA DISCRETA I Curso 09-10

RELACIONES DE ORDEN. ÁLGEBRAS DE BOOLE Relaciones de orden 1) En el conjunto A = (R-{0}) x R se define la relación: (x1,y1) R (x2,y2) ⇔ y1/x1 = y2/x2 y x1 ≤ x2 a) Demostrar que es una relación de orden, y estudiar si es un orden total. b) Representar el conjunto de los puntos comparables conel elemento (1,1). 001, 111, 010, 011, 000 y 100 2) Determina el orden lexicográfico de las siguientes cadenas de bits: basado en el orden 0 ≤ 1. Dibujar el diagrama de Hasse de estas cadenas, ahora con el orden producto. 3) Sea S = {1, 2, 3, 4}. Con respecto al orden lexicográfico basado en el orden usual “≤“ : a) Encontrar todos los pares en S x S anteriores a (2,3). b) Encontrar todos lospares en S x S posteriores a (3,1). c) Dibujar el diagrama de Hasse de (S x S, ≤Lex). 4) Hallar los elementos maximales, minimales, máximo y mínimo (si los hay) para los siguientes conjuntos con el orden dado por el diagrama de Hasse:
a) b) a b d c e d a b c e

c)

a

d) a b

b d e

c c d e

f

5) Hallar cotas superiores, cotas inferiores, supremo e ínfimo del conjunto B (si los hay) encada uno de los siguientes casos:
a) a c d f B={c,d,e} e 6 g 8 B={4,5,6} 7 b 3 4 5 3 2 4 b) 1 2 c) 1

6 5 B={2,3,4}

6) Representar el diagrama de Hasse de los siguientes conjuntos ordenados y hallar los elementos notables de los subconjuntos señalados: a) (D60, | ), A = {2, 5, 6, 10, 12, 30} y B = {2, 3, 6, 10, 15, 30} b) (D48, | ), A = {2, 4, 6, 12} y B = {3, 6, 8, 16} c) (D40, | ), A ={4, 5, 10} y B = {2, 4, 8, 20}

1

Departamento de Matemática Aplicada. Facultad de Informática. UPM.

MATEMÁTICA DISCRETA I Curso 09-10

7) Hallar, si los hay, los elementos maximales, minimales, máximo y mínimo para los siguientes conjuntos ordenados: (P(X),⊂); ((0,1),≥); (|N,| ); (|N-{1},|). 8) En cada uno de los casos siguientes, dígase si el conjunto X tiene o no una cota inferior, ysi tiene alguna hállese su ínfimo si existe: a) X={x∈Z; x2≤16} b) X={x∈Z; x=2y para algún y∈Z} c) X={x∈Z; x2≤100x} 9) En (|N,| )x(|N,| ) se considera el orden lexicográfico . Determinar, si existen, las cotas superiores, cotas inferiores, supremo e ínfimo del conjunto: A = {(2, 1), (3, 4)}. (x,y) < (x',y') ⇔ x ≤ x' e y ≤ y' 10) En R se considera la relación de orden 2 2 Hallar los elementosmaximales y minimales, supremo e ínfimo de C = {(x, y); x + y = 1}. 11) Se considera en D48 × N el orden lexicográfico correspondiente a tomar el orden divisibilidad en el primer factor y el orden usual en el segundo factor. Sea S = {(2, 2), (2, 3), (3, 2), (6, 3), (6, 1), (4, 2)}. Se pide hallar, si existen, las cotas superiores e inferiores, elementos maximales y minimales, máximo, mínimo, supremo eínfimo de S. 12) Dado el orden parcial del siguiente diagrama de Hasse, obtener un orden total que lo contenga. ¿Cuántos pueden obtenerse?
i
2

h f e c a b d g

13) Sea T = {a, b, c, d, e, f, g} la lista de tareas para realizar un trabajo, de las que se sabe que unas preceden inmediatamente a otras de la siguiente forma: f ≤ a, f ≤ d, e ≤ b, c ≤ f, e ≤ c, b ≤ f, e ≤ g, g ≤ f. Hallar el ordenparcial. ¿Qué tareas pueden realizarse independientemente? Construir un orden si el trabajo lo realiza sólo una persona. 14) En (D10,| ) x (D18,| ) se considera el orden lexicográfico. Hallar las cotas superiores, cotas inferiores, supremo e ínfimo, si existen, del subconjunto S = {(2, 2), (2, 3)}. Dibujar el diagrama de Hasse. Se define f : D10 x D18 → D180 por f(a, b) = ab. ¿es f inyectiva?, ¿essuprayectiva? Retículos 1) Dado un conjunto parcialmente ordenado (A, R), estudiar si son verdaderas o falsas las siguientes afirmaciones: a) Si (A, R) es retículo, entonces es totalmente ordenado. b) Si (A, R) es totalmente ordenado, entonces es retículo. 2) Estudiar cuales de los siguientes conjuntos ordenados son retículos:

3) Obtener los diagramas de Hasse de todos los retículos, salvo...
tracking img