GHANA TECHNOLOGY UNIVERSITY COLLEGE
FACULTY OF INFORMATICS
Diploma INFORMATION TECHNOLOGY (LEVEL 100)
END-OF-SEMESTER EXAMINATIONS, APRIL - MAY 2019
MATH 171: DISCRETE STRUCTURES
Duration:21/2 HOURS
THERE ARE THREE (3) SECTIONS IN THIS PAPER:
SECTIONS A, B, & C
SECTION A & B ON THE QUESTION PAPER
SECTION C IN THE ANSWER BOOKLET
STUDENT’S INDEX NUMBER__________________________
Examiner’s Name: SAMUEL N. N. NORTEY
–...1/6
SECTION A – PROVIDE SHORT ANSWERS MARKS
ON THE QUESTION PAPER
(20 MARKS)
1. What is a RSA Encryption/Decryption, who invented it and cite one application of it?
Description:
Inventor(s):
Application: (3)
2. Using CAESAR CIPHER (i.e. D(p) = (p – 3) mod 26) decrypt the phrase:
“FDHVDU FLSKHU LV DQ HQFUSWLRQ FRGH EXW QRW WKH
VDIHVW” (TRUE/FALSE)
Phrase:
(2)
TRUE/FALSE:
3. How many propositional statements, connectives are in this Compound Proposition?
Using P, Q, R,.. etc as the propositions write it out symbolically.
“Either bananas or apples (or both) are fruit”
Number of Propositions: Number of Connectives:
Symbolically: (2)
4. Find the contrapositive of the statement “If Productivity increases, then wages rises”.
Contrapositive:
(1)
5. If 3N + 2 is odd then N is an _______________ number. Provide the right answer and
state one method of proof to prove this.
An ______________ number; Type of Method of Proof: (1)
6. Write a set specification in a predicate form for the set: S = 2, 7,12,17, 22,...
Ans: S =
(1)
7. Let A = {a, b, c, d} and define a relation R as
R = {(a, a), (a, b), (a, d), (b, a), (b, b), (b, c), (c, b), (c, c), (d, a), (d, d)}.
Is R Transitive? Why?
YES / NO Reason: (2)
–...2/6
8. What type of graph has this adjacency matrix shown below? Prove that total number of
degrees is equal to twice the edges i.e.
0 1 0 0
−1 0 −1 1
0 1 0 −1
0 1 1 0
Type:
Proof:
(4)
9. Find the duality of the following Boolean expression:
(i) 0 0 = 0 (ii) X X 1 = 1 (iii) X 1 = X
(i) (iii) (iii) (2)
10. Write the Minterm and Maxterm for the function F(x, y, z), when: F = (1,3,5, 7)
(i) Minterm:
(2)
(ii) Maxterm:
SECTION B – MCQ’S
(20 MARKS)
CIRCLE THE CORRREC ANSWER ON QUESTION PAPER
11. Each of the 100 students in the first year of Utopia University’s Computer Science
Department studies at least one of the subsidiary subjects: mathematics, electronics and
accounting. Given that (1)
65 study mathematics,
45 study electronics,
42 study accounting,
20 study mathematics and electronics,
25 study mathematics and accounting, and
15 study electronics and accounting, find the number who study:
all three subsidiary subjects?
A) 5 B) 10 C) 15 D) 20 E) 8
12. Mathematics and Electronics but not Accounting? (In Question 11 above)
A) 10 B) 8 C) 12 D) 4 E) 2 (1)
–...3/6
13. Only Electronics as a subsidiary subject? (In Question 11 above)
A) 14 B) 18 C) 12 D) 4 E) 8 (1)
14. What is the cardinality of A B C if A = {1, 2}, B = {x, y, z}, C = {3, 4}?
A) 12 B) 8 C) 10 D) 27 E) 18 (1)
15. Lexicographical Ordering is an example of a POSET?
A) True B) False C) Cannot be determined D) None (1)
16. x2 − 4
Find the inverse, f − | when f ( x) = ?
2
(1)
−| 4x − 2 −|
A) f ( x) = B) f ( x) = 2 x + 4 C)
2
−|
f ( x) = 2 x − 4
−|
D) f ( x) = 4 x E) None of the Above
17. Determine the truth values of the statements where U = {1, 2, 3} is the universal set:
xy, x 2 y − 1; xy, x 2 + y 2 12 ?
A) True, False B) False, True C) False, False D) True, True E) None (1)
18. Given sets A = {a, b, c, d} and B = {1, 2, 3}, determine whether the mapping f from
A to B is a function, One – to – One, Onto, None f = {(a, 1), (b, 2), (c, 3)}?
(1)
A) 1-to -1 B) Onto C) Not a function D) None
19. Let R be the relation defined as R = {(n, m) | m n} , on the set
A = {0, 2, 5, 10, 11, 15}. Then the relation R is:
A) Reflexive, Symmetric B) Reflexive, Symmetric, Transitive
C) Transitive, Symmetric D) Reflexive, transitive and not Symmetric (1)
20. 1
Given that: 12 + 3 2 + 5 2 + ... + (2n + 1) 2 = (n + 1)(2n + 1)(2n + 3) for all n 0 ;
3
What is P(10) ?
A) P(10) = 1771 B) P(10) = 441
C) P(10) = 5 29 D) P(10) = 21 E) P(10) = 55 (1)
21. The following are criteria that algorithm follows except?
A) Generality B) Effectiveness
C) Correctness D) Iterative E) Output (1)
22. List the first 3 values of sum in the algorithm below?
(sum n: positive integer)
sum : = 0;
while i < 10; (1)
sum : = sum + i;
A) 0, 1, 2 B) 0, 1, 3 C) 1, 2, 3 D) 1, 3, 5 E) 4, 5, 6
23. Convert the decimal number 1011.001 to hexadecimal?
–...4/6
A) 3E.A B) 3F.005 C) 11.125 D) B.2 E) 3F3.004 (1)
24. If a relation R on the set {3, 4, 5} be defined by R = {(3, 3), (3, 5), (4, 4) (5, 5)}, then R
is
(1)
A) Reflexive B) Symmetric C) Transitive D) Equivalence E) None
25. Which method of Proof assumes that Premise is true and Conclusion is false?
A) Direct B) Indirect C) Induction D) Contradiction E) None (1)
26. Convert the hexadecimal number 2A2 to binary?
A) 1010110000 B) 1010110011 C) 1111000001 D) 1010100010 E) 1000110110 (1)
27. The bit string for the set A = {1, 2, 5} and B ={7, 8, 10} (with universal set of natural
numbers less than or equal to 10), what is A B is ___________________?
A) 0101010101 B) 1100101101 C) 1010010101
D) 0010010101 E) 1100101010 (1)
28. The inverse of the function f ( x) = ( x + 2)3 is ________________?
1 1 1
A) f −1 ( x) = ( x − 2) 3
B) f −1 ( x) = x 3
−2 C) f −1 ( x) = ( x) 3
D) f −1 ( x) = ( x − 2) E) f −1 ( x) = ( x − 2) 3 (1)
29. Let f and g be the function from the set of integers to itself, defined by
f(x) = 2x + 1 and g(x) = 3x + 4. Find ( f ° g)
A) 6x + 9 B) 6x + 7 C) 9x + 4 (1)
D) 4x + 3 E) 9x
30. The minimized expression of ABC + ABC + ABC + ABC is?
A) A + C B) BC C) C D) C E) B +C (1)
–...5/6
SECTION C – ESSAY QUESTIONS
(20 MARKS)
ANSWER ALL
ANSWER THIS SECTION IN THE ANSWER BOOKLET
1. (a) In the following argument, determine the validity or otherwise of the Statement:
" If there is milk, then I will drink coffee. If there is bread, then I will drink
coffee. There is no milk and there is no bread. I will drink coffee"
(3)
(b) Using truth table, determine the validity of the argument below:
P→Q
Q R
R
(2)
(c) (i) Use the K-map to minimize the Boolean expression:
PQR + PQR + PQR + PQR + PQR + PQR (3)
(2)
(ii) Encrypt the word CRYPTOGRAPHY using Caesar Cipher
2. (a) How many possible arrangements can be formed from the letters in
(2)
“CRYPTOCURRENCY”
(b) (i) Generate up to the tenth and twelfth rows of the Pascal triangle.
(ii) Verify that a, b and c are three consecutive numbers in the tenth row then
(2)
a + 2b + c gives an entry in the twelfth row.
(c) (i) Draw the digraph with vertices {1, 2, 3, 4, 5, 6} whose adjacency matrix is
1 0 0 1 0 0
1 0 1 0 0 1
0 1 1 0 1 0
1 0 0 1 1 1
0 0 0 1 0 1
0 1 1 1 1 0
Write out the adjacency list?
(3)
(ii) Given the digraph below: Prove the Handshaking Theorem.
(3)
–...6/6
