Xi’an Jiaotong-Liverpool University

PAPER CODE EXAMINER DEPARTMENT TEL

K.L. Man /
CPT 107 CPT 1509
G. Mogos

2022/23 SEMESTER 1 – Online Mock Exam

BACHELOR DEGREE – Year 2

Discrete Mathematics and Statistics

TIME ALLOWED: 2 hours

INSTRUCTIONS TO CANDIDATES

1. The Mock Exam should be done individually.

2. Total marks available are 100.

3. The number in the column on the right indicates the marks for each question.

4. Answer all questions.

5. Answers should be written in English.

6. Relevant and clear steps should be included in your answers.

7. Your solutions should be submitted electronically through the Learning Mall via
the submission link.

8. The naming of your solutions (in pdf) is as follows: CPT107_A_001_StudentID.pdf

(e.g., CPT107_A_001_1234567.pdf)

9. Answers can also be handwritten, fully and clearly scanned, or photographed for
submission as one single PDF document through the Learning Mall via the
submission link.

Notes:
◼ To obtain full marks for each question, relevant and clear steps need to be included
in the answers.

PAPER CODE: CPT107/22-23/S1 Page 1 of 6

 Xi’an Jiaotong-Liverpool University

◼ Partial marks may be awarded depending on the degree of completeness and clarity.

Question 1: Proof Techniques [12 marks]

(a) Use proof by contradiction to show the following statement: if a and b are rational numbers

and b ≠ 0, then a - b√3 is irrational.

(4 marks)

(b) √75 is irrational. If you think that it is true, prove it. If not, explain why.

(6 marks)

(c) Let x ∈ ℤ and 0 ≤ x, use proof by induction to show that:

2(1 + 2 + 4 + ⋯ + 2𝑥 ) = 2𝑥+2 − 2.

(2 marks)

Question 2: Set Theory [11 marks]

(a) Let A, B and C be non-empty sets, then A – C = (B – C) ∪ (𝐵 − 𝐶). If you think that it is true,
prove it. Otherwise, give a counterexample.

(3 marks)

(b) Let X and Y be sets, then 𝑋 ⊆ 𝑌 if and only if 𝑋 ∩ 𝑌 = 𝑋. If you think that it is true, prove
it. Otherwise, give a counterexample to show that it is false.

(5 marks)
PAPER CODE: CPT107/22-23/S1 Page 2 of 6
 Xi’an Jiaotong-Liverpool University

(c) The football cup Liverpool F.C. has 35 players, 29 players play in attack, 16 players play in
midfield and 10 players play in both attack and midfield. Find the number of players who play:
1. in attack only.
2. in midfield only.
3. in neither attack nor midfield.
(3 marks)

Question 3: Relations [22 marks]

(a) Let 𝑋 = {a, b, c, d, e, f} and let S be a relation on X such that:

𝑆 = {(a, b), (d, e), (e, f), (b, a), (c, d)}. Find the transitive closure of the relation S on X.

(5 marks)

(b) Let 𝑋 = {a, b, c, d, e} and let S be a relation on X such that:

𝑆 = {(a, a), (a, c), (a, d), (a, e), (b, b), (b, c), (b, d), (b, e), (c, c), (c, d), (c, e), (d, d), (e, e)}.
Prove or disprove that S is a partial order. If S is a partial order, draw its Hasse diagram.

(6 marks)

(c) Let A and B be both transitive relations on the set S. Prove or disprove the following:
1. A ∩ B is also transitive.
2. A ∘ B is also transitive.
3. “A ∘ B is also transitive” implies “A ∩ B is also transitive”.

(6 marks)

(d) If A is an equivalence relation over a set S, then A-1 is an equivalence relation over S. If you
think that it is true, prove it. If not, give a counterexample.

(5 marks)

PAPER CODE: CPT107/22-23/S1 Page 3 of 6

 Xi’an Jiaotong-Liverpool University

Question 4: Functions [19 marks]

(a) Let 𝑓: ℝ → ℝ such that ∀x,y ∈ ℝ (x < y → f(x) < f(y)).

1. Prove or disprove that f is injective.
2. All injective functions from ℝ → ℝ are of the type of function f.
If you think that it is true, prove it. If not, give a counterexample.

(5 marks)

(b) Let 𝑓: ℤ → ℤ such that ∀x ∈ ℤ f(f(x)) = x. Prove or disprove that 𝑓 is a bijection.

(4 marks)

(c) Prove or disprove the following:

1. The composition of two functions can never be commutative.
2. The composition of three functions is always associative.

(5 marks)

(d) Let 𝑓: 𝐴 → 𝐵 and 𝑔: 𝐵 → 𝐶 be two bijective functions.

1. Prove or disprove that both (𝑔 ∘ 𝑓) ∘ (𝑓 −1 ∘ 𝑔−1 ) and (𝑓 −1 ∘ 𝑔−1 ) ∘ (𝑔 ∘ 𝑓) are
identity mappings/functions.

2. Consider the equality: (𝑔 ∘ 𝑓) ∘ (𝑓 −1 ∘ 𝑔−1 ) = (𝑓 −1 ∘ 𝑔−1 ) ∘ (𝑔 ∘ 𝑓). If you think

that it is generally true, prove it. Otherwise, give a case/an example to show the equality
holds.
(5 marks)

Question 5: Logic [16 marks]

(a) For each of the two cases 1. and 2. below, show whether the statement on the left-hand side is
equivalent to the statement on the right-hand side:
PAPER CODE: CPT107/22-23/S1 Page 4 of 6
 Xi’an Jiaotong-Liverpool University

1. ¬((¬𝑥 ∧ ¬𝑦 ) ∨ (¬𝑥 ∧ 𝑦)) = 𝑥

2. ¬x ∨ (𝑦 ∧ 𝑧) = 𝑥 → (𝑦 → 𝑧)
(4 marks)

(b) Without using any truth table, show that ~(𝑃 ∧ (𝑄 ∨ 𝑅)) ∨ ((𝑃 ∧ 𝑄) ∨ (𝑃 ∧ 𝑅)) is a
tautology.

(4 marks)

(c) Let H be the set of all people. For a,b ∈ 𝐻, the predicate Likes(a,b) means person a likes person
b. Express the following sentences into the first-order logic formulaes:
1. One likes everyone.
2. Given any pair of two people, one of them likes the other.
3. Given any pair of two people, exactly one of them likes the other.

Explain what you understand by ∀a ∃b Likes(a, b). Consider the equality:

∀a ∃b Likes(a,b) = ∃b ∀a Likes(a,b). If you think that it is true, prove it. Otherwise, explain
why the equality does not hold.

(8 marks)

Question 6: Combinatorics and Probability [20 marks]

(a) CPT107 has 300 students. Prove that there are at least two students with their last name
starting with the same letter.
(2 marks)

(b) A tennis team consists of seven male members and eight female members.
1. How many ways are there to choose a manager, associate manager, captain and vice-
captain under the condition that:
• the manager must be a female member, and
• the associate manager be a male member, and
• these four roles must be filled up by four different members?
PAPER CODE: CPT107/22-23/S1 Page 5 of 6
 Xi’an Jiaotong-Liverpool University

2. How many ways are there to choose a sub-team of five members that has at least one
female member?
3. How many ways are there to select a sub-team of six members that includes members of
both sexes?
(6 marks)

(c) Bag A consists of 5 blue balls and 7 red balls. Bag B contains 3 blue balls and 12 red balls. A
fair coin is flipped. If the outcome is a tail, a ball is drawn from Bag A. Otherwise (i.e., the
outcome is a head), a ball is drawn from Bag B.
1. Suppose that this experiment is done and a blue ball is selected. What is the probability
that this ball is in fact taken from Bag B?
2. Suppose that the same experiment is done and a white ball is selected. What is the
probability that this ball is in fact taken from Bag B?
3. Suppose that the same experiment is done using a biased coin that comes up heads with
the probability of 0.4 and tails with the probability of 0.6. A red ball is selected. What is
the probability that this ball is in fact taken from Bag A?

(7 marks)

(d) Tom flips a fair coin until a tail first appears, and if the number of tosses equals m, then Tom
gets a payoff for 2m pounds. Calculate the expected value of his payoff.
(5 marks)

END OF MOCK EXAM PAPER

PAPER CODE: CPT107/22-23/S1 Page 6 of 6