Bit 1206 Discrete Mathematics Question Paper
Bit 1206 Discrete Mathematics
Course:Bachelor Of Science In Information Technology
Institution: Kca University question papers
Exam Year:2014
UNIVERSITY EXAMINATIONS: 2013/2014
ORDINARY EXAMINATION FOR THE BACHELOR OF SCIENCE
IN INFORMATION TECHNOLOGY
BIT 1206 DISCRETE MATHEMATICS
DATE: AUGUST, 2014
TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE (30MARKS)
a)
Define the following terms as used in discrete mathematics
i) (1 mark)
ii) Cartesian product of two sets A and B (1 mark)
i. Differentiate between relations and recurrence relations (2 marks)
ii.
b)
A proper subset Find the first five terms of the sequence defined by the following
recurrence relation and initial conditions
an
iii
3a n
1
2
, a0
1 , a1
Show that the sequence a n
an
c)
an
8a n
1
16 a n
(3 marks)
4 n is a solution of the recurrence relation
(4 marks)
2
0,1,2,3,4,5,6,7,8,9,10 , A
Let
2
3,4,5,6 , B
4,6,8,9,10 .
is the universal
set. List the elements of the following set.
(A
d)
e)
B)
A B
Use a truth table to show that
(3 marks)
p
p
q
q is a tautology.
(4 marks)
i. Clearly define a function (1 mark)
ii. State the difference between relations and functions (2 marks)
1
f)
Let B
1,2,4,5,10 ,20 .Define x
y
lcm x, y , x. y
gcd x, y , x
together with its operations a Boolean algebra?
g)
20
.Is B
x
(4 marks)
Test the validity of the following argument
„„If you are eligible for admission then you must be under 25 and if you are not
under 25 then you do not qualify for scholarship. Therefore if you qualify for a
scholarship then you are eligible for admission?
(5 marks)
QUESTION TWO (20 MARKS)
a)
Let A
1,2,3 , B
and S. R
a, b, c and C
x, y, z .Consider the following relation R
1, b , 2, a , 2, b , 3, a , (3, c) and S
a, x , a, z , b, x , b, y , (c, z
i) (3 marks)
ii) Find the matrices M R , M S and M RoS . (3 marks)
iii)
b)
Find the composition relation RoS Find the elements of R c , S c and ( RoS ) c (6 marks)
1,2,3,4,6,8,12 and R
Let A
a, b : a
b
i) (2 marks)
ii)
c)
List the elements of R Is R a partial ordering? Justify your answer (2 marks)
Let R be the relation represented by the matrix
0 1 1
0 1 1
1 1 1
Find the matrix representing
i) R
ii)
1
( 2 marks)
Rc
( 2 marks)
QUESTION THREE (20 MARKS)
a).
i)
Define a graph and state the difference between directed and undirected
graphs.
ii)
(2 marks)
Draw a directed graph with the adjacency matrix
2
1 1 0 1
0 0 1 0
A
1 0 1 1
1 0 1 1
With vertices ordering v1 , v 2 , v3 , v 4
iii)
(2 marks)
Use the graph in (i) to find the in-degree, out-degree and degree of each
vertex.
(3 marks)
c) Show that p
d) Let P(x) be the statement “ x
q and p
q
q are logically equivalent. (5 marks)
p
x 2 ”.If the universe of discourse is the set of
integers, what is the truth values of the following?
(i) P(0) (2 marks)
(ii) P(2) (2 marks)
(iii) xP(x) (2 marks)
(iv) (2 marks)
xP(x)
QUESTION FOUR (20 MARKS)
a)
Construct a relation on the set 1,2,3,4 that is Reflexive, symmetric, antisymetric
and transitive.
b)
x2
Let f ( x)
(3 marks)
1 and g ( x)
5 , find
3x
i) (3 marks)
ii) f g (x) (3 marks)
iii)
c)
g f (x) f g (4) (3 marks)
Solve the recurrence relations
an
d)
5a n
1
6a n
2
, a0
1 , a1
0
(5 marks)
Determine the domain of the function f ( x)
3
3x 5
4 x 2 16
(3 marks)
QUESTION FIVE (20 marks)
a)
If A
1,2,3,4 and B
a, b, c, d , Draw an arrow diagram of each function and
determine the type of the following functions
i) 1, a , 2, a , 3, b , 4, d (2 marks)
ii) g 1, b , 2, d , 3, a , 4, a (2 marks)
iii)
b)
f h 1, d , 2, b , 3, a , 4, c (2 marks)
In a class of 50 students. 30 study mathematics, 18 study Electronics, 26 study
accounting, 9 study mathematics and electronics, 16 study Mathematics and
accounting, and 8 study electronics and accounting, 47 study at least one of the
three subjects.
(i) How many students study none of the three subjects?
(1mark)
(ii) How many students study all of the three subjects?
(4 marks)
(iii) Present the information in a Venn diagram
(3 marks)
(iv) How many students study mathematics or electronics but not accounting?
(2 marks)
c)
Construct a truth table of the Boolean function f ( x, y, z)
y
z x z
(4 marks)
4
More Question Papers
Exams With Marking Schemes