Autoexamen 1. Que una relación R sobre un conjunto A sea antisimétrica significa que . 2. Para demostrar que una relación R en un conjunto infinito...

Autoexamen
1. Que una relación R sobre un conjunto A sea antisimétrica significa que .
2. Para demostrar que una relación R en un conjunto infinito A es antisimétrica, suponga que y demuestre que .
3. Para demostrar que una relación R sobre un conjunto A es no anti-simétrica, usted .
4. Para construir un diagrama de Hasse para una relación de orden parcial, inicie con una gráfica dirigida de la relación en la que todas las flechas apuntan hacia arriba y elimine , y .
5. Si A es un conjunto que es parcialmente ordenado con respecto a un relación y si a y b son elementos de A, decimos que a y b son comparables si y sólo si, o .
6. Una relación en un conjunto A es de orden total si y sólo si, .
7. Si A es un conjunto que es parcialmente ordenado con respecto a una relación y si B es un subconjunto de A, entonces B es una cadena si y sólo si, para todos a y b en B, .
8.5 Relaciones de orden parcial 513
Conjunto de ejercicios 8.5
1. Cada una de las siguientes es una relación sobre {0, 1, 2, 3}. Dibuje los grafos dirigidos para cada relación, e indique qué relaciones son antisimétricas.
a. R1 = {(0, 0), (0, 2), (1, 0), (1, 3), (2, 2), (3, 0), (3, 1)}
b. R2 = {(0, 1), (0, 2), (1, 1), (1, 2), (1, 3), (2, 2), (3, 2)}
c. R3 = {(0, 0), (0, 3), (1, 0), (1, 3), (2, 2), (3, 3), (3, 2)}
d. R4 = {(0, 0), (1, 0), (1, 2), (1, 3), (2, 0), (2, 1), (3, 2), (3, 0)}
2. Sea P el conjunto de todas las personas en el mundo y se define una relación R sobre P como sigue: Para todos x, y P, x R y x no tiene más edad que y. ¿Es R antisimétrica? Demuestre o dé un contraejemplo.
3. Sea S el conjunto de todas las cadenas de a y b. Se define una relación R sobre S como sigue: Para toda t S, s R t l (s) l (t ), donde l (x) denota la longitud de una cadena x. ¿Es R antisimétrica? Demuestre o dé un contraejemplo.
4. Sea R la relación “menor que” sobre el conjunto R de todos los números reales: Para todos x, y R, x R y x y. ¿Es R antisimétrica? Demuestre o dé un contraejemplo.
5. Sea R el conjunto de todos los números reales y se define una relación R sobre R R como sigue: Para todos (a, b) y (c, d ) en R R, (a, b) R (c, d ) ya sea a c o ambas a c y b d. ¿Es R una relación de orden parcial? Demuestre o dé un contraejemplo.
6. Sea P el conjunto de todas las personas que han vivido y se define una relación R sobre P como sigue: Para toda r, s P, r R s r es un antepasado de s o r s. ¿Es R una relación de orden parcial? Demuestre o dé un contraejemplo.
7. Se define una relación R sobre el conjunto Z de todos los enteros como sigue: Para todos m, n Z, m R n cada factor primo de m es un factor primo de n. ¿Es R una relación de orden parcial? Demuestre o dé un contraejemplo.
8. Se define una relación R sobre el conjunto Z de todos los enteros como sigue: Para todos m, n Z, m R n m n es par. ¿Es R una relación de orden parcial? Demuestre o dé un contraejemplo.
9. Se define una relación R sobre el conjunto de todos los números reales R como sigue: Para todos x, y R, x R y x 2 y 2. ¿Es R una relación de orden parcial? Demuestre o dé un contraejemplo.
10. Suponga que R y S son relaciones antisimétricas sobre un conjunto A. ¿Debe R S también ser antisimétrica? Explique.
11. Sea A {a, b} y suponga que A tiene la relación de orden parcial R donde R {(a, a), (a, b), (b, b)}. Sea S el conjunto de todas las cadenas de a y de b y sea el correspondiente orden lexicográfico sobre S. Indique cuáles de los siguientes enunciados son verdaderos y para cada enunciado verdadero cite como una razón los incisos 1), 2) o 3) de la definición de orden lexicográfico dada en el teorema 8.5.1.
a. aab � aaba b. bbab � bba
c. ǫ � aba d. aba � abb
e. bbab � bbaa f. ababa � ababaa
g. bbaba � bbabb
12. Demuestre el teorema 8.5.1.
13. Sea A {a, b}. Describa todas las relaciones de orden parcial sobre A.
14. Sea A {a, b, c}.
a. Describa todas las relaciones de orden parcial sobre A para las que a es un elemento máximo.
b. Describa todas las relaciones de orden parcial sobre A para las que a es un elemento mínimo.
15. Suponga que una relación R sobre un conjunto A es reflexiva, simétrica, transitiva y antisimétrica. ¿Qué puede concluir acerca de R? Demuestre su respuesta.
16. Considere la relación “divide” en cada uno de los siguientes conjuntos A. Dibuje el diagrama de Hasse para cada relación.
a. A = {1, 2, 4, 5, 10, 15, 20}
b. A = {2, 3, 4, 6, 8, 9, 12, 18}
17. Considere la relación “subconjunto” sobre (S) para cada uno de los siguientes conjuntos S. Dibuje el diagrama de Hasse para cada relación.
a. S {0, 1} b. S {0, 1, 2}
18. Sea A un conjunto que es parcialmente ordenado con respecto a una relación y sea a un elemento de A.
a. a es máximo si y sólo si, .
b. a es un elemento mayor de A si y sólo si, .
c. a es mínimo si y sólo si, .
d. a es un elemento menor de A si y sólo si, .
19. Dado un conjunto A que es parcialmente ordenado con respecto a una relación , la relación es un ordenamiento topológico para , si y sólo si, es un y para todos a y b en A si a b entonces .
20. PERT y CPM son utilizados para producir eficientes.
21. Considere la relación “divide” que se define en el conjunto A {1 , 2, 22, 23, . . . , 2n}, donde n es un entero no negativo.
a. Demuestre que esta relación es una relación de orden total sobre A.
b. Dibuje el diagrama de Hasse para esta relación para n 4.
En los ejercicios 22 al 29, determine el elemento mayor, el menor, el máximo y el mínimo para las relaciones en cada uno de los ejercicios mencionados.
22. Ejercicio 16a) 23. Ejercicio 16b) 24. Ejercicio 17a) 25. Ejercicio 17b) 26. Ejercicio 18 27. Ejercicio 19 28. Ejercicio 20 29. Ejercicio 21 30. Cada uno de los siguientes conjuntos está parcialmente ordenado con respecto a la relación “menor que o igual a”, , para números