UNIVERSITY EXAMINATIONS: 2011/2012
YEAR 1 EXAMINATION FOR THE BACHELOR OF SCIENCE IN
INFORMATION TECHNOLOGY
BIT 1206 DISCRETE MATHEMATICS
DATE: APRIL 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question One and Any other Two Questions
QUESTION ONE
a) Consider the following data for 120 mathematics students at a college concerning the languages
French, German and Russian:
65 study French, 45 study German, 42 study Russian, 20 study French and German, 25 study
French and Russian, 15 study Russian and German and 8 study all three languages.
Find the number of students who study at least one of the three languages. (5 Marks)
b) A man, woman, boy, girl, dog and cat are walking down a long and winding road one after the
other.
i) In how many ways can this happen? (2 Marks)
ii) In how many ways can this happen if the dog comes first. (3 Marks)
c) Give an example of a function f: N N → that is one to one but not onto. (5 Marks)
d) Determine the validity of the following argument:
lf l stay up late at night, then l will be tired in the morning. I m tired this morning. I
stayed up late last night. (5 Marks)
e) Given three consecutive integers b, b+1, b+2, prove that one of them is divisible by 3. (5 Marks)
f) Show that
QUESTION TWO
a) Let p → q be “If it rains, then l get wet”. Write down the inverse, converse and contrapositive of
this proposition. (6 Marks)
b) There are two shopping malls next to each other, one with a signboard “Good items are not cheap”
and a second with a signboard “cheap items are not good”. Do they mean the same? (7 Marks)
c) Construct the truth table for
(7 Marks)
QUESTION THREE
a) Find the smallest positive integer x such that when x is divided by 3 it yields a remainder 2, when x
is divided by 7 it yields a remainder 4, and when x is divided by 10 it yields a remainder 6.
(8 Marks)
b) Let a = 37 and b = 249. Find
i) d = gcd(a, b)
ii) Integers m and n such that d = ma + nb
iii) lcm (a,b).
(12 Marks)
QUESTION FOUR
a) Write the dual of each Boolean equation:
i) ( ) a a ⋅⋅ + = 10 0 ( )
ii) a ab a b + =+
(4 Marks)
b) Find the truth table for the Boolean expression E = E(x,y,z) where
E = ++ xyz xy z (6 Marks)
c) Define a Boolean Algebra. (5 Marks)
d) Show that these identities hold:
i) x ⊕= + y x y xy ( )( )
ii) x ⊕= + y xy xy ( ) ( )
(5 Marks)
QUESTION FIVE
a) Draw the graph K2,5. (5 Marks)
b) Which connected graphs can be both regular and bipartite? (5 Marks)
c) Prove the Euler’s formula V- E + R = 2. (5 Marks)
d) Show that the maximum number of edges in a simple graph with n vertices is
