M131
Discrete Mathematics
F I N A L E X A M I N A T I O N
Fall / 2013 – 2014
--/01/2014
2 Hours / Time Allowed: / 4 / Number of Exam Pages (including this cover sheet):
Keys
Instructions:
Part 1: MULTIPLE CHOICE QUESTIONS
You may solve all questions. Each question is worth 2 marks. Your grade in this part is that of the best 5 questions, giving a total of 10 possible marks.
Q–1: The negation of the statement “John is rich and he is not famous” is
a) John is neither rich nor famous
b) John is either rich or famous
c) If John is famous, then he is rich
d) If John is rich, then he is famous
e) None of the above
Q–2: The remainder r when -323 is divided by 4 is
a) 3
b) 1
c) -1
d) -3
e) None of the above
Q–3: The relation on A = {a, b, c}, where R = {(a, b), (c, c)}, is
a) Reflexive
b) Transitive
c) Symmetric
d) Antisymmetric
e) None of the above
Q–4: The maximal element of the poset (P(A), Í), A = {1, 2, 3}, is
a) 3
b) {3}
c) {{3}}
d) {1, 2, 3}
e) None of the above
Q–5: The number of vertices in the complete graph K7 is
a) 7
b) 15
c) 21
d) 56
e) None of the above
Q–6: The number of internal vertices in a full binary tree with 31 vertices is
a) 14
b) 15
c) 31
d) 61
e) None of the above
Part 2: ESSAY QUESTIONS
Each question is worth 10 marks. You should answer only FOUR out of the five questions, giving a total of 40 possible marks.
Q–1:
a) [5 Marks] Using the truth table, determine whether the statements and are logically equivalent.
They are logically equivalent:
p / q / r / / / / /F / F / F / T / T / T / F / T
F / F / T / T / T / T / T / T
F / T / F / F / T / T / T / T
F / T / T / F / T / T / T / T
T / F / F / F / F / F / F / F
T / F / T / F / T / T / T / T
T / T / F / T / F / T / T / T
T / T / T / T / T / T / T / T
b) [2×2.5 Marks] Determine whether each of the following is TRUE or FALE, Justify your answer:
i. , domain is the set of real numbers.
F (Take x = -3)
ii. , domain is the set integers.
T (Take y = 0)
Q–2:
a) [5×1 Marks] Let A = {a, b, c}. Determine whether each of the following is TRUE or FALSE:
i. .
F
ii. .
F
iii. .
T
iv. The number of binary relations on A is 9.
F
v. The graph G(A, {(a, a) , (a, b), (a, c)}) is also a tree.
F
b) [3+2 Marks] Consider the integer number a = 257.
i. Is the number a prime? Explain.
ii. Convert (a)8 into hexadecimal.
(257)8 = (010 101 111)2 = (AF)16
Q–3:
a) [2+3 Marks] Let R = {(x, y): x < y +1} be a binary relation on the set A = {1, 2, 3, 4}.
i. List the elements of R.
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
ii. Find the symmetric and transitive closures of R.
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4), (2,1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3) }
R* = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} = R
b) [1+1+3 Marks] Let R and S be relations on A = {a, b, c} defined by the matrices
.
Find the matrices that represent the relations:
i. .
ii. .
iii. .
Q–4:
a) [5 Marks] (Show that the relation R on the set of real numbers, where a R b if and only if a – b is an integer, is an equivalence relation.
R is reflexive: Since a – a = 0 is an integer, means a R a
R is symmetric: If a R b then whenever a – b is an integer, b – a is also integer, means b R a
R is transitive: If a R b and b R c then a – b and b – c are integers, therefore, a – b + b – c = a – c is also an integer, means a R c
b) [1+2+2 Marks] Consider the graph G:
i. Find deg(a).
4
ii. Find the incident matrix of G.
iii. Find the adjacency matrix of G.
Q–5:
a) [2+3 Marks] Which of the following relations on {0, 1, 2, 3} are partial order relations? (unit 21 q1)Explain.
i. R = {(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}.
R is not partial order relation: It is not transitive because (3, 2), (2, 0) belong to R but (3, 0) does not
ii. S = {(0, 0), (1, 1), (1, 2), (2, 2), (3, 3)}.
S is reflexive, transitive and anti-symmetric, hence is a partial order.
b) [1+1+1+2 Marks] Consider the binary tree:
i. What is the height of the tree?
3
ii. Determine whether or not the tree is balanced.
Balanced
iii. How many comparisons with words in the tree are needed to determine if the word SEAWEED is in the tree?
4
iv. Write the in-order traversal of the tree.
BY, SEA, SEASHORE, SELL, SHE, SHELLS, THE