# ALGEBRA AND LOGIC

This assignment comprises a total of 60 marks and is worth 15% of the overall ## WE WRITE PAPERS FOR STUDENTS 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 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

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

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

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

1. 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}

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

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

SOURCE: WWW.ROYALRESEARCHERS.COM
Havent found the Essay You Want?
We Can Help
The Essay is Written From Scratch for You

ORDER AN ESSAY WRITTEN FROM SCRATCH at : https://royalresearchers.com/ 