Get premium membership and access revision papers, questions with answers as well as video lessons.
Got a question or eager to learn? Discover limitless learning on WhatsApp now -
Start Now!
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 EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 1206: DISCRETE MATHEMATICS
DATE: APRIL 2011 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION TWO (20 MARKS)
a) Let A ={1,2,3,4,5,6,7,8} and R = {(a,b): a / b}
i. list the elements of R (2 Marks)
ii. Is R a partial ordering? Justify your answer (3 Marks)
iii. Are the elements 5 and 6 comparable? Justify your answer (2 Marks)
iv. Is the set A, a totally ordered set? Justify your answer (2 Marks)
b) i. Define a Boolean algebra (2 Marks)
ii. Let B ={1,2,5,7,10,14,35,70}.Define +,× , , on B by
x + y = lcm(x, y) , x × y = gcd( x, y) ,
x
x = 70 .For x, y ? B ,lcm and gcd denote respectively, the
least common multiple and the greatest common divisor. is (B,+,×, ,1,70) a Boolean algebra?
(6 Marks)
c) i. Define a recurrence relation (2 Marks)
ii. Solve the recurrence relation 1 2 7 10 - - = - n n n a a a for n = 2 subject to the Initial
Conditions 0 , 3 0 1 a = a = . (6 Marks)
d) Draw a Hasse diagram of the partial order R on A = {2,7,14,28,56,84} given by
2
R ={(a,b): a / b} (6 Marks)
QUESTION TWO (20 MARKS)
a) State the main difference between directed and undirected graphs (2 Marks)
b) Show that the maximum number of edges in a graph with n -vertices is
2 nC (4 Marks)
c) Show that the number of vertices of odd degree in a simple graph is always even (4 Marks)
d) i. Draw a directed graph with the adjacency matrix
? ? ? ?
?
?
? ? ? ?
?
?
=
1 1 1 0
1 1 0 1
0 0 1 0
0 0 1 1
A
With vertices ordering of 1 2 3 4 v ,v ,v ,v . (4 Marks)
iii. Obtain the path matrix (P) of the graph in d (i) above (6 Marks)
QUESTION THREE (20 MARKS)
a) Use the binomial theorem
i. To prove that ( 1) 0
0
= ?
??
?
? ??
?
- S=
n
k
k
k
n
(4 Marks)
ii. To find the coefficient of x101 y99 in the expansion of (2x - 3y)200 (3 Marks)
b) 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
(6Marks)
c) Solve the following recurrence relation 1 2 3 6 11 6 - - - = - + n n n n a a a a given that
2 , 5, 15 0 1 3 a = a = a = (7 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,6,8,12,24,36,48} (8 Marks)
3
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 = {6,8,12} (2 Marks)
iv. Find the least upper bound and greatest lower bound of B = {6,8,12}, if they exist (2Marks)
v. Is this poset a lattice? Give reason for your answer (2 Marks)
QUESTION FIVE (20 MARKS)
a) i. Draw the graphs of , , , , 5 5 6 4,5 W C K K and 1,5 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)
b) Use Boolean laws to show that
i. (x + y) + x y =1 (3 Marks)
ii. (x +1) =1 (3 Marks)
c) Construct the truth table for the following Boolean expression
f(x, y, z)= x(y + z) (3 Marks)
More Question Papers
Popular Exams
Return to Question Papers