THE UNIVERSITY OF SUSSEX 5059

BA and BSc EXAMINATIONS 2000

INTRODUCTION TO LOGIC

June, 2000 –

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.

Q.1 a Draw up truth tables for each of the following statements of propositional logic and indicate their status (i.e. inconsistent, contingent or tautologous):

1. p → ¬p

2. p ∧ ¬(p ∨ q)

3. p ∧ (p → ¬q)

4. ¬(p ∧ q) ↔ (p → ¬q)

5. (p → (q → r)) → ((p → q) → r)

[4 marks]

b Use the method of truth tables to determine which of the following pairs of statements are logical equivalences:

1. (p ∧ q) and ¬(p → ¬q)

2. ¬(p ∧ q) and p → q

3. p → (q → r) and (p ∧ q) → r

[4 marks]

c Formalise the following argument as a single statement of propositional logic and determine whether or not it is sound:

If Spock is a Vulcan, then Spock is logical. If Spock is logical, then Kirk is nervous. So, either Spock is not a Vulcan or else Kirk is nervous.

5059 Introduction to Logic

[4 marks] d Let ↓ be a logical connective such that for any sentences A and B, (A ↓ B)

is equivalent to ¬(A ∧ B). Show that the following statements can be expressed using ↓ as the sole connective:

1. ¬A

2. (A → B)

3. (A ∨ B)

[4 marks]

e Construct an example, in English, of a simple argument that cannot be ade-

quately formalized using propositional logic.

[4 marks]

Q.2 a Use the method of semantic tableaux to determine whether the following sets of statements of propositional logic are consistent or inconsistent:

1. {p, (p → q), ¬q}

2. {(p ∨ q), (¬q → r), (p → ¬r)}

3. {(¬p ∨ q), (q → r), (p → (q → r)}

[4 marks]

b Use the method of semantic tableaux to determine whether the the following statements of semantic entailment hold:

1. {(¬p ∨ q), ¬q} ⊧ ¬p

2. {(p ∨ q) → p, q} ⊧ p

[4 marks]

c Consider the following putative rule of inference:

For any statements of propositional logic A, B and C, given A → B and B → C as premises, obtain A → C as a direct consequence.

Show that this rule is sound.

[4 marks]

d Use the method of natural deduction to show that the following statements are theorems:

1. (p ∧ q) → (p ∨ q)

2. p → (q → (p ∧ q))

[4 marks]

e Sketch an argument to show that the relation of semantic entailment (symbolized as ⊧) satisfies the following rule (where G is a set of statements and A and B are arbitrary statements):

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

[4 marks] Q.3 a Provide paraphrases in English for the following sentences of the predicate

calculus, assuming that d and m are individual constants “Dumbo” and “Micky”, E, F and M are one-place predicate symbols “is an elephant”, “is flying” and “is a mouse”, and S is a two-place predicate symbol such that S(x, y) means “x is smaller than y”.

1. E(d) ∨ ¬E(m)

2. ∃x.(E(x) ∧ F (x))

3. ∀x.(M(x) → S(x, d))

4. ∀x.(M(x) ∧ ∃y.(E(y) → S(x, y)))

[4 marks]

b Express the following English sentences in the predicate calculus. (You may wish to make use of the individual constants and predicate symbols introduced in part a above.)

1. Dumbo is a flying elephant

2. Micky is smaller than any elephant

3. No elephant is smaller than a mouse.

[4 marks]

c Assuming the domain of natural numbers, for each of the following formulas of the predicate calculus, find a satisfying interpretation.

1. ∀x.A(x, x)

2. ∀x.∃y.B(x, y)

3. ∀x.∀y.∀z.(C(x, y) ∧ C(y, z)) → C(x, z)

[4 marks]

d In general, can the method of truth tables be used to determine whether a sentence of the first order predicate calculus is a tautology? (Give reasons for your answer).

[4 marks]

e Explain how the method of semantic tableau for propositional logic is adapted

to the predicate calculus.

[4 marks]