Be accurate and show your working and explanation step by step

1. (a) Show each of the following [40]:

(i) P Q, Q R, P R P

(ii) A B (B A) (A B)

(iii) (A B) C, B C, (C A) (C A) A

(iv) (P Q) (P Q)

(v) (P Q) [[(P Q) (P Q)] (Q P)]

(b) Show each of the following [60]:

(i) y (Ryy Ga) x (Rxx) Ga

(ii) x [(Fx Fx) (Gx Gx)]

(iii) x (Fx y (Fy y = x)), Fa Fb a = b

(iv) xGx, x [Fx y (Fy y = x)], y (Gy Fy) xy (Gy x

= y)

2. Answer all parts of this question.

(a) Using the following symbolisation key:

domain: all living creatures

Bx: ____x is a bulldog

Hx: ____x is a human

Sx: ____x skateboards

Axy: ____x admires ____y

Bxy: ____x is better at skateboarding than ____y

i: Tillman

r: Rodney

Symbolise the following English sentences as best you can in FOL, commenting on any difficulties or limitations you encounter:

i. Rodney is a human and Tillman is a bulldog, and both can skateboard.

ii. Everybody admires Tillman, because he is a bulldog who can skateboard.

iii. Tillman is the skateboarding bulldog.

iv. There are skateboarding bulldogs besides Tillman.

v. Some human and some bulldog skateboard exactly as well as each other.

vi. Tillman is better at skateboarding than some humans, but he is not better than Rodney.

vii. When it comes to skateboarding, Tillman is the best bulldog.

viii. No bulldog skateboards better than Tillman does.

ix. Tillman admires all skateboarding bulldogs, whether or not they

are better at skateboarding than him.

x. Two humans who skateboard are better than Rodney at it.

(b) Show that each of the following claims is true [30]

i. x(Fx y(x = y Gy Rxy)), Fa, Fb, a = b xyz(x =

y x = z y = z)

ii. xyz(x = y y = z x = z (Rxy Ryx) (Rxy Rxz))

xy(Rxy Ryx)

iii. x(x = a x = b x = c), x((x = a x = b) Fx), x((x = b x =

c) Gx), Rab, Rba xyz(x = y x = z y = z)

iv. xyRyx, xyRxy, xyz((Rxy Ryz) Rxz) xyz((Rxy

Rxz) y = z)

(c) Explain why we insist that the domain of quantification for any interpretation in FOL must always contain at least one object.

3. (a) Define the following notions from set theory: Cartesian product, Empty set, Power set, Proper subset [10]

(b) Give examples of the following:

i. A set with exactly one subset.

ii. A set with exactly one proper subset.

iii. A set of which at least one member is also a subset.

iv. Two sets whose Cartesian product has exactly six members.

v. A set whose power set has the set containing the empty set as a member.

vi. A set whose intersection with its own powerset is not empty.

vii. A non-empty (and finite!) set whose members include all members of its own members.

viii. A set whose members are all sets.

(c) Define the following notions from the theory of relations: Ancestral, Converse, Equivalence relation, Equivalence class.

(d) Each of the following statements is false. In each case give a counterexample, being careful to specify the domain for each answer. [30]

i. Every relation is its own ancestral.

ii. Every relation is its own converse.

iii. Every reflexive symmetric relation is transitive.

iv. Every symmetric transitive relation is reflexive.

v. Every reflexive transitive relation is symmetric.