THE UNIVERSITY OF SUSSEX 5059

BA and BSc EXAMINATIONS 1997

INTRODUCTION TO LOGIC

Saturday 21 June, 1997 2.00 p.m. – 3.30 p.m.

Introduction to Logic 3 Questions

Candidates should answer TWO questions. The time allowed is ONE AND A HALF hours.

Q.1 a Draw up truth tables for each of the following statements of the Propositional Calculus and indicate their status (inconsistent or consistent):

1. ¬p → p

2. p ∧ ¬(q ∧ p)

3. p ∧ ¬(¬q → p)

4. (p ∧ q) ↔ (p ∨ r)

5. (p → (q ∨ r)) ∧ (p ∧ ¬(¬q → r))

[10 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

[10 marks]

c Formalize the following arguments as statements of the Propositional Calculus and determine whether or not they are sound.

1. Either x is negative or y is positive. If z is negative, then y is positive. Therefore, if x is positive or y is negative, then z is positive.

2. If Tweety is a migrant, then Tweety can fly. If Tweety can fly then Tweety

5059 Introduction to Logic

is not an Ostrich. So, if Tweety is an Ostrich, then Tweety is not a migrant. [15 marks] d Identify the premises and the conclusion in the following (sound) argument. Can

this argument be formalized appropriately as a statement of the Propositional Calculus? (Give reasons for your answer.)

If Fido is a dog, then Fido is a mammal. All mammals are warmbloodied. Therefore, if Fido is not warm-bloodied, then Fido is not a dog.

[5 marks]

e Explain why the method of truth tables cannot generally be used to determine

whether a sentence of the First Order Predicate Calculus is tautologous. [10 marks]

Q.2 a Use the method of semantic tableaux to determine the status (consistent or inconsistent) of the following sets of sentences:

1. {p ∧ q, ¬p, q}

2. {p ∨ q, ¬p, ¬q}

3. {p → r, q → r, (p ∧ q) → r}

4. {(p ∨ q) → q, p ∨ (r → q), p, q}

[10 marks]

b Display the following derivation rules of the system of natural deduction. Using the method of semantic tableaux, demonstrate that they are sound:

1. ∧ – introduction

2. → – elimination

3. ∨ – elimination

[10 marks]

c Let ∘ be a logical connective such that for any pair of statements A and B, the statement (A ∘ B) is logically equivalent to ¬(B → A). Display the truth table for the connective ∘ and devise suitable tableaux derivation rules for sentences of the form (A ∘ B) and ¬(A ∘ B).

[10 marks]

d What does it mean to say that a system of formal logic is

1. sound

2. complete

[10 marks]

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

if G ∪ {A} ⊧ B then G ⊧ (A → B)

[10 marks] Q.3 a Express the following English sentences as formulas of the First Order Predicate

Calculus, providing informal interpretations for any symbols that your introduce.

1. If x > y and y > z, then x > z

2. Every natural number is less than its successor.

3. There is a prime number that is even.

4. Every natural number is the sum of two natural numbers

5. There is no number that is larger than all other numbers

[10 marks]

b Explain how the method of semantic tableaux for the Propositional Calculus is

extended to the case of the First Order Predicate Calculus.

[10 marks]

c Let a and b be constants and f, m, s and t function symbols with the interpretation:

I(a) is Ann I(b) is Bob
I(f) is father I(m) is mother I(s) is sister I(t) is brother

Express the following concepts as first order terms:

1. Ann’s sister

2. Bob’s paternal grandmother

3. The father of Ann’s mother’s sister.

4. The brother of the mother of Bob’s paternal grandfather.

[5 marks]

d Let a, b, c and d be individual constants and M, W, L and H predicate symbols with the interpretation:

I(a) is Ann I(b) is Bob  I(c) is Cath I(d) is Dave
I(M) is man I(W) is woman I(L) is likes I(H) is hates

Assuming the domain of all people, provide paraphrases in English for the following formulas:

1. ∀x.H(x, b) → ¬L(b, x)

2. ∀x.L(x, d) → (L(x, c) ∨ H(x, b))

3. ∀x.∃y.M(x) → (W (y) ∧ L(x, y))

4. ∃x.W (x) ∧ ¬(H(x, d) ∨ L(x, d))

5. ¬∃x.∃y.W (x) ∧ W (y) ∧ H(x, y) ∧ L(y, x)

[10 marks]

e For each of the following formulas of the First Order Predicate Calculus, specify (a) an interpretation which makes the formula true, and (b) an interpretation which makes the formula false.

1. ∀x.∀y.A(x, y) ∨ ¬A(y, x)

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

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

[15 marks]