Bit 1206: Discrete Mathematics (Distance Learning) Question Paper
Bit 1206: Discrete Mathematics (Distance Learning)
Course:Bachelor Of Science In Information Technology
Institution: Kca University question papers
Exam Year:2014
1
UNIVERSITY EXAMINATIONS: 2013/2014
ORDINARY EXAMINATION FOR THE BACHELOR OF SCIENCE
IN INFORMATION TECHNOLOGY
BIT 1206 DISCRETE MATHEMATICS
(DISTANCE LEARNING)
DATE: APRIL, 2014 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE :( 30 MARKS)
a) In an athletic club, there are 16male members and 10 female members. How many
ways can we form a committee of 7 members subject to the following conditions:
i. There must be 3 males and 4 females. (2 Marks)
ii. The committee must contain at least 2 females. (6 Marks)
b) Let A 3, 2, 1,0,1,2 .Find the range of the functions f : A R , defined by
1 2 f x x for all x A. (3 Marks)
c) For each of the following relations on A 1,2,3,4 , decide whether it is reflective,
symmetric, anti- symmetric or transitive. (6Marks)
i. R 1, 1 , 2, 2 , 3, 3 , 4, 4 , 1, 2 , 2,1
ii. R 1, 1 , 2, 2 , 3, 3 , 1, 2 , 2,1
iii. R 1, 1 , 2, 2 , 3, 3 , 4, 4 , 1, 2
iv. R 1, 2 , 2,1
2
d) What is the truth true of the quantification xP x ? The domain of the discourse is
the set of all positive integers.
i. P x : x 2 x 3 is an even integer (1 Mark)
ii. : 1 7 2 P x x (1 Mark)
iii. P x : x 3 5 (1 Mark)
e) State the converse, contrapositive and inverse of the following statement.
“If it snows tonight, then I will stay at home” (6 Marks)
f) Let U 1,2,3,4,5,6,7,8,9 , A 1,2,3,4 , C 3,4,5,6 .List the elements of the set
A B C. (4 Marks)
QUESTION TWO :(20 MARKS)
a) Briefly describe a Hasse diagram. (3 Marks)
b) Draw a Hasse diagram of the partial ordering, R on
A 1,2,3,6,12,24,36,48 given by R a,b : a / b (7 Marks)
i. Find the maximal and minimal elements (2 Marks)
ii. Find the greatest and least elements if they exist (2 Marks)
iii. Find all upper bounds and lower bounds of the set B 3, 6, 12
(2 Marks)
iv. Find least upper bound and greatest lower bound of B 3, 6, 12 if they
exist. (2 Marks)
v. Is the poset a lattice? Give reason for your answer. (2 Marks)
QUESTION THREE: (20 MARKS)
a) Define the following terms
i. Literal (1 Mark)
ii. Minterm (1 Mark)
3
b) Prove the following Boolean law:
a a a
(3 Marks)
c) Construct the truth table for the Boolean expression
f (x, y, z) xy xyz (4 Marks)
d) Write the dual of each statement
i. (a b) (c 0) a bc 0 (2 Marks)
ii. x y xy (3 Marks)
e) Prove that p q q p . (4 Marks)
f) Let p and q be propositions:
p :I bought a lottery ticket this week
q : I won the million dollar jackpot on Friday
Express each of the following propositions as an English sentence
i. q p
ii. p q (2 Marks)
QUESTION FOUR :( 20 MARKS)
a) Draw the graph,G V,E, g where 1 2 3 4 5 V v , v , v , v , v
, 1 2 3 4 5 6 7 E e , e , e , e , e , e , e and g is defined by
7 4 5
6 2 4
4 5 1 3
3 4 4
1 2 1 2
,
,
,
,
,
g e v v
g e v v
g e g e v v
g e v v
g e g e v v
(3 Marks)
i. Find the degree of each vertex (5 Marks)
ii. Find all odd degree vertices (2 Marks)
iii. Find the adjacency matrix G A of the graph above (3 Marks)
4
iv. Find the incidence matrix G I of the graph above (3 Marks)
v. Identify a pendant vertex of the graph above and give reason (2 Marks)
b) How many vertices are there in a graph with 15 edges if each vertex is of degree
3. (2 Marks)
QUESTION FIVE: (20 MARKS)
a) Find a SOP expansion of the following Boolean function using Boolean identities.
f (x, y, z) x y z (3 Marks)
b) Let A 2,3,4 , B x, y, z be sets and R 2, x , 3, x , 3, y , 3, z , 4, y , 4, z .
Compute.
i. A B (1 Mark)
ii. R (2 Marks)
c) Show that the statement formula A: p q p r is logically equivalent to
statement formula B : p q r . (5 Marks)
d) Let f (x) 3x 1and
7
( )
x
g x , find
i. g o f (2 Marks)
ii. f o g (2 Marks)
iii. (x) 1 g (2 Marks)
iv. 1 g o f (3 Marks)
More Question Papers
Exams With Marking Schemes