Discrete Mathematics for Computer Science

Chapter Review 215

3.12.2 Starting to Review

1. Let A = {1, 2, 3, 41. Define a relation R of A as R = {(1, 3), (4, 2), (2, 4), (2, 3),

(3, 1)}. Which of the following properties does this relation not possess?

(a) Reflexive

(b) Symmetric

(c) Transitive

(d) All of the above

2. Which of the following relations defined on X = { 1, 2, 31 is an equivalence relation?
   (a) {(1, 2), (2, 2), (3, 3)}
   (b) [(1, 1), (2, 2), (2, 2), (2, 1), (3, 3), (1, 1)}
   (c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 1), (3, 3), (3, 1)}
   (d) All of the above


3. Let R be a relation on a set S. R is circular if, for x, y, z e S, whenever x R y and
   y R z, it follows that z R x. Which of the properties do a reflexive and circular relation
   possess?
   (a) Irreflexive
   (b) Transitive
   (c) Antisymmetric
   (d) None of the above


4. Which of the following relations defined on X = {1, 2, 3} is a partial order?
   (a) {(1, 1), (2, 2), (3, 3))
   (b) {(1, 2), (1, 2), (2, 2), (3, 3)}
   (c) {(1, 1), (2, 1), (2, 2), (1, 3), (3, 3)1
   (d) All of the above


5. Given the following graph of a partial order R on X = 11, 2, 3, 4, 51, list all the ordered
   pairs (x, y) such that x R y.

4

3 5

2

6. Let R be a partial order on a set X, and let x E X. The element x is a minimal element
   in R if:
   (a) x <yforallyrX.
   (b) x < y for all y E X such that y 0 x and y is comparable to x.
   (c) x < y for all y such that y E X and y is comparable to x.
   (d) None of the above.