UNIVERSITY EXAMINATIONS 2017/2018
ORDINARY EXAMINATION FOR BACHELOR OF SCIENCE INFORMATION
TECHNOLOGY, BSc. APPLIED COMPUTING
BIT 1206: DISCRETE MATHEMATICS (DAY/EVENING)
DATE: AUGUST, 2018 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and Any other TWO questions
QUESTION ONE
a) In a Boolean algebra, the following are equivalent:
(1) a+b = b
(2) a*b = a
(3) a’+b = 1
(4) a*b’ = 0
Prove the equivalence of (1) and (2) (4 Marks)
b) Prove the Boundedness Laws in Boolean algebra (4 Marks)
c) Show that the following arguments are valid
(i) p→ q, r → q, r ⊢∼ p (4 Marks)
(ii) p↔ q, q ⊢ p (4 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 (3 Marks)
ii) B ∩ C (3 Marks)
Total [30 Marks]
QUESTION TWO
a) Define the following terms
i) One-to-one (or injective ) Functions (2 Marks)
ii) Onto (or surjective) Functions (1 Mark)
iii) One-to-one correspondence (or bijective) Functions (2 Marks)
iv) Invertible Functions (2 Marks)
Are any of these functions one to one? (2 Marks)
c) Consider the functions
f(x) = 2x − 3 and g(x) = x
2 + 3x + 5
Find a formula for the composition functions:
i) g ∘ f (1 Mark)
ii) f ∘ g (2 Mark)
d) Consider the maps
f ∶ A → B, g ∶ B → A
h ∶ C → B, F: B → C
G ∶ A → C
i) Is g∘f defined? If so what is the domain and codomain? (2 Marks)
ii) Is h∘f defined? If so what is the domain and codomain? (2 Marks)
iii) Is F∘h∘G defined? If so what is the domain and codomain? (2 Marks)
iv) Is G∘F∘h defined? If so what is the domain and codomain? (2Marks)
Total[20 Marks]
QUESTION THREE
(a) Draw the multigraph G whose adjacency matrix A is A =
(2 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 (3 Marks)
ii) Determine the number of connected paths of G-A (3 Marks)
(c) Draw the Diagrams of each of the following graphs G (V,E):
i) V = {A,B,C,D}
ii) E = [{A,B},{A,D},{B,C},{B,D}{C,D}] (3 Marks)
iii) V= {a, b, c, d, e}
iv) E= [{a, b}, {a, c}, {b, c}, {d, e}] (3 Marks)
a) Order the sets of numbers: Z, IR,QI , IN using ⊂ (3 Marks)
b) Consider the propositions:
p: Juan is a math major.
f: Juan is a computer science major.
Use symbolic connectives to represent the proposition “Juan is a math major but not a
computer science major.” (4 Marks)
Total [20 Marks]
QUESTION FOUR
a) List the elements of the following sets
i) A = {x: x ∈ N, 3 < ? < 9} (1 Mark)
ii) B = {x: x ∈ N, x
2 + 1 = 10} (1 Mark)
iii) C = {x: x ∈ N, x 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) A survey on a sample of 25 new cars being sold at a local auto dealer was conducted to see which
of the three popular options, air-conditioning (A), radio(R), and power windows (W) were
already installed. The survey found:
15 had air-conditioning
12 had Radio
5 had air-conditioning and Power windows
9 had air-conditioning and radio
4 had radio and power window
3 had all the three options
2 had no options
Find the number of cars that had:
i) Only power windows (2 Marks)
ii) Only air-conditioning (1 Mark)
iii) Only radio (1 Mark)
iv) Radio and power windows but not air-conditioning (1 Mark)
v) Air conditioning and radio but not power windows (1 Mark)
vi) Only one of the options (2 Marks)
Total [20 Marks]
QUESTION FIVE
(a) How many committees of five with a given chairperson can be selected from twelve persons?
(5 Marks)
(b) How many diagonals has a regular polygon with n sides (5 Marks)
(c) Which regular polygon has the same number of diagonals as sides (5 Marks)
(d) Prove P(n,r) =
?!
(?−?)!
= ?(? − 1)(? − 2) … . . (? − ? + 1) (5 Marks)
Total (20 Marks)
