UNIVERSITY EXAMINATIONS: 2018/2019
ORDINARY EXAMINATION FOR BACHELOR OF SCIENCE INFORMATION
TECHNOLOGY, BSc. APPLIED COMPUTING, BSD, BISF
BIT 1206: DISCRETE MATHEMATICS (DAY/EVENING)
DATE: AUGUST, 2019 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and Any other TWO questions
QUESTION ONE
a) Let a = 1101010 and b = 1011011 in B7 [seven bit sequences]. Find a + b, a ∗ b
and a′ (4 Marks)
b) Determine whether or not the following is a sub algebra of D70 [Divisors of 70]
i) X = {1, 5, 10, 70} (4 Marks)
ii) Y = {1, 2, 35, 70} (4 Marks)
c) Test the validity of the following argument:
If it rains, Erick will be sick.
It did not rain.
Erick was not sick. (8 Marks)
d) Show that p ˄ q logically implies p ↔ q (4 Marks)
e) Consider a graph where
V (G) = {A, B, C,D} and
E (G) = [{A, B},{B, C}, {B,D},{C,D}]
Find the degree and parity of each vertex in G (4 Marks)
f) Let:
U = {1, 2, 3, … . .8, 9}
A = {1, 2, 3, 4}
B = { 2, 4,6,8}
C= { 3, 4,5,6} be sets
Find
i) A ∪ B (1 Mark)
ii) B ∩ C (1 Mark)
Total [30 Marks]
QUESTION TWO
a) Suppose f: A → B and g: B → C one to one functions. Show that (g ⃘f) ∶ A → C is
one to one (4 Mark)
b) Recall that a function f: IR→ IR may be identified with its graph. Give a geometrical condition
which is equivalent to
i) f is one to one (1 Mark)
ii) f is onto (1 Mark)
iii) f is invertible (1 Mark)
c) Write the negation of each of statement as simply as possible
i) If he studies, he will pass the exam (3 Marks)
ii) He swims if and only if the water is warm. (3 Marks)
iii) If it snows, then he does not drive the car. (3 Marks)
d) Let 𝑝 denote, “He is rich” and let 𝑞 denote, “He is happy”. Write each statement in symbolic
form
i) Being rich is a necessary condition to being happy (1 Mark)
ii) One is never happy when one is rich (1 Mark)
iii) He is poor only if he is happy (1 Mark)
iv) To be rich means the same as to be happy (1 Mark)
Total [20 Marks]
QUESTION THREE
a) How many Diagonals does a regular polygon with 𝑛 sides have? (5 Marks)
b) Which regular polygon has the same number of diagonals as sides? (5 Marks)
c) Find the number 𝑚 of triangles that can be formed by the vertices of a regular
polygon with n sides (and hence 𝑛 vertices) (5 Marks)
d) Find the number 𝑚 of triangles that can be formed by the vertices of a regular polygon with 𝑛
sides (and hence 𝑛 vertices) if the sides of the polygon are not to be sides of any
triangle. (5 Marks)
Total [20 Marks]
QUESTION FOUR
a) List the elements of the following sets
i) A = {𝑥: 𝑥 ∈ 𝐍, 3 < 𝑥 < 9} (1 Mark)
ii) B = {𝑥: 𝑥 ∈ 𝐍, 𝑥
2+1 = 10} (1 Mark)
iii) C = {𝑥: 𝑥 ∈ 𝐍, 𝑥 is odd , −5 < 𝑥 < 5} ` (1 Mark)
b) i) Draw a Venn diagram of sets A, B, C where A ⊆ B, sets A and C are disjoint
but B and C have elements in common (4 Marks)
ii) Write A ∩ (B ∪ C) as the (disjoint) union of fundamental products. (5 Marks)
c) Let G be the graph below:
Determine whether each of the following is a closed path, trail, simple path or cycle.
i) (B, A, X, C, B), (1 Mark)
ii) (X, A, B, Y), (1 Mark)
iii) (B, X, Y, B). (1 Mark)
d)
i) Define the subgraph G – e where e is an edge in G (1 Mark)
ii) Define a bridge for a connected graph G (1 Mark)
iii) Let G be the graph below.
Find:
a) G – X (1 Mark)
b) G – Y (1 Mark)
c) G – Z (1 Mark)
Total [20 Marks]
QUESTION FIVE
(a) Draw the multigraph G whose adjacency matrix A is A =
(5 Marks)
(b) Let G be the graph where
V (G) = {A, B, C, X, Y, Z} and
E (G) = [{A, C}, {A, X}, {A, Y}, {B, Y}, {B, Z}]
i) Find G-A (2 Marks)
ii) Determine the number of connected components of G-A (2 Marks)
(c) Draw a diagram of each of the following graphs G (V, E):
i) V = {A, B, C, D}
E = [{A, B}, {A, D}, {B, C}, {B, D}, {C, D}] (2 Marks)
ii) E= [{a, b}, {a, c}, {b, c}, {d, e}] (2 Marks)
d) V= {a, b, c, d, e} Determine the contrapositve of each statement.
i) If he has courage he will win. (1 Mark)
ii) It is necessary to be strong in order to be a sailor. (1 Mark)
iii) Only if he does not tire will he win. (1 Mark)
iv) It is sufficient for it to be a square in order to be a rectangle. (1 Mark)
v) Prove: (p → q) if 𝑥 is an integer and 𝑥
is odd, then 𝑥 is odd (3 Marks)
Total [20 Marks]
