Notes:

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

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

Question 1: Proof Techniques                                                                                       [10 marks]

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

and b ≠ 0, then a2  - b√3   + c is irrational. (4 marks)

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

(c) For all integers n  ≥ 2, use proof by induction to show that:

2 j2(1)  − 1  =  − (2n(1+)n) (3 marks)

Question 2: Set Theory                                                                                                 [10 marks]

(a) Let X, Y and Z be non-empty sets, prove or disprove that X – (Z  ∩   Y) =  (X – Z)  ∩ (x   –   Y). (2 marks)

(b) Let X and Y be non-empty sets. Prove or disprove X  ∪  (Y – X) = Y if and only if X  ⊆   Y. (5 marks)

(c) There exist three non-empty sets X, Y and Z such that X ∈ Y, X ⊈ Z, and Y  ⊆  Z. If you think that it is true, give an example. If not, disprove it. (3 marks)

Question 3: Relations    [20 marks]

Question 4: Functions and PHP           [17 marks] 

(a)  Consider the function  f: [0, +∞) → [3, +∞)   defined by  f(x) = 2x + 3

1. Prove that f is injective.     (3 marks)

2. Prove that f is surjective.    (3 marks)

3. Find the inverse off.     (3 marks)

(b) Let f,g: R → R where  f(x) = ax + b and g(x) = cx + d for all x e R, with a, b, c, d real constants.

What relationship(s) must be satisfied by a, b, c, d if  (f。g)(x) = (g。f)(x) for all x e R? (5 marks)

(c) Avillage has 400 inhabitants. Show that at least two of them have the same birthday, and that at least 34 are born in the same month of the year. (3 marks)

(b) 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.    (p Λ q) → r 三 ¬ p v (q → r)                                         (3 marks)

2.    (p Λ q) → (¬ r v ¬ s) 三 (r Λ s) → (¬ p v ¬ q)                         (3 marks)

(c) Let the domain contain the set of all students and courses. Define the following predicates:

C(x): x is a course.

S(x): x is a student.

T (x, y): student x has taken course y.

Translate the following sentences into S-formulae, that is, for each of the following sentences provide an S-formula that expresses the sentences:

1.   Every student has taken some course.

2.   Some student has not taken any course.

3.   A student has taken a course.

4.  No student has taken every course.

5.   Every student has taken every course.

6.   A student has taken at least 2 courses. (12 marks)

1.   All children are of the same sex.                        (2 marks)

2.   The 3 eldest are boys, and the other girls.     (2 marks)

3.   There is at least 1 girl.           (2 marks)