BIT108 Sample Test
Time: 2 Hours Total mark is 100. Value: 20%
Show all your workings.
Question 1 (Sets, Relations, Functions)
a) Shade the region of the Venn Diagram indicated by the following set:
A B
A' – (B C)
C
b) Given A = {2, 3, 4} and B = {6, 8, 10} and the relation
B = {(x, y) ∈ A × B | x divides y}
Write B as a set of ordered pairs.
c) Given A = {2, 3, 4} and B = {6, 8, 10} and the relations
R = {(2,6), (3,8), (4,8)}
S = {(2,6), (3, 6), (3,8), (4,10)}
Are the relations defined above functions from A to B? Justify your answer.
d) In a survey of 80 people, it was found that 31 read Newsweek magazines, 40 read Times, and
43 read Fortune. Also 14 people read both Newsweek and Times, 12 read both Newsweek
and Fortune, 19 read both Times and Fortune, and 4 read all three magazines.
Using a Venn diagram, answer the following questions:
i) How many people read Times and Fortune but not Newsweek?
i) How many people read Times or Fortune or both but not Newsweek?
iii) How many people read exactly one magazine?
iv) How many people read none of the three magazines
Question 2 (Logic and Proof + Quantifier)
a) Let p, q and r be the propositions
p: Alex had started revision on Functions.
q: Benjamin had done the tutorial on Sets.
r: The test is on Friday.
Represent the following statements symbolically using the logical connective, and (), or (),
not (~), conditional (→), biconditional ().
(i) Alex had not started revision on Functions.
(ii) Benjamin had done the tutorial on Sets, but the test is not on Friday.
(iii) If either Alex had not started revision on Functions or Benjamin had not done the tutorial
on Sets, then the test is not on Friday.
b) Write the inverse for the following statement:
If Cindy tells the truth, then David will be punished.
c) Prove [(p → ~q) q ] → ~p is a tautology using Laws of Proposition.
NOTE: When proving using Laws of Proposition, you MUST write down the laws which are
used in each step to get full marks.
d) Determine the truth value for each of the following quantified expression:
i) x (x + 1 > 2) [U: set of natural numbers] ii) x (x + 1 > 2) [U: the integers 2, 3, 4]
iii) x (x2 = 3) [U: set of natural numbers] iv) x (x2 = 4) [U: set of natural numbers]
v) x (x2 > 0) [U: set of real numbers] vi) x (x2 > 0) [U: set of natural numbers]
vii) x (x < x2) [U: set of positive real numbers] viii) x (x < x2) [U: set of natural numbers]
v) x (x2 = –1) [U: set of real numbers] vi) x (2x = 1) [U: set of rational numbers]
(U: universe of discourse)
Question 3 (Methods of Proof)
a) Using mathematical induction, prove that for all integers n 0,
1 1 1 1
1+ + +. . . + =2− .
2 22 2n 2n
b) Using direct proof to prove the following:
The sum of any two rational numbers is rational.
(If m and n are any rational number, then their sum is rational.)
c) Prove the following statement
For all integers m and n, if 11m + 19n is odd then either m or n (or both) is odd.
using:
i) Proof by Contradiction
ii) Proof by Contrapositive
Question 4 (Recurrence Relations)
Find all the solutions of the recurrence relations an = 8an-1 – 16an-2 – 9, with initial conditions a0 =
0, a1 = –9.
