BIT 1206 BAC 1201 BISF 1101 BSD 1202 DISCRETE MATHEMATICS.

UNIVERSITY EXAMINATIONS: 2021/2022
ORDINARY EXAMINATION FOR BACHELOR OFSCIENCE
INFORMATION TECHNOLOGY, BSc. APPLIED COMPUTING, BSD,
BISF
BIT 1206/ BAC 1201/ BISF 1101/ BSD 1202: DISCRETE
MATHEMATICS
(PARTTIME/ DISTANCE LEARNING)
DATE: DECEMBER, 2021 TIME: 2 HOURS
INSTRUCTIONS: Answer Question One and Any Other Two questions

QUESTION ONE
(a)Use the laws of algebra of sets to simplify

[5Marks]
(b)Prove : if 𝐴 is a subset of the null set 𝜙 ,then 𝐴 = 𝜙.
[5Marks]
(c)Let 𝑆 be a subset of 𝐴 and let ⅈ: 𝑆 ↦ 𝐴 be an iclusion
map .Show that the inclusion map is one-to-one.
[5Marks]
(d)Find the largest interval 𝐷 on which the formulae
𝑓(𝑥) = 𝑥
2
defines a one to one function.
[5Marks]
QUESTION TWO
(a)Find a traversable trail 𝛼 for the graph 𝐺 where𝑉(𝐺) =
{𝐴, 𝐵, 𝐶,𝐷} and 𝐸(𝐺) = [{𝐴, 𝐶},{𝐴,𝐷},{𝐵, 𝐶},{𝐵,𝐷},{𝐶,𝐷}] .
[5Marks]
(b)Draw the multigraph 𝐺 whose adjacency matrix is

[10Marks]
QUESTION THREE
(a)Determine the number of loops and multiple edges in
a multigraph 𝐺 from its adjacency matrix

[5Marks]
(b)Let 𝐺 be a graph with 𝑚 vertices. Describe two major
drawbacks in the computer storage of 𝐺 as its adjacency
matrix 𝐴. [10Marks]
QUESTION FOUR
(a)Prove:There is a path from a vertex 𝑢 to a vertex 𝑣 if and
only if there is a simple path from 𝑢 to 𝑣.
[5Marks]
(b)Consider the statement “if Oscar eats Chinese
food,then he drinks milk”.
(i)Write the converse of the statement.
[2Marks]
(ii)Write the contrapositive of the statement.
[2Marks]
(c) Consider the function 𝑓:{1,2,3,4} ↦ {1,2,3,4} given by

(i) Find 𝑓(1)
[1Mark]
(ii) Find an element 𝑛 in the domain such that 𝑓(𝑛) = 1
[1Mark]
(iii) Find an element 𝑛 of the domain such that 𝑓(𝑛) = 𝑛
[1Mark]
(iv) Find an element of the condomain that is not in the
range [1Mark]
(d)Consider the function 𝑓: ℤ ↦ ℤ given by 𝑓(𝑛) =
{
𝑛 + 1: 𝑛 ⋅ 𝑒𝑣𝑒𝑛
𝑛 − 3: 𝑛 ⋅ 𝑜 ⅆⅆ
(i)Is 𝑓 injective?Prove your answer
[1Mark]
(ii)Is 𝑓 surjective?Prove your answer
[1Mark]