Question 1
Let E = { 1,2, 3, 4, 5,6,7,8,9} be the universal set.
Let A = {1,2,3,5}, B = {2,4,7,8} and C = {3,4,5,8}.
Find:
(i) [`A],  (ii) A ÇC,   (iii) A ÈB,   (iv) (A ÈB) ÇB,   (v) [`((A ÇB))],   (vi) A ÈÆ,   (vii) A ÈE.

Question 2
27 professional photographers were asked whether they work in black and white or in colour. 25 said they work in colour and 13 said they use both. Use the Inclusion-Exclusion Principle to find how many work in black and white only.

Question 3
In a group of 29 people, there are 14 dog owners and 9 cat owners. If 4 people own both a cat and a dog, how many people own neither?

Question 4
Let E = { 1,2,3,4,5,6,7,8,9}.
(i) Find the representation of Æ, {1,3,9}, {2,4,5}, {9}, {2,4,5,7} as bit strings.
(ii) Write down the sets represented by the following bit strings  001110101, 010110001, 110101101, 101101011, 111100001
(iii) Find the sets got by bitwise AND-ing the following together

Question 5
Represent the following relations as (i) directed graphs and (ii) relation matrices.
(a) R = { (1,2), (2,1), (3,3), (1,1), (2,2)} on X = {1,2,3}
(b) R = { (1,2), (2,3), (3,4), (4,1)} on X = {1,2,3,4}
(c) R  on {1,2,3,4} defined by (x,y) Î R if x² ³ y
(d) R = { (a,b), (b,a), (b,d), (a,c), (c,c), (c,d)} on X = {a,b,c,d}

Question 6
Give the set on which the following relations are defined. Write the relations as sets of ordered pairs.

Question 7
Determine if the following relations are equivalence relations on {1,2,3,4,5}, and if they are, determine the associated equivalence classes.
(i) R = { (1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1)}
(ii) R = { (1,1), (2,2), (3,3), (4,4), (5,5), (1,5), (5,1), (3,5), (5,3), (1,3),(3,1)}
(iii) R = { (1,1), (2,2), (3,3), (4,4)}
(iv) R = { (1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3) (4,4), (5,5)}
(v) R = { (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1) (3,2), (3,3), (4,4), (5,5) }

Question 8
Determine if the following relations are reflexive, irreflexive, symmetric, antisymmetric or transitive. If possible classify them as equivalence relations or partial orders.
(i) R = {(x,y) | x = y} defined on the set of positive integers.
(ii)R = { (1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (2,1), (3,2) } defined on {1,2,3,4}
(iii)R = { (1,1), (2,1), (2,2) } defined on {1,2,3,4}
(iv) R = {(x,y) | 3 divides x+y } on the set {1,2,3,4,5}

Question 9
Determine if the following relations from X = {1,2,3,4} to Y = {a,b,c,d} are functions. If they are functions are they one-to-one or onto?
(i) R = { (1,a), (2,a), (3,c), (4,b)}
(ii) R = { (1,c), (2,a), (3,b), (4,c), (2,d)}
(iii) R = { (1,c), (2,d), (3,a), (4,b)}
(iv) R = { (1,d), (2,d), (4,a)}
(v) R = { (1,b), (2,b), (3,b),(4,b)}

Question 10
Given function g from X = {1,2,3} to Y = {a,b,c,d} defined by

Question 11
If function f: R ® R is defined by f(x) = x²+3x and function g:R ® R is defined by g(x) = 7x+2, evaluate the following
(i) f °g
(ii) g °f
(iii) f °f
(iv) f °g °f
(v) g °f °g

Question 12
Determine if the following functions have inverses, and if they do, find the inverse:
(i) y = 0.5x+1
(ii) y = x²     x ³ 0
(iii) y = x³ +1
(iv) y = x⁴     x ³ 0
(v) y = ¹/₂x -⁷/₂

Question 13
Evaluate the first six terms for the following recursively defined sequences:
(i) t(1) = 7,     t(n) = t(n-1) +3   (n > 1)
(ii) t(1) = 2,     t(n) = ¹/₂t(n-1) +3   (n > 1)
(iii) t(1) = 0,     t(n) = 3t(n-1) +n   (n > 1)

Question 14
Evaluate t(3), t(4), t(5) and t(6) for the following:
(i) t(1) = 2     t(2) = 4     t(n) = 2t(n-1) +t(n-2)    (n > 2)
(ii) t(1) = 3     t(2) = 1     t(n) = ¹/₂[t(n-1) +t(n-2)]    (n > 2)
(iii) t(1) = 7     t(2) = 11     t(n) = 3t(n-1) +2t(n-2)    (n > 2)

Question 15
For each of the sequences in Question 13 write an iterative algorithm to output the first n terms of the sequence.

Question 16
Prove the following statements are true for all natural numbers n using induction.
(i) 1(2) +2(3) + 3(4) + ... +n(n+1) = [(n(n+1)(n+2))/ 3]
(ii) 1(1!) +2(2!) + 3(3!) + ... +n(n!) = (n+1)! -1
(iii) 1² -2² + 3² - ... +(-1)ⁿ⁺¹n² = (-1)ⁿ⁺¹ [(n(n+1))/ 2]
(iv) 1³ + 2³ + 3³ + ... +n³ = ([(n(n+1))/ 2])²

Question 17
Let t(n) be defined recursively as follows:
t(1) = 4        t(n) = 2t(n-1) +3
Prove by induction that t(n) = 7·2^n-1 -3

Question 18
Let t(n) be defined recursively as follows:
t(1) = 7        t(n) = 3t(n-1) +11
Prove by induction that t(n) = 3^n-1(12.5) - 5.5

Question 19
Find a recursive expression for the output of each of the following algorithms. Hence prove by induction that the algorithm produces the output claimed.
(i) Algorithm to output a table of values of [(i(4i² +18i +11))/ 3] i = 1,2,3,... n

1. input n 
2. value <- 0 
3. for i=1 to n do 
	3.1 j <- (2i+1)(2i+1)
	3.2 value <- value + j
	3.3 output i, value

(ii) Algorithm to output a table of values of [(i(i-1))/ 2], i = 1,2,3,...,n:

1. input n 
2. value <- 0 
3. for i=1 to n do 
	3.1. j <- i-1
	3.2 value <- value +j
	3.3 output i, value

Answers

Question 2
Two use black and white only.

Question 3
Ten people do not own either a dog or a cat.

Question 4
(i)

Question 5
(a) R = { (1,2), (2,1), (3,3), (1,1), (2,2)} on X = {1,2,3}

Question 6
(i) R = { (1,1), (2,2), (3,3), (4,4), (5,5), (3,5), (5,4), (4,3)} on {1,2,3,4,5}.
(ii) R = { (b,c), (c,b), (d,d)} on {a,b,c,d}
(iii) R = { (1,1), (1,2), (1,3), (1,4), (2,2) (2,3), (3,3), (3,4), (4,4) } on {1,2,3,4}.

Question 7
(i) Equivalence relation: [1] = [3] = {1,3}, [2] = {2}, [4] = {4}, [5] = {5}
(ii) Equivalence relation: [1] = [3] = [5] = {1,3, 5}, [2] = {2}, [4] = {4}
(iii) Not an equivalence relation since (5,5) \not Î R.
(iv) Equivalence relation: [1] = [2] = {1,2}, [3] = [4] = {3,4}, [5] = {5}
(v) Equivalence relation: [1] = [2] = [3] = {1,2,3}, [4] = {4}, [5] = {5}

Question 8
(i) This is reflexive, symmetric, antisymmetric and transitive. It is not irreflexive.
This means that it is an equivalence relation and a partial order.
(ii)This is reflexive, symmetric and transitive. It is not irreflexive and antisymmetric. It is an equivalence relation
(iii) This is antisymmetric and transitive. It is not reflexive, irreflexive, symmetric.
(iv) This is symmetric. It is not reflexive, irreflexive, transitive or antisymmetric.

Question 9
(i) It is a function, it is neither one-to-one or onto.
(ii) It is not a function since (2,a) and (2,d) are in R.
(iii) It is a function. It is one-to-one and onto.
(iv) It is not a function since 3 is not mapped onto the range.
(v) It is a function. It is neither one-to-one or onto.

Question 10
f°g = { (1,x), (2,z), (3,x) }

Question 11
If function f: R ® R is defined by f(x) = x²+3x and function g:R ® R is defined by g(x) = 7x+2, evaluate the following
(i)

(v)

Question 12
(i) f^-1 (x) = 2(x-1)
(ii) f^-1 (x) = +Öx
(iii) f^-1 (x) = ³Ö{x-1}
(iv) f^-1 (x) = +⁴Ö{x}
(v) f^-1 (x) = 2x +7

Question 13
(i)

(ii)

(iii)

Question 14
(i)

(ii)

(iii)

Question 15
(i)

1. input n
2. value <- t(1)=7
3  output value
4. for i = 1 to n do 
	4.1 value <- value + 3
	4.2 output value

(ii)

1. input n
2. value <- 2
3  output value
4. for i = 1 to n do 
	4.1 value <-  0.5(value) + 3
	4.2 output value

(iii)

1. input n
2. value <- 2
3  output value
4. for i = 1 to n do 
	4.1 value <-  3(value) + n
	4.2 output value

Question 16
(i) True for n = 1 since

Question 17
True for n = 1 since

Question 18
True for n = 1 since

Question 19
(i) t(1) = 9, t(k) = t(k-1) + (2k+1)² . Need to use induction to show