Question 1

(a)  Numbers and sets

(i) Compute 42  and 43  modulo 3 .  From these results, conjecture a property P(n) of 4n   modulo  3 .   Prove  by  induction that  P(n)  is satisfied for all  n  e N .

[3 marks]

(ii)  Let sqr t : {x e N | x > 0} → {y e R | y > 0} be the square root function

from non-negative integers to non-negative reals, i .e . sqr t(x) = y if and only if x = y2 .

Is sqr t injective? surjective? bijective? Justify your answers .           [3 marks]

(iii)  Let float  javaSqrt(int  x) be a Java implementation of this square root

function (assume it throws an exception if x is negative) .  Discuss the differ- ences between sqr t and javaSqrt when considered as mathematical functions between sets .                                                                                       [4 marks]

(b)  Linear algebra

Consider the three points

P1  =  (2(1)) (4l

P2  =  ( -0(1))

(   4 l

P3  =  ( -2(1))

(   2 l

(i)  Show that these form the corners of an equilateral triangle (i .e . a triangle where all sides have the same length) .                                                          [2 marks]

(ii) The triangle defines a plane M in R3 .  Give its parametric representation and

its normal form .                                                                                   [4 marks]

(iii) Another plane N is given by

( 0(1))        (1(1))        (0(2))

Find the line of intersection of M and N .

Show your working for each part .

[4 marks]

Question 2

(a)  Propositional Logic

Let F be the formula (A V B) → (B V A), and

let G be the formula A → (B → (-B V -A)) → -B .

(i)  Provide a constructive Sequent Calculus proof of F .

(ii)  Provide a constructive Natural Deduction proof of G .

(iii)  Is G satisfiable? Justify your answer .

[4 marks]

[6 marks]

[2 marks]