**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.