Notes:

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

. Partial marks maybe 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 + ⋯ + 2x ) =  2x+2   − 2.

(2 marks)

Question 2: Set Theory             [11 marks]

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

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

(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 X = {a, b, c, d, e, f}  and let S be a relation on X such that:

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

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

S = {(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 Sis 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)

Question 4: Functions             [19 marks]

(a) Let f: ℝ → ℝ   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 f: ℤ → ℤ   such that ∀x ∈  ℤ f(f(x)) = x. Prove or disprove that  f  isa 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 f: A → B  and  g: B → C  be two bijective functions.

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

2.    Consider the equality:  (g ∘ f) ∘ (f−1   ∘ g−1 )  =  (f−1   ∘ g−1 )   ∘   (g ∘ f). 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:

1.    ¬((¬x ∧  ¬y ) ∨  (¬x  ∧ y)) = x

2.    ¬x ∨ (y ∧ z) =  x  → (y → z) (4  marks)

(b) Without  using  any  truth  table,  show  that   ~(p  ∧ (Q ∨ R)) ∨ ((p  ∧ Q) ∨ (p ∧ R))  is   a tautology. (4 marks)

(c) LetH be the set of all people. For a,b ∈  H, the predicate Likes(a,b) means person alikes 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?

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 ahead), 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)