THE UNIVERSITY OF SUSSEX 5059

BA and BSc EXAMINATIONS 2001

INTRODUCTION TO LOGIC

June, 2001 –

Introduction to Logic 3 Questions

Candidates should answer TWO questions. The time allowed is ONE AND A HALF hours. Each question is worth 20 marks.

1. (a) For each of the following statements of the Propositional Calculus, use the method of truth tables to determine whether it is contingent, tautologous or inconsistent:

i. p → ¬p ii. (p ∨ q) → q iii. (p ∨ ¬q) ↔ (q → p) iv. r → ¬((p ∧ q) ∨ r)

[4 marks]

(b) Using the Propositional Calculus, provide a formal representation of the following argument. Using the method of truth tables, determine whether or not the argument is sound.

Either the solution is acid or it is alkaline. If the solution is acid, then the litmus paper will be red. It follows that if the litmus paper is not red, then the solution is alkaline.

[4 marks]

(c) Using the formal laws of logical equivalence, simplify the following statements of the Propositional Calculus as far as possible:

i. p → (p ∧ q) ii. (p → q) ∧ (p → ¬q) iii. ((p → r) → ((r ∧ p) ∧ q))

5059 Introduction to Logic

[4 marks] (d) Justify the following proposition about the semantic entailment relation

(where G is a set of statements and A and B are statements).

if G ⊧ A and G ∪ {A} ⊧ B, then G ⊧ B

[4 marks]

(e) What does it mean to say that a system of formal logic is; i. sound ii. complete iii. decidable

[4 marks]

2. (a) Use the method of semantic tableaux to determine whether the following sets of sentences are consistent or inconsistent: i. {(p → q), ¬q, (r ∧ ¬p)} ii. {(p ↔ (q ∨ r)), (¬p ∨ ¬q)} iii. {((p ∨ q) ∧ (p ∨ ¬q)), ¬p}

[4 marks]

(b) Let ∘ be a logical operator with the following truth function:

(∘ t f) / (t t t)
f f t

Devise suitable tableaux derivation rules for sentences of the form (A ∘ B) and ¬(A ∘ B)

[4 marks]

(c) Using the method of natural deduction, show that the following statements are theorems i. (p ∧ q) → (q ∧ p) ii. ((p → q) ∧ p) → q iii. ((¬p → q) ∧ ¬q) → p

[4 marks]

(d) Present an argument to show that the natural deduction proof rule of

reductio ad absurdum (proof by contradiction) is sound.

[4 marks]

(e) With reference to the First Order Predicate Calculus, explain what is meant by the following terms: i. a first order theory ii. an interpretation iii. a model 3. (a) Is the language of the Propositional Calculus appropriate as a means of

representing the following argument? Give reasons for your answer.

All men are mortal. Socrates is a man. So, Socrates is mortal.

[4 marks]

(b) Express the following English sentences as statements of the First Order Predicate Calculus, providing informal interpretations for any symbols that you introduce. i. Every integer is either even or odd. ii. No integer is both even and odd. iii. The sum of two odd integers is an even integer. iv. Every integer is smaller than some other integer. v. Negative integers are smaller than positive integers.

[4 marks]

(c) Explain why the method of truth tables cannot generally be used to determine the status (i.e. contingent, tautologous, inconsistent) of statements of the First Order Predicate Calculus.

[4 marks]

(d) Let C_{1} and C_{2} be two clauses, as shown below. Show that C_{1} and C_{2} resolve and display their resolvent.

C_{1} = {¬P (a, x), ¬Q(x, a)}
C_{2} = {Q(b, y), R(y)}

[4 marks]

(e) In resolution theorem proving what, is meant by i. a literal ii. a definite clause iii. a goal clause

[4 marks]