• University of Massachusetts, Boston

• CS 220

CS 220-02 Homework #10 Question 1: Family relations continued a) [45 pts] Use the answer to Question 1c of the previous Homework as your starting point for computing the transitive closure of R. Apply the Boolean power method we discussed in class. Once you have derived the matrix representing the transitive closure of R, also translate it into set notation and digraph notation. R 2 = 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 R 3 = 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 R 4 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Since R 4 is all zeros, R 5 and R 6 will also be all zeros. No need to calculate them. The transitive closure matrix is R 1 ⋃ R 2 ⋃ R 3 ⋃ R 4 ⋃ R 5 ⋃ R 6 = R* R* = 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 R* = {(Sarah, Judy), (Sarah, Frank), (Sarah, Lola), (Sarah, Kira), (Sarah, Reuben), (Frank, Lola), (Frank, Kira), (Frank, Reuben), (Kira, Reuben)} b) [10 pts] What does the transitive closure of R specify? What name could you give it, if you considered even larger family trees including many generations? The transitive closure relation indicates if the first person is an ancestor of the second person. So we can call the relation “ancestor”. (There can be other correct answers here) Question 2: Count the Relations a) [15 pts] How many different equivalence relations can we define on the set A = {c, d, e}? This is equal to the number of possible partitions of A. Those are: P = {{c}, {d}, {e}} P = {{c}, {d, e}} P = {{d}, {c, e}} P = {{e}, {c, d}} P = {{c, d, e}} There are 5 possible equivalence relations. b) [15 pts] How many different partial orderings can we define on the set A = {x, y}? R = {(x, x), (y, y)} R = {(x, x), (y, y), (x, y)}