From the Text

Complete the following questions from the text:

• Section 8.4: 22, 24
• Section 8.5: 2, 16, 46, 58, 60, 64
  • Question 46: if not a partition, briefly say why.
  • Question 58: You can expand the definition of “equivalence” to include any combination of rotations and reflexions. I think there 10 equivalence classes.
  • Question 64: The wording is a little funny: start with a relation; take its transitive closure; take the reflexive closure of the result; take the symmetric closure of that result. Is the final result an equivalence relation? Hint: No. Come up with a counter-example.
• Section 8.6: 4, 12, 22(a,c), 34(a,b,c,d)

Questions

1. Use the naïve algorithm (the $\Theta(n^4)$ one) to find the transitive closure of the relation represented by: $$\mathbf{M}_R=\left[\begin{smallmatrix}0&1&0 \\ 1&0&1 \\ 0&0&0 \end{smallmatrix}\right]$$
2. Use Warshall's Algorithm to find the transitive closure of the relation represented by: $$\mathbf{M}_R=\left[\begin{smallmatrix}1&1&1 \\ 0&0&0 \\ 0&1&0 \end{smallmatrix}\right]$$ Draw the graph of the relation represented by the matrix, and update it as you work through the algorithm.
3. Show that if $(A_1,\preceq_1)$ and $(A_2,\preceq_2)$ are total orders, then $A_1\times A_2$ is totally-ordered by lexicographic ordering. [We already know its a partial order. You only need to show that it's total.]