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