**UNIVERSITY EXAMINATIONS: 2015/2016**

**EXAMINATION FOR THE DIPLOMA IN BUSINESS/ INFORMATION **

**TECHNOLOGY **

**DIT204 DISCRETE MATHEMATICS**

**DATE: AUGUST 2016 TIME: 1½HOURS**

**INSTRUCTIONS: Answer Any THREE Questions.**

**QUESTION ONE**

a) i) Define the term Boolean algebra (2 Marks)

ii) Use Boolean identities to prove that x + x = x (2 Marks)

iii) Express the value F (x, y, z) = (x̅ + y)

′ + x̅y as a sum of products and then

complete sum-of- products form. (4 Marks)

b) LetA = {1, 2, 3, 4}. In each relation given below, determine whether they are

reflexive, symmetric and anti-symmetric or transitive is satisfied or not. In each case, justify your

answer.

R1 = {(1,1), ( 1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)} (3 Marks)

R2 = {(1,1), ( 2,2), (3,3)} (3 Marks)

R3 = {(1,1), (1,3), (3,1), (1,2), (3,3), (4,4)} (3 Marks)

R4 = {(1,1), (1,3), (1,4), (3,1) , (2,2), ( 3,3), (3,4), ( 4,4)} (3 Marks)

**QUESTION TWO**

a) Define the following terms as used in graph theory:

i. a directed graph (2 Marks)

ii. a multigraph (2 Marks)

iii. a subgraph (2 Marks)

iv. a Null graph (2 Marks)

b) (i) Draw the graph G of a whose adjacency matrix A = aij (6 Marks)

(ii) Use the graph in b (i) above to find the in – degree, out- degree and

degree of each Vertex (6 Marks)

**QUESTION THREE**

a) Define a proposition as used in propositional logic (2 Marks)

b) Using appropriate truth diagrams, define the following:-

i) Conjunction (2 Marks)

ii) Disjunction (2 Marks)

iii) With the help of a truth table, show that

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (4 Marks)

iv) Show that (p ∧ q) ∧ ∼ (p ∨ q) a contradiction (4 Marks)

c) Using suitable Venn diagrams, illustrate each of the following set operations

i. Union of sets (2 Marks)

ii. Disjoint sets (2 Marks)

iii. Complement of a set (2 Marks)

0 0 1 1 1

1 0 0 1 0

0 1 0 0 0

0 0 0 1 1

0 0 1 0 0

**QUESTION FOUR**

a) Define a function as used in Discrete Mathematics (3 Marks)

b) Given two sets: A= {a, g, k, p, t} and B = {2, 5, 7, 8, 9, 3},

state, with reasons, whether the following are functions or not.

i. f = { (a,2), (g,3), (k,9), (g,3), (t,4)} (3 Marks)

ii. g = { (k,9), (a,8), (g,5), (p,3), (t,3)} (3 Marks)

iii. h = { (k,2), (p,8), (t,b), (g,c), (k,3)} (3 Marks)

c) Differentiate, with examples, amongst surjectives, injectives and

Bijectives (4 Marks)

d) Let A = (4, 7, 9, 6), B = (f, g, h, k) and C= (p, q, r)

if f is the function:

f: A→ B and g: B→ C defined by :

f = {(4, f), (7, k), (9, f) (6, h)}

g = {(f, r), (g, p), (h, p), (k, r)}

Find the composition function f◦g (4 Marks)

**QUESTION FIVE**

a) Define the following terms as used in discrete mathematics

i. A Set (2 Marks)

ii. A Venn diagram (2 Marks)

b) Use the set builder notation to represent the following sets:

i. V, a set of all the English Alphabet vowels (2 Marks)

ii. P, a prime number between 5 and 7 (2 Marks)

c) Write down English statements to represent the following sets:

i. A = {x: x

2 = 4} (2 Marks)

ii. A = {x: x

2 + 1 = 0} (2 Marks)

d) In a class of 50 students,

30 play football, 21 play basketball, 20 plays volleyball, 16 play both football and

volleyball, 13 play both football and basketball and play both volleyball and basketball. If

12 play all the three games, determine:

i. The number of students that play only one game. (2 Marks)

ii. The number of students that play only basketball and football. (3 Marks)

iii. The number of students that play no games at all. (3 Marks)