TIC1201 Discrete Structures (AY2019/20) Midterm Exam Solution

This document presents the complete solution to the TIC1201 Discrete Structures midterm exam administered at the National University of Singapore during Semester 2 of AY2019/20. The exam covers core concepts in discrete mathematics, including truth tables, logical arguments, set theory, relations, and mathematical proofs. The solution provides detailed answers to each of the six questions, demonstrating the application of these concepts. Question 1 analyzes the validity of an argument using a truth table. Question 2 explores relations and ordered pairs. Questions 3 and 4 involve evaluating statements and proving divisibility using mathematical induction. Question 5 delves into the rationality of logarithms, and Question 6 solves a logic puzzle involving deduction. The document provides step-by-step explanations and calculations, making it a valuable resource for students studying discrete structures.

DISCRETE MATHEMATICS
MIDTERM EXAM
STUDENT ID:
[Pick the date]

Question 1
The requisite truth table is shown below.
p q p→ q q → p • p • p ∧ q (p→ q ) ∧ (q → p )
T T T T F F T
T F F T F F F
F T T F T T F
F F T T T F T
From the above truth table, it is evident that the premise does not lead to the conclusion and
hence the argument in the given case would be considered as invalid.
Question 2
a) The list of all ordered pairs of relation take would contain the following elements.
 (Adi, TIC1201)
 (Adi, TIC2001)
 (Deepak, TIC1201)
 (Deepak, TMA2102)
 (Lily, TIC2001)
 (Lily, TIC1001)
 (Lily, TMA2102)
b) False since certain input values have more than one output
c) True since (TIC1001,SR7) belongs to the relation held_in.
d) The list of all ordered pairs of relation take would contain the following elements.
 (SR1,Lily)
 (LT15, Adi)
 (LT15, Lily)
 (SR7, Lily)
 (LT15, Deepak)
 (SR10, Lily)
 (SR7, Adi)
 (SR1, Adi)
 (SR10, Deepak)
Question 3
a) True

b) False
c) False
d) True
e) False
f) True
Question 4
2.1 – Substitute n = 0 in the expression 9n – 4n
2.2 – Simplify using simple algebra i.e. 90 – 40 = 1-1 = 0
2.3 – 0 when divided by 5 would leave a remainder of 0
3.1.2 = 9k+1 – 4k+1 = 9k*91 – 4k*41 (Using law of exponents)
3.1.3 = 9k*91 – 4k*41 = (5+4)*9k – 4*4k
3.1.4 = 4*9k -4*4k + 5*9k = 4(9k – 4k) +5*9k (Using splitting of terms)
3.1.5 It is known that 9k – 4k is perfectly divisible by 5 and hence can be reflected as 5p
where p is any natural number
3.1.6 = 4*(5p) +5*9k (By substituting of 9k – 4k as 5p)
3.1.7 – Both the above terms are divisible by 5 and hence the remainder would be zero.
Question 5
1.3 By raising both sides to the power of b, we get 5b = 3a by basic algebra
1.4 In order for the above equality relation to be satisfied, it is essential that 5 must be
divisible by 3
1.5 However, 3 and 5 are both co-prime numbers which implies that the only common factor
for the two numbers is 1.
1.6 Therefore, the initial assumption of log35 being rational is wrong.
Question 6
The numbers on Aiken’s and Dueet’s foreheads would be 17 and 18 respectively.
The explanation for the above is as follows. If Dueet sees 17 on Aiken’s forehead, then this is
essentially the product of two numbers. However, 17 being a prime number has only two
factors namely 1 and 17. Thus, it is possible for Dueet to guess the number written on his

forehead which would be 1+17 = 18. On the contrary, Aiken would see the number 18 as sum
which can be produced in a host of ways such as (12+6), (9+9), (8+10), (17+1). Without
knowing the number written on Aiken’s forehead, it would be impossible for him to ascertain
the correct pair of numbers.