Introduction to Discrete Mathematics – MAT2612, University of South Africa (UNISA), 2022, complete exam materia

MAT2612

Solutions: ASSIGNMENT 02: SEMESTER 2



Question 1

Functions are discussed in Chapter 5.

(a) R1 is not a function since (4, 2) and (4, 3) are in R1 .

(b) (i) R2 is a function since we do not have (a, b) and (a, c) in R2 for b  c.

(ii) R2 is not onto since there is no pair (a, 1).

(iii) R2 is not one-to-one since we have (2, 5) and (5, 5) in R2

(iv) R2 is everywhere defined since for all a  A there exists b  A such that (a, b)  R2



Question 2

1
f(x) =
10  x
(a) f is defined for all x  0.

(b) f is not onto. Range of f = (0, 1/10]

1 1
(c) Suppose f(a) = f(b)  =  a = b  a = b. Hence f is one-to-one.
10  a 10  b

1
(d) Since f is one-to-one, f is invertible. To find f 1 interchange x and y so that x = 
10  y

1 1 1
x( y + 10) = 1  y + 10 =  y = - 10  y = ( - 10) 2
for x  (0, 1/10]
x x x


Question 3

(a) f(n) = 10. Then f(2n) = 10 = f(n) and computing time stays constant.

(b) f(n) = 5n + 6. Then f(2n) = 5(2n) + 6 = 2(5n + 6) – 6 = 2f(n) – 6.

(c) f(2n) = 6 (2n) 2 = 6(4n 2 ) = 4(6n 2 ) = 4 f(n). Hence computing time is 4 times the original time.

(d) f(2n) = 2 2n = ( 2 n ) 2 = (f(n)) 2 Hence the square of the original time.

,Question 4

(a) To show that n 2 is O (n 2 log n) we need to find constants c and k such that

| n 2 |  c |n 2 log n| for all n  k, that is n 2  c ( n 2 log n) for all n  k

Now n 2  n 2 log n for n  10 since log n  1 for n  10.

Let c = 1 and k = 10.

(b) Assume that n 2 is O (n 2 log n). Then, by definition, there exist c, k such that

n 2 log n  c n 2 for all n  k  n 2 log n / n 2  c for all n  k  log n  c for all n  k

But log n   as n   , a contradiction.

Hence n 2 log n is not O (n 2 ).



Question 5

A permutation is a bijection (1-1 and onto function) from a set A to itself.

(a) f(a) = a + 2

f is onto, since for any b  there exists a  such that f(a) = b (let a = b – 2).

f is 1 – 1: f(a) = f(b)  a + 2 = b + 2  a = b.

Hence f is a permutation.



(b) f(a) = a 2 - 2a

f is not a permutation, since f is not 1 – 1: for example, f (-1) = f (3).



Question 6

 1 2 3 4 5 6 7 8
(a) (2,3) o (4,5,6) o (1,3,6,7) =  
 2 3 4 5 6 7 1 8


 1 2 3 4 5 6 7 8
(b) (5,8,3) o (1,2) o (3,5,6,7) =  
 2 1 8 4 6 3 5 3

,Question 7

(a) p(1) = 5, p(2) = 6, p(3) = 2, p(4) = 7, p(5) = 3, p(6) = 4, p(7) = 8, p(8) = 1.



(b) p = (1, 5, 3, 2, 6, 4, 7, 8)



(c) p = (1, 8)(1, 7)(1, 4)(1, 6)(1,2)(1, 3)(1,5)



(d) p is an odd permutation since it is a product of an odd number of transpositions.



1 2 3 4 5 6 7 8
(e) p o p =   = (1, 3, 6, 7)(2, 4, 8, 5)
3 4 6 8 2 7 1 5


1 2 3 4 5 6 7 8 
(f) p 1 =   = (1, 8, 7, 4, 6, 2, 3,5)
 8 3 5 6 1 2 4 7 


(g) p is a cycle of length 8, and hence period of p is 8



1 2 3 4 5 6 7 8
(h) Let r =  
 2 5 1 6 3 8 7 4

 1 2 3 4 5 6 7 8  1 2 3 4 5 6 7 8 
Then q o p = r  q = r o p 1 =  o 
 2 5 1 6 3 8 7 4 8 3 5 6 1 2 4 7 


1 2 3 4 5 6 7 8
= 
4 1 3 8 2 5 6 7


Question 8

Any cycle of length 5, for example (1, 2, 3, 5, 6)

, Question 9

A partial order on a set A is a reflexive, antisymmetric and transitive relation on A.

(a) R 1 is not a partial order: R 1 is not reflexive, since (a, a)  R 1 for all a  A



(b) R 2 is not a partial order: R 2 is not transitive, for example (1, 2) and (2, 3)  R 2 but (1, 3)  R 2



Question 10

D 72 = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72}

|D 72 | = 12

(a)




(b)For any a, b  D n , a  b = LCM (a, b) and a  b = GCD (a, b) (see Example 3, section 6.3 in KBR).