Get premium membership and access revision papers, questions with answers as well as video lessons.
Discrete Mathematics Question Paper
Discrete Mathematics
Course:Diploma In Information Technology
Institution: Bungoma Technical Training Institute question papers
Exam Year:2009
STAGE II EXAMINATION FOR THE DIPLOMA IN INFORMATION
TECHNOLOGY
DISCRETE MATHEMATICS
DATE: APRIL, 2012 TIME: 1½ HOURS
INSTRUCTIONS: Answer Any Three Questions
Question One (20 Marks)
a) i) Define the term Boolean algebra (2 Marks)
ii) Use Boolean identities to prove that x + x = x (3 Marks)
iii) Find the value of (1*0) + (0 +1)' (2 Marks)
iv) Express F (x, y, z) = (x + y)' + x y as a sum-of-products and then in its complete sum-of
Products form. (4 Marks)
b) Let A = {1,2,3,4}. In each relation given below determine whether the following relations are
reflexive, symmetric and antisymmetric or transitive are satisfied or not. In each case justify your
answer.
{( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )} 1 R = 1,1 , 1, 2 , 2,1 , 2, 2 , 3,3 , 3, 4 , 4,3 , 4, 4
{( ) ( ) ( )} 2 R = 1,1 , 2, 2 , 3,3
{( ) ( ) ( ) ( ) ( ) ( )} 3 R = 1,1 , 1,3 , 3,1 , 1,2 , 3,3 , 4,4
{( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )} 4 R = 1,1 , 1,3 , 1,4 , 3,1 , 2,2 , 3,3 , 3,4 , 4,4 (9 Marks)
2
Question Two (20 Marks)
a) Define a lattice as used in posets. (2 Marks)
b) Briefly describe a Hasse diagram (2 Marks)
c) Draw a Hasse diagram for the following set under the divisibility relation on a set
A = {1,2,3,4,6,8,9,12,18, 24} showing all steps. (6 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 the upper bound and lower bound of the set B = {4,6,9} (2 Marks)
iv)Find the least upper bound and greatest lower bound of the set B = {4,6,9}, if they exist
(2 Marks)
v) Is this poset a lattice? Give reason for your answer. (2 Marks)
Question Three (20 Marks)
a) Prove that n n
n r r C C - = (3 Marks)
b) A club has two groups of players’ labeled group A and group B. The number of players in group B
is 8. Find the number of ways a football team of 11 players can be formed from the two groups so
that the team contains at least 4 players from group A. (8 Marks)
c) Solve the recurrence relation 1 2 3 3 3 n n n n a a a a - - - = - + if n > 2 with the initial conditions
0 1 2 a = 2,a =1 and a =1 (9 Marks)
Question Four (20 Marks)
a) State the handshaking Theorem (2 Marks)
b) Use the graph below to answer the following questions
i) State the degree of each of the vertices (3 Marks)
ii)Verify the Handshaking Theorem using the graph above (2 Marks)
iii) Use alphabetical order to determine the adjacency and incidence matrices to represent the
graph. (6 Marks)
c) i) Verify that the number of edges in a complete graph with n vertices is
( ) 12
n n-
(4 Marks)
ii) Draw the complete graph 3 K and 4 K (3 Marks)
Question Five (20 Marks)
a) Let A = {1,2,3} and B = {1,2,3,4}. 1 R and 2 R are relations from A into B.
{( ) ( ) ( )} 1 R = 1,1 , 2,2 , 3,3 and {( ) ( ) ( ) ( )} 2 R = 1,1 , 1,2 , 1,3 , 1,4 . Find
i) 1 2 R - R (2 Marks)
ii) 1 2 R °R (2 Marks)
iii) R2 M c (2 Marks)
b) Find the DNF of the Boolean function F ( x, y, z) = ( x + z ) y algebraically. (4 Marks)
c) Write the following relations as sets of ordered pairs.
i) 1 R is from A = {1,2,3,4}into B = {5,6,10} defined by 1 aR b if and only if gcd(a,b) =1
(2 Marks)
ii) 2 R is from A = {2,5,7,18} into B = {2,3,4,5,10} defined by 2 aR b if and only if a = b
(2 Marks)
d) i) Define the term dual and find the dual of xyz + x y z = 0 (3 Marks)
ii) Draw the graph represented by the given adjacency
0 2 1 0
2 0 1 1
1 1 0 0
0 1 0 1
(3 Marks)
More Question Papers
Popular Exams
Return to Question Papers