This  assignment  comprises 60 marks  and is  worth 20% of the  overall assessment. It  should  be  completed  and  uploaded  into  Canvas  before  midnight  on  Friday  19 May 2023.  Acknowledge  any sources  or assistance .   This  must  be  your own work. Breaches  of academic  integrity,  including  copying  solutions,  sharing  answers  and attempts at contract cheating,  attract severe penalties .

1.  Use the rules of deduction in the Predicate Calculus to find a formal proof for the following sequent (without invoking sequent or theorem introduction):

(3北) ╱G(北)  ÷  ╱H(北) A K(北)、、,  (A北) ~ K(北)    上    (3北) ~ G(北)                (5 marks)

2.  (a) Find the error in the following argument. Explain briefly.

1         (1)      ╱(3北)G(北)、A ╱(Ay)H(y)、    A

1         (2)      (3北)G(北)                              1 A E

3         (3)      G(a)                                      A

1         (4)      (Ay)H(y)                              1 A E

1         (5)      H(a)                                     4 A E

1, 3     (6)      G(a)A H(a)                         3, 5 A I

1         (7)      G(a)A H(a)                         2, 3, 6 3 E

1         (8)      (A北) ╱G(北) A H(北)、              7 A I

(b) Find a model to demonstrate that the following sequent cannot be proved using the Predicate Calculus:

╱(3北)G(北)、A ╱(Ay)H(y)、    上    (A北) ╱G(北) A H(北)、

Explain briefly.

(c)  Prove the following sequent using rules of deduction from the Predicate Calculus (without invoking sequent or theorem introduction):

(A北) ╱G(北) A H(北)、    上    ╱(3北)G(北)、A ╱(Ay)H(y)、

3.  Consider the following well-formed formulae:

W1   =  (Vx)╱E(x, x) A ╱ G(x) v H(x)、、,  W2   =  (ax) ╱G(x) A H(x)、,

W3   =  (ax)(ay)╱ ~ G(x) A ~ G(y) A  ~ E(x, y)、,

W4   =  (ax)(ay)╱ ~ H(x) A ~ H(y) A  ~ E(x, y)、

Prove that any model in which W1 , W2 , W3  and W4  are all true must have at least 5 elements. Find one such model with 5 elements. (8 marks)

4.  Recall the division ring of quaternions

H = {a + bi + cj + dk I a, b, c, d, e R}

Put β = 2 + i - j + k . Find γ, δ e H such that

βγ  =  δβ  =  3j - 4k .

Verify any claims.

[Hint: you may use without proof the fact that if α = a + bi + cj + dk e H and α = a - bi - cj - dk . then

αα  =  a2 + b2 + c2 + d2  .] (6 marks)

5.  Let R  =  {0, 1, x, x + 1, x2 , x2 + 1, x2 + x, x2 + x + 1} be the subset of Z2 [x] consisting of all polynomials of degree at most  2,  with usual addition and multiplication of polynomials followed by taking the remainder after dividing by x3 + x2 + 1.  Then R is a commutative ring with identity (and you do not need to verify this).

(a)  Construct the multiplication table for nonzero elements of R, and explain briefly why R is a field. (To get full credit for this part, it is not necessary to show any calculations.)

(b)  Solve the following equation over R for α where

α3 + x2 α + x2 + 1  =  0 .

[Hint: α = 1 is a solution.] (8 marks)