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:2009

UNIVERSITY EXAMINATIONS: 2008/2009
FIRST YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 1206: DISCRETE MATHEMATICS
DATE: AUGUST 2009 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE
a) Define the following terms
i) Partial ordering
ii) Totally ordered set
iii) Poset
iv) Lattice
v) Boolean algebra (5 Marks)
b) Let S ={1,2,3,5,6,10,15,30}.Define +,. and ‘on S by
x+y=lcm(x,y),x.y=gcd(x,y),x’=
x
30 .For x, y ? S ,lcm and gcd denote,respectively,the least
common multiple and the greatest common divisor. Show that (S,+,’,1,30) is a Boolean
algebra. (5 Marks)
c) Solve the recurrence relation 6 9 4 1 2 + + = n n- n- a a a for n = 2subject to the initial Conditions
0 , 1, 0 1 a = a = . (5 Marks)
d) Show that the maximum number of edges in a graph with n -vertices is
2
? ??
?
? ??
?
2
n
. (4 Marks)
e) Given that R is a relation defined by{(x, y); x divides y} is a partial ordering
on the set A={1,2,3,4,6,8,9,12,18,24}.Construct its Hasse diagram (6 Marks)
f) i.state the binomial theorem (1 Mark)
ii.Use the binomial theorem to prove that k
n
k
n
k
n
3 2
0 S=
? ??
?
? ??
?
= . (4 Marks)
QUESTION TWO (20 MARKS)
a) Define the following terms as used in graph theory
i. reachability matrix
ii. path
iii. subgraph
iv. strongly connected graph
v. a source (5 Marks)
b) i. Draw a directed graph with the adjacency matrix
? ? ? ?
?
?
? ? ? ?
?
?
=
1 1 1 0
1 0 1 0
0 0 1 0
1 1 1 0
A
With vertices ordering of a,b,c,d. (2 Marks)
ii) Find the indegree and outdegree of each vertex in the graph in (i) above (4 Marks)
iii. How many paths of length 4 are there from a to c in the graph in b (i) above. (4 Marks)
iv. Obtain the path matrix (P) of the graph in b (i) above (5 Marks)
QUESTION THREE (20 MARKS)
a) Construct a truth table for the Boolean function f (x, y, z) = xy + yz + x yz (5 Marks)
b) Using Boolean properties show that
i. x + xy = x (5 Marks)
ii. x +1 = 1 (5 Marks)
c) Write the dual of each statement
3
i. (x +1)(x + y)= x + xy + y (2 Marks)
ii. xz + x.0 + x.1 (3 Marks)
QUESTION FOUR (20 MARKS)
a) Draw the Hasse diagram for the partial ordering, (? (A),?) power set ? (A)
where A ={1,2,3}. (6 Marks)
b) X={2,3,6,12,24,36}.R on X={(x, y)? R; x divides y}
i. Construct Hasse diagram (4 Marks)
ii. Find the maximal and minimal elements (2 Marks)
iii. Is there greatest and least elements (2 Marks)
iv find all upper bounds and lower bounds of {6,12,24} (2 Marks)
v Find least upper bounds and greatest lower bound of{6,12,24} (2 Marks)
vi. Is poset a lattice? Give reason for your answer (2 Marks)
QUESTION FIVE (20 MARKS)
a) i. Find the number of ways in which five persons can sit in a row?
ii. How many ways are there if two of the persons insist of sitting next to one another
iii. Solve part (i) assuming they sit around a circular table
iv. Solve part (ii) assuming they sit around a circular table
(8 Marks)
b) Find the coefficient of x101 y99 in the expansion of (2x - 3y)200 (4 Marks)
c) i. Define the basis step and recursive step in recursively defined sets (4 Marks)
ii. Give a recursive definition of the set of positive integers that are multiples of 5 (4 Marks)

Discrete Mathematics Question Paper

More Question Papers

Popular Exams