Previous: Homework assignment 10Homework assignment 10 Up: Homework assignmentsHomework assignments Next: Homework assignment 12Homework assignment 12
Document also available in PDF, Postscript, DVI, pure text and LaTeX.

Homework assignment 11



4.1. Relations

Exercise 1  [4 p. 248]   For each of the accompanying figures, give the binary relation on R that describes the shaded area.
Proof: [Correction]
  1. x rho y<-> x>-1
  2. x rho y<-> -2<= y<= 2
  3. x rho y<-> y<= 2-x
  4. x rho y<-> x2/22 + y2/12 <= 1
Exercise 2  [14 p. 250]   Find the reflexive, symmetric, and transitive closure of each of the relations in Exercise 8.
Let S = {0,1,2,4,6}. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and transitivity.
  1. rho = {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6)}
  2. rho = {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4)}
  3. rho = {(0,1), (1,2), (0,2), (2,0), (2,1), (1,0), (0,0), (1,1), (2,2)}
  4. rho = {(0,0), (1,1), (2,2), (4,4), (6,6), (4,6), (6,4)}
  5. rho = Ø
Proof: [Correction] The reflexive, symmetric, and transitive closures of the following sets are:
  1. rho = {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6)}
    1. Reflexive: {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6)}
    2. Symmetry: {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6), (1,0), (2,1), (4,2), (6,4)}
    3. Transitive: {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6), (0,2), (0,4), (0,6), (1,4), (1,6), (2,6)}
  2. rho = {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4)}
    1. Reflexive: {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4), (0,0), (1,1), (2,2), (4,4), (6,6)}
    2. Symmetry: {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4)}
    3. Transitive: {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4), (0,0), (2,2), (2,6), (4,4)}
  3. rho = {(0,1), (1,2), (0,2), (2,0), (2,1), (1,0), (0,0), (1,1), (2,2)}
    1. Reflexive: {(0,1), (1,2), (0,2), (2,0), (2,1), (1,0), (0,0), (1,1), (2,2)}
    2. Symmetry: {(0,1), (1,2), (0,2), (2,0), (2,1), (1,0), (0,0), (1,1), (2,2)}
    3. Transitive: {(0,1), (1,2), (0,2), (2,0), (2,1), (1,0), (0,0), (1,1), (2,2)}
  4. rho = {(0,0), (1,1), (2,2), (4,4), (6,6), (4,6), (6,4)}
    1. Reflexive: {(0,0), (1,1), (2,2), (4,4), (6,6), (4,6), (6,4)}
    2. Symmetry: {(0,0), (1,1), (2,2), (4,4), (6,6), (4,6), (6,4)}
    3. Transitive: {(0,0), (1,1), (2,2), (4,4), (6,6), (4,6), (6,4)}
  5. rho = Ø
    1. Reflexive: {(0,0), (1,1), (2,2), (4,4), (6,6)}
    2. Symmetry: Ø
    3. Transitive: Ø
Exercise 3  [24 p. 251]   Draw the Hasse diagram for each of the two partially ordered sets.
  1. S = {1,2,3,5,6,10,15,30}, such that x rho y <-> x divides y.
  2. S = ({1,2,3}), such that A rho B<-> A included in or equal to B.
Proof: [Correction]
  1. See figure ??.
  2. See figure ??.


Figure 1: Hasse diagram for S = {1,2,3,5,6,10,15,30}, such that x rho y <-> x divides y.


Figure 2: Hasse diagram for S = ({1,2,3}), such that A rho B<-> A included in or equal to B.

Exercise 4  [27 p. 252]   Let rho be a binary relation on a set S. Then a binary relation called the inverse of rho, denoted by rho-1, is defined by x rho-1 y <-> y rho x.
  1. For rho = {(1,2), (2,3), (5,3), (4,5)} on the set N, what is rho-1?
  2. Prove that if rho is a reflexive relation on a set S, then rho-1 is reflexive.
  3. Prove that if rho is a symmetric relation on a set S, then rho-1 is symmetric.
  4. Prove that if rho is a antisymmetric relation on a set S, then rho-1 is antisymmetric.
  5. Prove that if rho is a transitive relation on a set S, then rho-1 is transitive.
  6. Prove that if rho is an irreflexive relation on a set S, then rho-1 is irreflexive.
  7. Prove that if rho is an asymmetric relation on a set S, then rho-1 is asymmetric.
Proof: [Correction]
  1. rho-1 = {(2,1), (3,2), (3,5), (5,4)}
  2. Assume (for all x)(x in S -> (x,x)inrho) is true. Take any x in S. We know that (x,x)inrho, and it follows that (x,x)inrho-1. Then, (for all x)(x in S -> (x,x)inrho-1) is true, and rho-1 is reflexive.
  3. Assume (for all x)(for all y)(x in S /\ y in S /\ (x,y)in rho -> (y,x)in rho) is true. As above, take x and y as above, and assume that (x,y)inrho-1. It follows successively that (y,x)in rho, (x,y)inrho and (y,x)inrho-1. Hence the property (for all x)(for all y)(x in S /\ y in S /\ (x,y)in rho-1 -> (y,x)in rho-1) is true, and rho-1 is symmetric.
  4. Assume (for all x)(for all y)(x in S /\ y in S /\ (x,y)in rho /\ (y,x)in rho -> x = y) is true. As above, by taking two elements x, y of S, we get that x rho y <-> y rho-1 x. is true, so rho-1 is antisymmetric.
  5. Assume (for all x)(for all y)(for all z)(x in S /\ yin S /\ z in S /\ (x,y) in rho /\ (y,z) in rho -> (x,z)inrho). Same thing as above by taking x, y and z in S.
  6. Assume (for all x)(x in S -> (x,x)not inrho) is true. Then (x,x)not inrho-1 is obviously true for any x, so rho-1 is antireflexive.
  7. Same as above.
Exercise 5  [29 p. 252]  
  1. Let (S,rho) be a partially ordered set. Then rho-1 can be defined as in Exercise 27. Show that (S,rho-1) is a partially ordered set, called the dual of (S,rho).
  2. If (S,rho) is a finite, partially ordered set with the Hasse diagram shown, draw the diagram of the dual of (S,rho).
  3. Let (S,rho) be a totally ordered set and let X={(x,x)|xin S}. Show that the set difference rho-1-X equals the set rho'.
Proof: [Correction]
  1. If (S,rho) is a poset, then rho is reflexive, antisymmetric and transitive. By the exercise above, rho-1 is also reflexive, antisymmetric and transitive. Hence, (S,rho-1) is a also poset.
  2. See figure ??.


    Figure 3: The dual of the Hasse diagram shown in Exercise 29 page 252.

Exercise 6  [30 p. 252]   A computer program is to be written that will generate a dictionary or the index for a book. We will assume a maximum length of n characters per word. Thus, we are given a set S of words of length at most n, and we want to produce a linear list of these words arranged in alphabetical order. There is a natural total ordering on alphabetic characters (a b, b c, etc.), and we shall assume our words contain only alphabetic characters. We want to define a total ordering on S called a lexicographical ordering that will arrange the members of S alphabetically. The idea is to compare two words X and Y character by character, passing over equal characters. If at any point the X-character alphabetically precedes the corresponding Y-character, then X precedes Y; if all characters in X are equal to the corresponding Y characters but we run out of characters in X before characters in Y, then X precedes Y. Otherwise, Y precedes X.

Formally, let X=(x1,x2,...,xj) and Y=(y1,y2,...,yk) be members of S with j<= k. Let beta (for blank) be a new symbol, and fill out X with k-j blanks on the right. X can now be written (x1,x2,...,xk). Let beta precede any alphabetical character. Then X Y if x1 != y1 and x1 y1 or x1=y1, x2 = y2, ..., xm = ym (m<= k), xm+1!= ym+1, and xm+1 ym1. Otherwise, Y X.

Note that because the ordering on alphabetical characters in a total ordering, if Y X by ``otherwise,'' then there exists m<= k such that x1 = y1, x2 = y2, ..., xm = ym, xm+1!= ym+1 and ym+1 xm+1.

  1. Show that on S as defined above is a total ordering.
  2. Apply the total ordering described to the words boo, bug, be, bah, and bugg. Note why each word precedes the next.
Proof: [Correction]
  2. We obtain the list bah, be, boo, bug, bugg. The decision takes place at the second letter for bah and be. Samething for be and boo, boo and bug. For bug and bugg, we run out of letters in the first one, and so bug is before bugg.
Exercise 7  [37 p.256]   Let S = N × N and let rho be a binary relation on S defined by (x,y) rho (z,w) <-> x+w = z + y. Show that rho is an equivalence relation on S and describe the resulting equivalence classes.
Proof: [Correction]
  1. rho is reflexive. Indeed, take (x,y)in S. Then, obviously x+y=x+y, and so (x,y)rho(x,y).
  2. rho is symmetric since x+w=z+y is equivalent to z+y=x+w
  3. rho is transivite. Indeed, take (x,y), (z,w), (s,t) in S, and assume that (x,y)rho(z,w) and (z,w)rho(s,t). Then, x+w=z+y, and z+t=s+w. By adding the two equations, we get x+t+(z+w)=s+y+(z+w). The z+w cancels out, and we get x+t=s+y, and thus (x,y)rho(s,t), as expected.

4.2. Topological Sorting

Exercise 8  [1 p. 263]   The following tasks are required in order to assemble a bicycle. As the manufacturer, you must write a list of sequential instructions for the buyer to follow. Will the sequential order given below work? Give another sequence that could be used.
Task Prerequisite Tasks
1. Tightening frame fittings None
2. Attaching handle bars to frame 1
3. Attaching gear mechanism 1
4. Mounting tire on wheel assembly None
5. Attaching wheel assembly to frame 1,4
6. Installing brake mechanism 2,3,5
7. Adding pedals 6
8. Attaching seat 1
9. Adjusting seat height 7,8
Proof: [Correction] Yes, the sequential order given above will work (it suffices to check all the constraints). Other sequences which could be used are: (1,4,2,3,8,5,6,7,9), (1,4,2,8,3,5,6,7,9), (1,4,3,2,8,5,6,7,9), (1,4,3,8,2,5,6,7,9), (1,4,8,2,3,5,6,7,9), (1,4,8,3,2,5,6,7,9), {(4,1,2,3,8,5,6,7,9), (4,1,2,8,3,5,6,7,9), (4,1,3,2,8,5,6,7,9), (4,1,3,8,2,5,6,7,9), (4,1,8,2,3,5,6,7,9), and (4,1,8,3,2,5,6,7,9)

Exercise 9  [3 p. 264]   Construct a PERT chart from the following task table.
Task Prerequisite Tasks Time to Perform
1 2 4
2 3 2
3 8 5
4 3 2
5 4,7 2
6 5 1
7 3 3
8 None 5
Proof: [Correction] See figure ??.


Figure 4: The PERT chart for Problem 3 on pg. 264

Exercise 10  [5 p. 264]   Compute the minimum time to completion and the nodes on the critical path for the problem in Exercise 3.
Proof: [Correction] The minimum time to completion is 16, which is along the path (8,3,7,5,6), as seen clearly in figure ??.

Exercise 11  [6p. 264]   Do a topological sort on the partially ordered set shown in the accompanying figure.
Proof: [Correction] For example: G, H, F, A, C, D, B, E.

4.4. Functions

Exercise 12  [2 p. 301]   The accompanying figure illustrates various binary relations from R to R. Which are functions? For those that are functions, which are onto? Which are one-to-one?
Proof: [Correction] Which are functions: a, c, and d. Which are onto: c and d. Which are one-to-one: a, b, and c.

Exercise 13  [9 p. 302]   Let f:R->R be defined by f(x)=xn, where n is fixed, positive integer. For what values of n is f bijective?
Proof: [Correction] For f to be bijective, n must be a positive odd integer.
Previous: Homework assignment 10Homework assignment 10 Up: Homework assignmentsHomework assignments Next: Homework assignment 12Homework assignment 12
Homework assignment 11 / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:29 2003