CSE 321 Assignment #7
Autumn 1997

Due: Wednesday, December 3, 1997.

Reading assignment: Read the text, Discrete Mathematics and Its Applications Sections 6.1-6.5.

Problems:

1. page 364, Problem 4.

2. page 366, Problem 28.

3. page 366, Problem 36. (You may use without proof the fact that the composition of relations is associative, i.e. (R o S) o T = R o (S o T) for all relations R, S, and T on a set A.)

4. page 380, Problem 8.

5. Draw the graphs representing the relations from Problem 8 above.

6. page 423, Problem 10.

7. page 400, Problem 10.

8. (Bonus) Let M be a 01-matrix and let I be the identity matrix. Prove that for all n >= 0, (I v M)^(n) = I v M v M^(2) v ... v M^(n). You will need to use the fact that L (M v N)= L M v L N (where I've written matrices next to each other to indicate boolean matrix multiplication.)