UNIVERSITY EXAMINATIONS: 2011/2012
FIRST YEAR EXAMINATION FOR THE BACHELOR OF SCIENCE
IN INFORMATION TECHNOLOGY
BIT 1206 DISCRETE MATHEMATICS
DATE: AUGUST, 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE
a) In a survey of 100 students, the numbers studying the various languages were
found to be: Spanish 28, German 30, French 42, Spanish and German 8, Spanish
and French 10, German and French 5, all three languages 5.
i. How many were studying no language?
ii. How many had French as their only language?
(5 Marks)
b) Give the converse, contrapositive and inverse of the following implication: “ If it
rains today, l will go to college tomorrow”. (6 Marks)
c) Write the following statements in Symbolic form:
i. The sun is bright and the humidity is not high.
ii. If you do not see me tomorrow, it means l have gone to Chicago.
(4 Marks)
(5 Marks)
QUESTION TWO
a) Test the validity of the following argument. If two sides of a triangle are equal,
then the opposite angles are equal. Two sides of a triangle are not equal. The
opposite angles are not equal. (6 Marks)
b) Given the following propositions: p: food is good, q: service is good, r : restaurant
is 5 Star. Write the following in Symbolic notation:
i. Either food is good or the service is good or both
ii. Either food is good or service is good but not both
iii. Food is good while the service is poor
iv. It is not the case that food is good and the rating is five star
v. If both the food and the service are good, then the rating will be 5 Star.
vi. It is not true that 5 Star rating always means good food and good service.
(6 Marks)
(7 Marks)
QUESTION THREE
a) Write the following statement in symbolic form: There will be no test
examination tomorrow if Professor is out of town or there’s a Matatu Strike.
(3 Marks)
b) Show that xy + yz + xz = xy + yz + xz (7 Marks)
c) Show that these identities hold:
i. x ⊕= + y x y xy ( )( )
ii. x ⊕= + y xy xy ( ) ( )
(4 Marks)
d) Translate the distributive law into logical equivalence and
prove. (8 Marks)
QUESTION FOUR
a) For each pair of integers a and b, find integers q and r such that
(6 Marks)
c) 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? (6 Marks)
QUESTION FIVE
a) Define the following terms as used in Graphs:
i. Directed Graph
ii. Degree of a vertex in a graph
iii. Path
iv. Connected graph
v. Subgraph.
b) Consider the graph G below:
(10 Marks)
Find:
i. All simple paths from A toF
ii. All trails from A to F
iii. All cycle which include vertex A
iv. All cycles in G.
(10 Marks)
