UNIVERSITY EXAMINATIONS: 2012/2013
FIRST YEAR EXAMINATION FOR THE BACHELOR OF SCIENCE
IN INFORMATION TECHNOLOGY
BIT 1206 DISCRETE MATHEMATICS
DATE: DECEMBER, 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE
a) Prove that the intersection of sets is associative. (3 Marks)
b) Find the gcd of 427 and 616 and express it in the form .
(5 Marks)
c) Use an adjacency matrix to represent the graph shown below: (4 Marks)
d) Let p be the statement “The South West monsoon is very good this year” and q be
the statement “ The Rivers are rising”. Give the verbal translations of:
h) How many permutations can be made with the letters of the word MISSISSIPPI
taken all together. (2 Marks)
QUESTION TWO
a) A TV survey shows that 60% people see program A, 50% see program B, 50%
see program C, 30% see program A and B, 20% see program B and C, 30% see
program A and C and 10% do not see any program. Find (9 Marks)
i) What percentage see program A, B and C?
ii) What percentage see exactly two programs?
iii) What percentage see program A only?
b) How many numbers greater than a million can be formed with the digits 1, 7, 1, 0,
7, 3, 7? (4 Marks)
c) i) Define a Boolean Algebra. (3 Marks)
ii) Construct an input/output table for the Boolean function defined as
follows:
QUESTION THREE
a) Using the principle of mathematical induction, prove that
QUESTION FOUR
a) Define the following terms as used in graph theory:
i) Graph
ii) Degree of a Vertex
iii) Path
iv) Trail
(8 Marks)
b) Determine the number of loops and multiple edges in a multigraph G whose
adjacency matrix is
QUESTION FIVE
a) Show that the relation “ (subset ) defined on the power set P(A) of the set A is
a partial order relation. (6 Marks)
b) What are logical connectives? Explain the following terms
i) Negation
ii) Conjuction
iii) Disjunction (7 Marks)
c) Let p be Eric reads Newsweek, q be “ Eric reads the New Yorker” and r be “ Eric
reads Time. Write each of the following in symbolic form:
i) Eric reads Newsweek or the New Yorker but not Time
ii) Eric reads Newsweek and the New Yorker or he does not read Newsweek
and Time.
iii) It is not true that Eric reads Newsweek but not Time
iv) It is not true that Eric reads time or the New Yorker but not Newsweek.
