0.1 Discrete structures relation  (Page 12/13)

Questions and exercises

1. Indicate which of the following statements are correct and which are not.

a.<<1,2>,<1,3>>is an ordered pair.

b. Any set of ordered pair is a binary relation.

c. {<1,2>,<1,3>,<2,3>} is less than relation on {1,2,3}

d. {1,2} × {3} = {<1,3>,<2,3>,<3,1>,<3,2>}

2. Indicate which of the following statements are correct and which are not.

a. Any set of quadruplets is a 4-ary relation.

b. {<1,2,1>} is a ternary relation on the set of natural numbers.

c. {1,2} × {3} × {4,5} = {1,2} × {4,5} × {3}

d. {<1,2,{1,2}>,<2,3,{2,3}>,<3,1,{1,3}>} is a ternary relation.

3. Indicate which of the following statements are correct and which are not.

a. {<1,2>,<2,3>} is equal to {<1,2>,<2,3>} as a relation.

b. The relation {<1,1>,<2,2>} over {1,2} is equal to the relation {<1,1,1>,<2,2,2>} over {1,2}.

c. The relation {<1,2>,<2,1>} over {1,2} is equal to the relation {<1,2>,<2,1>} over {1,2,3}.

d. The relation {<1,2>,<2,1>} over {1,2} is equal to the relation {<1,2>,<2,1>,<1,2>} over {1,2}.

4. For the graph in Figure 11, indicate which of the following statements are correct and which are not.

a. The in-degree of vertex 2 is 3.

b. Every partial digraph with vertices 2,4 and 5 is connected.

c. 22 is a loop.

d. 213 is a simple directed path.

5. Indicate which of the following statements are correct and which are not.

a. A binary relation on a set can be neither symmetric nor anti-symmetric.

b. For a transitive relation, only vertices connected by a directed path are connected by an arc.

c. If a relation R is symmetric, then for every<a,b>in R<b,a>must be in R.

d. A symmetric relation cannot be transitive an irreflexive at the same time.

6. Indicate which of the following statements are correct and which are not.

a. The intersection of less-than-or-equal-to and greater-than-or-equal-to relations is quality relation.

b. If B is a binary relation on a set A and T is a ternary relation on A, union of B and T is a relation.

c. If<a,b>is in RR, then b can reached from a in 2 or less hops in the digraph of R.

d. The square of less-than-or-equal-to relation is equal to less-than-or-equal-to relation.

7. Indicate which of the following statements are correct and which are not.

a. The symmetric closure of a relation is a relation, and it is symmetric.

b. The transitive closure of a relation contains all the ordered pairs of the relation, and possibly more.

c. If a relation is symmetric, then it is its own symmetric closure.

d. If the digraph of a relation is a simple cycle, then its transitive closure is the universal relation.

8. Indicate which of the following statements are correct and which are not.

a. An equivalence relation must be symmetric.

b. An equivalence relation can be antisymmetric.

c. Objects in different equivalence classes may be related to each other.

d. An equivalence relation is the universal relation on each of its equivalence classes.

9. Indicate which of the following statements are correct and which are not.

a. A total order is a partial order.

b. The partial order can be reconstructed from a Hasse diagram.