THE UNIVERSITY OF SUSSEX 5059

BA and BSc EXAMINATIONS 1999

INTRODUCTION TO LOGIC

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 (i.e. tautologous, contingent or inconsistent).

1. p → ¬p

2. ¬p ∧ (q → ¬p)

3. (p ∧ q) ↔ ¬(p ∨ q)

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

[4 marks]

b Using the formal laws of logical equivalence, demonstrate the following equivalences:

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

2. ¬(p → ¬p) ∧ (¬p → p) ≡ ⊥

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

[4 marks]

c What does it mean to say that the connectives of the Propositional Calculus are

truth functional?

[4 marks]

d Identify the premises and conclusion of the following argument. Using any appropriate method, determine whether or not the argument is sound.

The solution in the test-tube is either acid or alkaline. If the litmus paper has turned red, then the it is clearly acid. However, the litmus paper has not turned red so the solution is clearly alkaline.

5059 Introduction to Logic

[4 marks] e Explain what it means to say that a formal system of logic is decidable. Assuming

that the axiomatic system of Propositional Logic is both sound and complete, sketch an argument to show that it is decidable.

[4 marks]

Q.2 a Use the method of semantic tableaux to determine whether or not the following statements of semantic entailment hold:

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

2. {p ∧ q} ⊧ ¬(p → ¬q)

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

[4 marks]

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

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

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

[4 marks]

c Display the following derivation rules of the system of natural deduction. Using any appropriate method, demonstrate that they are sound:

1. ∧ –introduction

2. ∨ – introduction

3. → – elimination

[4 marks]

d Using the method of natural deduction, present proofs that the following statements are theorems

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

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

3. ((¬p → q) ∧ ¬q) → p

[4 marks]

e Justify the following proposition concerning the semantic entailment relation, where A and B are aribitrary statements.

if G ⊧ (A ∧ ¬A), then G ⊧ B

[4 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. Every integer is either even or odd.

2. No integer is both even and odd.

3. The sum of two odd integers is an even integer.

4. Every integer is smaller than some other integer.

5. Negative integers are smaller positive integers.

[4 marks]

b With reference to the First Order Predicate Calculus, explain what is meant by the following.

1. a theory

2. an interpretation

3. a model

[4 marks]

c Consider the following argument:

All cats like milk. Felix is a cat. Therefore, Felix likes milk. Now do the following:

1. Explain why the language of Propositional Logic is not appropriate as a means of representing this argument.

2. Identify the premises and the conclusion of the argument and formalize them as statements of the First Order Predicate Calculus.

3. Using the method of semantic tableaux, show that the argument is sound.

[8 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} = {¬A(a, x), B(x, a)}
C_{2} = {¬B(b, y), C(y)}

[4 marks]