December 1999
MA214 : DISCRETE MATHEMATICS

QUESTION 2

Total Marks: 15 Marks

• Question 1
• Question 3
• Question 4
• Question 5
• Cover Page

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 2

Consider the following relations on the set {1 ,2 ,3 ,4 }

R 1 ={(1 ,1 ),(1 ,2 ),(2 ,1 ),(2 ,2 ),(3 ,4 ),(4 ,1 ),(4 ,4 )}

R 2 ={(1 ,1 ),(1 ,2 ),(2 ,1 )}

R 3 ={(1 ,1 ),(1 ,2 ),(1 ,4 ),(2 ,1 ),(2 ,2 ),(3 ,3 ),(4 ,1 ),(4 ,4 )}

R 4 ={(2 ,1 ),(3 ,1 ),(3 ,2 ),(4 ,1 ),(4 ,2 ),(4 ,3 )}

R 5 ={(1 ,1 ),(1 ,2 ),(1 ,3 ),(1 ,4 ),(2 ,2 ),(2 ,3 ),(2 ,4 ),(3 ,3 ),(3 ,4 ),(4 ,4 )}

R 6 ={(3 ,4 )}

(i)Which of these relations are reflexive?Explain.[2 marks ]

The relations R 3 and R 5 are reflexive since they both contain all pairs of the form (a ,a ),for all elements a .

(ii)Which of these relations are symmetric?Explain.[2 marks ]

The relations R 2 and R 3 are symmetric because in each case (b ,a )belongs to the relation whenever (a ,b )does.

(iii)Which of these relations are antisymmetric?Explain.[2 marks ]

The relations R 4,R 5 and R 6 are all antisymmentric because for each of these relations there is no pair of elements a and b with a .b such that both (a ,b ) and (b ,a )belong to the relation.

(iv)Which of these relations are transitive?Explain.[2 marks ]

The relations R 4, R 5 and R 6 are transitive. For each of these relations, if (a ,b ) and (b ,c ) belong to the relation,then so does
(a ,c).[2 marks ] In each case,award one mark for the correct relations and one mark for the correct explanation.

Let A ,B and C be sets.Show,using algebraic laws,that

(i)(A U B )(A U B U C )[2 marks ]

(ii)(A n B n C )(A n B )[2 marks ]UG

Why is f not a function from R to R in the following equations?

(i)f (x )=1 /x [1 mark ]

f (0 )is not defined.

(ii)f (x )= [1 mark ]

f (x ) is not defined for x <0.g

(iii)f (x )= [1 mark ]

f (x ) is not well –defined since there are two distinct values assigned to each x .