Get premium membership and access revision papers, questions with answers as well as video lessons.

Discrete Mathematics Question Paper

Discrete Mathematics

Course:Bachelor Of Science In Information Technology

Institution: Kca University question papers

Exam Year:2011

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)
ii. Let S be the universal set and let G = ? (S) ,the power set of S .Define the following
operations X + Y = X ?Y , XY = X nY , X = X C on G .Show that (G,?,n, ,F,S) is a Boolean
algebra (6 Marks)
b) Let A = {4,5,6,7,8,9,10} and R = {(a,b): a = b}
i) list the elements of R (2 Marks)
ii) Is (A, R) a poset? Justify your answer (3 Marks)
iii)Are the elements 7 and 8 comparable? Justify your answer (2 Marks)
iv)Is R a total ordering? Justify your answer (2 Marks)
c) Solve the recurrence relation 1 2 3 5 8 4 - - - = - + n n n n a a a a for n = 3 subject to the Initial
Conditions 0 , 1, 2 0 1 3 a = a = a = . (6 Marks)
d) Draw a Hasse diagram of the partial order R on A = {1,2,3,6,12,24,36,48} given by
2
R = {(a,b): a / b} (7 Marks)
Question Two (20 Marks)
a) i. Draw the graphs of , , , , 3 3 5 3,4 W C K K and 1,6 K (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
i) To prove that n
(5 Marks)
ii) To find the coefficient of x12 y13 in the expansion of (4x - 6y)25 (3 Marks)
b) i. Draw a directed graph with the adjacency matrix
With vertices ordering of 1 2 3 4 v ,v ,v ,v . (2 Marks)
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
3
(2 Marks)
v) Is this poset a lattice? Give reason for your answer (2 Marks)
Question Five (20 Marks)
a) Let B = {1,2,5,10,11,22,55,110}.Define +,×, , on B by
x + y = lcm(x, y) , x + y = gcd(x, y) ,
x
x = 110 .For x, y ? B ,lcm and gcd denote respectively,
the least common multiple and the greatest common divisor. is (B,+,×, ,1,110) a Boolean
algebra? (6 Marks)
b) Use Boolean laws to show that
i. (x + y)x y = 0 (3 Marks)
ii. x + xy = x (3 Marks)
c) Construct the truth table for the following Boolean expression
f (x, y, z) = x(y + z) (3 Marks)
d) Out of 12 employees, a group of four trainees is to be sent for software testing and QA for one
month. In how many ways can the four employees be selected if there are two employees who want
to go together that is either they both go or both do not go for training? ( 5 Marks)

Discrete Mathematics Question Paper

More Question Papers

Popular Exams