THE UNIVERSITY OF SUSSEX 5059

BA and BSc EXAMINATIONS 1998

INTRODUCTION TO LOGIC

Friday 26 June 9.30 - 11.00 am

Introduction to Logic 3 Questions

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

1. (a) Construct truth tables for each of the following statements of the Propositional Calculus and indicate their status (i.e. contingent, tautologous or inconsistent):

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

[10 marks]

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

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

[10 marks]

(c) Formalize the following argument as a single statement of the Propositional Calculus and determine whether or not it is sound.

Either the Earth is not round or the Moon is made of cheese. If the Moon is made of cheese, then the mice are happy. It follows that if the mice are not happy, then the Earth is round.

5059 Introduction to Logic

[10 marks] (d) Show that the truth functions for the logical connectives ¬, ∧ and ∨ can be

synthesized using just the connective → and the ‘inconsistent proposition’ ⊥. [10 marks]

(e) Justify the following law of semantic entailment, where G is a set of statements and A a statement:

if G ⊧ A, then G ∪ {¬A} is inconsistent

[10 marks]

2. (a) Using the method of semantic tableaux, determine whether or not the following statements of semantic entailment hold:

i. {p → q, ¬q} ⊧ ¬p ii. {p → r, q → r} ⊧ (¬r → ¬p) iii. {p → (q ∧ r), (p ∧ (¬q ∨ ¬r))} ⊧ (p ∧ ¬p)

[10 marks]

(b) 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]

(c) Explain how the method of semantic tableau for the Propositional Calculus is

extended to the case of the First Order Predicate Calculus.

[10 marks]

(d) Use the method of natural deduction to construct proofs for the following:

i. ⊢ (p ∧ q) → q ii. ⊢ (p → r) → ((p ∧ q) → r)) iii. ⊢ ((p → r) ∧ (q → r)) → ((p ∨ q) → r)

[10 marks]

(e) Explain what it means to say that a system of formal logic is:

i. sound ii. complete iii. decidable

[10 marks] 3. (a) Give an example of a simple argument (in English) that cannot be adequately

represented using the Propositional Calculus. Explain which aspects of your argument are problematic in this respect.

[10 marks]

(b) Express the following English sentences as formulas of the First Order Predicate Calculus, providing informal interpretations for any symbols (i.e. predicate symbols, individual constants) that your introduce.

i. If Micky is a mouse, then Micky is small. ii. Mice are smaller than elephants. iii. All elephants are grey and have trunks. iv. There is something that is grey that is not an elephant. v. There is a mouse that frightens every elephant.

[10 marks]

(c) Consider the following statements of the Predicate Calculus, where t is an individual constant with the interpretation “Tweety” and B, F, P and S are predicate symbols with the interpretations “is a bird”, “can fly”, “is a penguin” and “can swim”, respectively.

i. B(t) ∧ ¬F (t) ii. ∀x.(B(x) ∧ ¬P (x)) → F (x) iii. ∀x.P (x) → S(x) iv. ∃x.¬S(x) ∧ ¬F (x) Provide paraphrases, in English, for each of the statements given above. Now say whether the statements given below follow from those above. (Try to justify your answers.)

i. S(t) ii. ∃x.¬B(x) iii. ∀x.(B(x) ∧ ¬S(x)) → F (x)

[10 marks]

(d) For each of the following statements of the First Order Predicate Calculus, find

a satisfying interpretation.

i. ∀x.∀y.A(x, y) ∧ ¬A(y, x) ii. ∀y.∃x.B(x, y) iii. ∀x.∀y.∀z.(C(x, y) ∧ C(x, z)) → C(y, z)

[10 marks]

(e) What is meant by the following:

i. A first-order theory. ii. A model of a first-order theory.

[10 marks]