This assignment comprises a total of 60 marks and is worth 15% of the overall

assessment. It should be completed, accompanied by a signed cover sheet, and a

hardcopy handed in at the lecture on Wednesday 25 May. Acknowledge any sources

or assistance. An electronic copy or scan should also be downloaded using Turnitin

from the Blackboard portal.

- Let W

1

and W

be wﬀs such that the following sequent can be proved using

the 10 rules of deduction in the Propositional Calculus:

2

W

1

⊢ W

2

.

Let W be another wﬀ in the Propositional Calculus. Use Sequent Introduction

to prove the following sequents:

(a) ~ W

2

⊢ ~ W

1

(b) W ∨ W

1

⊢ W ∨ W

Decide which of the following sequents can be proved, providing a proof or

counterexample in each case:

(c) W

2

⇒ W ⊢ W

1

⇒ W (d) W

1

⇒ W ⊢ W

- Use the rules of deduction in the Predicate Calculus (but avoiding derived

rules) to ﬁnd formal proofs for the following sequents:

(a) (∃x) F(x) ⊢ ~ (∀x) ~ F(x)

(b) ~ (∀x) ~ F(x) ⊢ (∃x) F(x)

(c) (∀x)

~ F(x) ⇒ G(x)

_

⊢

(∃x) ~ G(x)

(d) (∃z)(∃y)(∀x) K(x, y, z) ⊢ (∀x)(∃y)(∃z) K(x, y, z)

(e) (∃x)

_

G(x) ∧ (∀y)

F(y) ⇒ H(y, x)

,

(∀x)

_

G(x) ⇒ (∀y)

L(y) ⇒~ H(y, x)

_

_

_

_

_

⇒

(∃y)F(y)

_

2

2

⇒ W

(9 marks)

⊢ (∀x)

F(x) ⇒~ L(x)

_

(20 marks)

- Find faults in the following arguments, with brief explanations:

(a) First faulty argument:

1 (1) (∀x)

F(x) ⇒ G(x)

_

A

2 (2) (∃x) F(x) A

3 (3) F(a) A

1 (4) F(a) ⇒ G(a) 1 ∀ E

1, 3 (5) G(a) 3, 4 MP

1, 3 (6) (∀x) G(x) 5 ∀ I

1, 2 (7) (∀x) G(x) 2, 3, 6 ∃ E

(b) Second faulty argument:

1 (1) (∀x)(∃y) H(x, y) A

1 (2) (∃y) H(a, y) 1 ∀ E

1 (3) (∃y) H(b, y) 1 ∀ E

4 (4) H(a, b) A

5 (5) H(b, a) A

4, 5 (6) H(a, b) ∧ H(b, a) 4, 5 ∧ I

4, 5 (7) (∃y)

H(a, y) ∧ H(y, a)

4, 5 (8) (∃x)(∃y)

H(x, y) ∧ H(y, x)

1, 4 (9) (∃x)(∃y)

H(x, y) ∧ H(y, x)

1 (10) (∃x)(∃y)

H(x, y) ∧ H(y, x)

_

6 ∃ I

_

7 ∃ I

_

3, 5, 8 ∃ E

_

2, 4, 9 ∃ E

Now ﬁnd models to demonstrate that the following sequents are not valid, with

brief explanations:

(c) (∀x)

F(x) ⇒ G(x)

_

, (∃x) F(x) ⊢ (∀x) G(x)

(d) (∀x)(∃y) H(x, y) ⊢ (∃x)(∃y)

H(x, y) ∧ H(y, x)

- Solve the following equations simultaneously over Z

7

_

and explain why no solution

exists in Z

11

:

5x + 2y = 4

3x – y = 3

(9 marks)

(4 marks)

- In this exercise we work with polynomials over Z

3

. Consider the ring

R = {0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2}

of remainders with addition and multiplication modulo the quadratic

p(x) = x

where all coeﬃcients come from Z

2

+ 2x + 2 = x

3

2

– x – 1 ,

.

(a) Verify that p(x) has no linear factors, so is irreducible. (Hence R is a ﬁeld.)

(b) Calculate in R the following powers of x:

x

2

, x

3

, x

(c) Explain why x is primitive in R, but x

4

, x

5

, x

2

6

, x

is not primitive.

(d) Find both square roots of 2 in R.

(e) Solve over R the following quadratic equation in a:

a

2

- Suppose that a, b, c ∈ R with a 6 = 0 and b

– 2xa + x – 1 = 0 .

r(x) = ax

2

is an irreducible quadratic polynomial. Prove that

2

7

, x

8

.

– 4ac < 0, so that

+ bx + c

R[x]/r(x)R[x]

~

=

C .

[Hint: use the Fundamental Homomorphism Theorem. You may assume without

proof that an appropriate evaluation map is a ring homomorphism.]

(9 marks)

(9 marks)