ALGEBRA AND LOGIC

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.

1. Let W

1

and W

be wffs 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 wff 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

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

rules) to find 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)

3. 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 find 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)

4. 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)

5. 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 coefficients 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 field.)

(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

6. 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)