UNIVERSITY EXAMINATIONS: 2010/2011
FIRST YEAR STAGE EXAMINATION FOR THE DEGREE OF BACHELOR
OF SCIENCE IN INFORMATION TECHNOLOGY
BIT 1206: DISCRETE MATHEMATICS
DATE: AUGUST 2011 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
Question One
a) i. Define a Boolean algebra (2 Marks)
Question Two (20 Marks)
a) i. Draw the graphs of , , , , W3 C3 K5 K3,4 and K1,6 (5 Marks)
ii. Give an example in each case of special type of graph that is used in star, ring and hybrid
topologies. Show diagrams in each case. (6 Marks)
iii. Define a complete bipartite graph and give an example showing its graph (4 Marks)
b) Show that the number of vertices of odd degree in a simple graph is always even (5 Marks)
Question Three (20 Marks)
a) Use the binomial theorem
ii Obtain the degree of each vertex (4 Marks)
iii. Obtain the path matrix (P) of the graph in d (i) above (6 Marks)
Question Four (20 Marks)
a) Define a lattice as used in posets (2 Marks)
b) Draw a Hasse diagram for the following set under the divisibility relation
{ } 1,2,3,4,6,8,9,12,18,24 (8 Marks)
i) Find the maximal and minimal elements (2 Marks)
ii) Find the greatest and least elements, if they exist (2 Marks)
iii)Find the all upper bound and all lower bound of the set B = {4,6,9} (2 Marks)
iv) Find the least upper bound and greatest lower bound of B = {4,6,9}, if they exist
(2 Marks)
v) Is this poset a lattice? Give reason for your answer (2 Marks)
Question Five (20 Marks)
