UNIVERSITY EXAMINATIONS: 2015/2016
EXAMINATION FOR THE DIPLOMA IN BUSINESS/ INFORMATION
TECHNOLOGY
DIT 204 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)
