Discrete Mathematics for Computer Science

216 CHAPTER^3 Relations

7. Prove that {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (1, 5), (2, 4), (2, 6), (4, 6), (6, 4),
   (6, 2), (4, 2), (5, 1)} is an equivalence relation. Find the distinct equivalence classes
   for this equivalence relation.


8. If A = {1, 2, 3, 4, 5} and R is the equivalence relation on A that induces the partition

A = {1,2} U {3,4} U {5}

what is R?

9. What are the minimal and maximal elements in the following diagram of a partial
   order?

a b

<

Of

d e

10. What is the difference between a maximal element and a maximum element in a partial
    order on a set X?

3.12.3 Review Questions

1. Prove or find a counterexample to the following conjectures about relations R 1 and R 2.
   (a) If R, and R 2 are reflexive, then R 1 o R 2 is reflexive.
   (b) If R 1 and R 2 are irreflexive, then R 1 o R 2 is irreflexive.
   (c) If RI and R 2 are symmetric, then RI o R 2 is symmetric.
   (d) If R 1 and R 2 are antisymmetric, then RI o R 2 is antisymmetric.
   (e) If R, and R 2 are transitive, then RI o R 2 is transitive.


2. For x, y E Z, define the relation R as x R y if and only if x • y is odd. Is R Reflexive?
   Symmetric? Transitive? Prove, or give a counterexample.


3. Let R be a relation defined on (a, b, c, d} such that

R = {(a, a), (b, b), (c, a), (d, d), (a, b), (b, d), (a, d)}

Find the symmetric closure of R.

4. Find the transitive closure of the relation R = {(1, 2), (2, 3), (3, 4), (4, 1)}. Show R'
   for all values of i that give new elements of the transitive closure.


5. Define the relation R on R x IR such that for any (x, y), (u, v) E 1R x 1R, we have
   (x, y) R (u, v) if and only if y = v. Prove that R is an equivalence relation.

6. Let R be a binary relation on the set of all strings of O's and l's such that R = { (x, y)

strings x and y contain the same number of O's}. Is R Reflexive? Symmetric? Anti-

symmetric? Transitive? An equivalence relation?

7. The oddness or evenness of an integer is called its parity. Prove that the relation "have
   the same parity" is an equivalence relation. Find the distinct equivalence classes of this
   equivalence relation.


8. Four friends-Bill, Chuck, Maria, and Susie-are seated around a table. Define a re-

lation ARRANGE to contain a pair (Arrl, Arr2) of seating arrangements for these four

people around a round table ifArrl can be obtained from Arr2 by shifting each person