Logic and proof

Supervision 1

1) Provide truth tables for the following formulæ

P Q P Q

¬P Q ¬R ¬Q

Q R ¬(P ¬Q (P R))

2) Verify de Morgan's laws.

3) Each of the following formulæ is satisfiable but not valid. Exhibit an interpretation that makes the formula true and another interpretation that makes the formula false.

P  Q

¬( P Q R)

¬( P Q) ¬( Q R) ( P R)

4) Convert each of the following propositional formulæ into Conjunctive Normal Form and also into Disjunctive Normal Form. For each formula, state whether it is valid, satisfiable, or unsatisfiable; justify each answer.

( P Q) ( Q P )

(( P Q) R) (¬(( P R) ( Q R)))

¬ P Q R   P Q R

5) Prove the following sequents:

¬¬ A A

A B B A

A B B A

6) Translate the following English sentences into FOL

Migratory birds can fly.

A train to Gatwick costs more than a train to Heathrow.

Some pupil in this course has the highest mark.

7) Consider the following formulæ: everybody loves somebody vs there is somebody that everybody loves:

(1) ∀x y loves(x , y )

(2) ∃ y x loves(x , y ) (2)

Does (1) imply (2)? Does (2) imply (1)? Consider both the informal meaning and

the formal semantics defined in your notes.

8) Let ≈ be a 2-place predicate symbol, which we write using infix

notation as x ≈ y instead of ≈ (x , y ). Consider the axioms

(1) ∀x x ≈ x

(2) ∀x y (x ≈ y y ≈ x )

(3) ∀x y z (x ≈ y y ≈ z x ≈ z )

Let the universe be the set of natural numbers, N = { 0, 1, 2, ...}. Which axioms

hold if I [ ≈] is

• the empty relation, ?

• the universal relation, {(x , y ) | x , y N }?

• the equality relation, {(x , x ) | x N }?

• the relation {(x , y ) | x , y N x + y is even}?

• the relation {(x , y ) | x , y N x + y = 100}?

----------

2004 Paper 5 Question 9: part c

For each of the following first order logic formulae: either prove it to be valid using the sequent calculus; or give an interpretation that makes it false.

[ x(y(R(x, y)))] x(R(x, x))

[ x(¬P (x))] ¬x(P (x))

[ ¬x(P (x))] x(¬P (x))

x(P (x) P (a) P (b))