(Q

a
~.
UNIVERSITY OF EDUCATION, WINNEBA
COLLEGE OF TECHNOLOGY EDUCATION, KUMASI
.

DEPARTMENT OF INFORMATION TECHNOLOGY EDUCATION

END OF FIRST SEMESTER EXAMINATION. DECEMBER 2019/2020

COURSE CODE ITC 117 -

COURSE TITLE DISCRETE MATHEMATICS
DURATION 2 HOURS 30 MINUTES
LECTURER
INSTRUCTION(S) .
DR. F. O. BOATENG AND KWAME O. BEMPAH
'
Answer all questions .
• Circle the correct answer on the question paper.
• Shade the letter that corresponds to the correct
answer to each question on the scannable form
provided.
• If your answer does not appear in the options
provided, write yours on the question paper and shade
the letter 'E'.

INDEX NUMBER

CLASS

SIXTY (60) MARKS

1. In which of the following statements is exclusive OR implied?

A. You can use birth certificate or passport for the Ghana Card registration.
B. I will vote for my preferred Assemblyman or Unit Committee Members.
C. I will go and vote or wait for the counting of the votes.
D. The election will be conducted on Monday or Friday.

2. Determine the formula or rule that generates the terms of the sequence 15, 8, 1, -6, -13,
-20, -27, ....

A. 8 + 7n C. 22 + 7n
B. 15-7n D. 22 -7n
.
3. The message HDW was encrypted using Caesar cipher. The Decrypted message is
A. DPE C. lFY
B. KGZ D. LHA

4. The number of elements in the power sets of the sets {a, b, {c, d}} is:
A. 16 C.8
B. 4 D. None of these

Page 1 of 8
2
· -7x+8
5. Letf be a function R to R such that f(x) =X-;2:---- . Find the set of values for
x +2x-8
whichf is undefined.
A. x E{2,4} C. x E{-2,4}
B. x E{-2,-4} D. x E{2,-4}

6. When the greatest common divisor of two integers is exactly one, then it means
A. They are odd prime C. They are not even numbers
B. They are relatively prime D. None ofthese

7. The message PLY was encrypted using the functionf(p) = (2p + 9) mod 26. Decrypt
this message.
A. BIG C.DOG
B. MAD D.DOT

8. Iff(x) = cos x and g(x) = x3, then if 0 g)(x) is:

A. (cos x)3 C. xcosx
B. cos3x D. cos x'
C.

9. p -+ q is logically equivalent to:

A. - q-+p C. - p r. q
B. - p-+q D. - pV q

10. The statement [- q A (p -+ q)] -+ - pis

A. Contingency C. Tautology
B. Satisfiable D. Contradiction

11. Which of the following pair is not congruent with modulo 7 ?

A. 10,24 C. -31, 11
B. 25, 56 D. - 64 , - 15

12. Letf defmed recursively by!o = -1, ji = 2 and fen + 1)= fen -1), for n = 1, 2, ....:
fen)
Findf(5).
A. 1/8 C. - 32
B. 1/2 D.-l

13. Find the values of the Boolean functionsf(x, y) = (x EB y)l(x t y).

A. 0000 C. 0001
B. 1111 D. 1000

14. Evaluate (1 IO)"!' [(1El71) I (0+1)].

A. 1 C. -1
B. 0 D. Y2

Page 2 of 8
15. The number of distinguishable permutations of the letters in the word BANANA are
A. 60 C.20
B. 36 D.I0

16. Let R be a relation from A to B and is defined as {(1, a), (I, b), (4, b), (2, a), (4, c)}.
Find the R-relative set, R (4).

A. {a, b, c} C. {a, b, c, d}
B. {a, d} D. {b, c}

17. Let Q(x) mean x < 2 what is the truth value of \/x Q(x), where D = real numbers?
A. TRUE
B. FALSE
18.Let A = {l, 2} and B = {3, 4}. Let R be a relation from set A to set B defined as
(1, 3), (2, 4). The complement of this relation is given by:

A. (1,2), (2, 3) c. (1, 4), (2, 3)

B. (1,3), (1,4), (2,3), (2,4) D. (1,4)

19. If a relation R on a set A is defined by (x, y) E R ~ (y, x) f/:. R for x =j:. y, then the relation is
A. Symmetric C. Asymmetric
B. Reflexive D. Irreflexive

20. An Eulerian walk in a graph G= (V, E) is a walk which uses

A. Each vertex exactly once C. Each edge exactly once
B. Each vertex and edge once D. Each edge at least once

21. For every n EN satisfying n ~ 3, the cycle graph en, b(V) is always equal to:
A.3 C.2
B. 4 D.5

22. If A = {I, 2, 3} and let R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2,3), (3, 2)}, then R is:
A. Reflexive, symmetric but not transitive
B. Symmetric, transitive but not reflexive
C. Reflexive, and transitive but not symmetric
D. An equivalence relation

23. Let R be a relation defined on Z as follows: (a,b) ER <=> a2 +b2 = 25, then domain of R
IS:
A. {3, 4, 5} C. {0,±3,±4,±5}
B. {O,3, 4, 5} D. None of these

Page B of B
24. The relation R defined on the set A = {1,2,3,4,5} by R = {(a,b) : la2 - b21 < 16} is given by:
A {(I, 1), (2, 1), (3, 1), (4,1), (5, 2)} C. {(3, 3), (4, 3), (5, 1), (3, 4)}
B. {(2, 2), (3, 2), (4, 2), (4, 2)} D. None of these

25. Let A {I, 2, 3} and B = {I, 4, 6, 9} and R is a relation from A to B defined by 'x is greater
=
thany'. Then the range of R is given by:
A. {I, 4, 6, 9} C. {I}
B. {4, 6, 9} D. {I, 2, 3}

26. Given that m= qn + r is a division algorithm where m, q, n, r E Z+ and 0 ~ r < n. If

m=16 and n=3, find the values of q and r.
A q = 4, r = 3 C.q=6,r=-3
B. q = 5, r = 1 D. q=4, r=4

27. What is the degree of the Boolean function defined by F(w,x,y,z) = wxy+xz+w?
A 3 C. 16
B. 4 D.32

28. A is an ordered collection of objects.

A Set C. Relation
B. Proposition D. Function

29. Given the setA = {17, 19,21,23,25,27, 29} and B = {21, 23, 27, 35}, what is the
cardinality of the power set PCB - A).
Al C.6
B. 2 D.16

30. Evaluate (11011 v a 1010) EB(1 0001,} 11011)

A 1 1010 c. a 1010
B. 1 1110 D. 1 1111

Use the given information to answer question 31 and 32.

Let U = {1,2,3,4,5,6, 7,8,9,10} and the ordering of elements of Uhas the element ill

increasing order. Let A = {I, 2, 4, 6, 10} and B = {1,3, 5, 6, 7, 8}. Find the comp er
representation of the following set operations:

31. (AnB)-B.
A a 101 000 all C. 1 010 101 010
B. a 101 000 101 D. a 000 111 111

32. (AEBB)nA.
A. 1 010 101 010 c. a 101 010 101
B. a 110 101 000 D. a 101 000 001

Page 4 of 8
33. A literal is a Boolean variable or its completement.
A. True
B. False

34. Find the Boolean minterm that equals 1 if Xl = x4 = a and X2 = X3 = Xs = I, and equals a
otherwise.
A. XlX2X3X4XS C. XlX2X3X4XS
B. Xl X2X3X4XS D. XlX2X3X4XS

35. Find the general rule of the sequence -t, %, - 2~' 881,....
A. u, -- - -31(13 )n-l 5
C. U; =-t+'9(n-l)

B. u, = -t-~(n-1) D. v. = -t( -1 r
36. When is the quantification 3x\iy P(X,y) true for the statement Pix, y)?
A. There is an X for which P(x, y) is true for every y
B. For every x, there is a y for which P(x, y) is true
C. There is a pair x, y for which P(x, y) is true
D. P(x, y) is false for x, y

37. If the product of two integers is 27 310 51 79 and their greatest common divisor is
23345, what is their least common multiple?

A. 27385179 C.243451711
B. 24365179 D.385179

Use the following graph to answer questions 38 to 41.

38. Which of the following is not true about the given graph?
A. There exist a Hamiltonian cycle C. The number odd vertices is even
B. There exist an Eulerian walk D. The number of even vertices is odd

39. Determine the elements in the 3rd row of the adjacency matrix in the order 1,2,3,4,5,6.
A. 010110 C. 101101
B. 010110 D.101111

Page 5 of 8
40. Determine the elements in the 4th column of the adjacency matrix in the order 1, 2, 3,4, 5, 6.
A. 010110 C.OII011
B. 110110 D. 101111

4l. What is the sum of the value of the degree taken over all the vertices on the graph?
A. 20 C.21
B. 22 D.25

Use the following digraph to answer questions 42to 45.

A network of 5 computers is represent in a digraph as
b

42. Which of the following is not a relation, R on the vertices {a, b, c, d, e}?
A. aR d C. aR e
B. c R b D. e R b

43. Computer C is reachable from computer e.

A. True
B. False

44. Computer a is not reachable from computer d.

A. True
B. False

45. Determine the elements in the 2nd row of the adjacency matrix of the digraph in the order
a, b, c, d, e.
A. 10110 C.00110
B. 00001 D.00111

Use the following digraph to answer questions 46 to 47.

LetAj={2i+l, 3i+2, 4i+3, 5i+4}fori={l,2,3, ...}.
4

46. Find U~- A j•

j=3
A. {7, 9, 11, 14, 15, 19, 24} C. {II, 14, 15, 19, 24}
B. {9, 14, 19, 24} D.{}

47. Find nAj EBA3

2

A. {7, 11, 15, 19} C. {9, 14, 19, 24}

B. {7,9, 11, 14, 15, 19, 24} D. {II, 14, 15, 19, 24}

48. Evaluate '~)3k - k)

k=O
A. 34 C. 46
B. 36 D.56

Page 6 of 8
I 2
49. Evaluate L IT (2m - 2n).
m=On=m+l
A.O C.-3
B. 3 D.6

Use the following argument to answer questions 50 to 52.

Let P(x,y) be the statement" 3x < 4y -1" and the universe of discourses are gives as
1 3
follows: DI = {x: 0,1, 2} and D, = {y: -, -, 2}
2 2
Determine the truth value of the following quantifications.

50. 3x\iy P(x,y)

A. True
B. False

51. \ix3yP(x,y)
A. True
B. False

52. 3x3y P(x,y)

a) True
b) False

Use the following argument to answer questions 53 to 55.

Let p, q and r be propositions such that
p: I vote in the Assemblyman election
q: My preferred Assemblyman won
r: I have development in my area

53. I voting in the Assemblyman election or my preferred Assemblyman winning IS

necessary for me to have development in my area.
A. (p v q) ~ r C. (r ~ p) v q
B. r~(pvq) D. (p~r)vq

54. If! did not vote in the Assemblyman election and my preferred Assemblyman won, then
I will not have development in my area.
A. (- P /\ q) ~- r c. - P /\ (q ~- r)
B. -r~(-p/\q) D.-r~(-pvq)

55. It is not the case that whenever I have development in my area then my preferred
Assemblyman won.
A. - (r ~ q) C. -r~q
B. -(q~r) D. -q~r

Page 7 of 8
Use the following argument to answer questions 56 to 57.
Voting for an Assemblyman is not sufficient for me to have development in your area.
I have development in my area. Therefore, it is not the case that voting for an
Assemblyman is necessary to have development in your area.

Let V and D represent the following statements in the argument above.

V: Voting for an Assemblyman
D: I have development in my area

56. Which of the following is the symbolic form of the argument?

A. (V -+-D)/\D~-(D-+V) C. -(V -+D)/\D~-(V -+D)
B. -(V-+D)/\D~-(D-+V) D. -(V-+D)/\D~-V-+D

57. Determine the validity of the argument.

A. Valid
B. Not valid
C. The validity of the argument cannot be determined
D. None ofthe above

Use the following logical circuit to answer questions 58 - 60.

;
z
t~------------
~
A

x~
y ~ B

z--~

58. Provide the expression for the output labelled A.

A. xyzEBxyz C. (x+ y+z)EB(x+ y+z)
B. xyz.J..xyz D. (x+y+z).J..(x+y+z)

59. Provide the expression for the output labelled B.

A. xyz C. x+ y+z
B. Xyz D. x + y + z

60. Provide the expression for the output labelled C.

A. (xyz EB xyz) Z (x + y + z) C. (xyz.J.. xyz) Z (x + y + z)

B. (xyz ) + Z + ( x + y + z EB (x + y + z) ) D. (xyz EB xyz) + Z + (x + y + z)

Page 8 of 8