## Description

1. [1 marks Diwali offer: 2 marks] Formalise the following as sentences of first order logic. Use

B(x) for “x is a barber”, and S(x, y) for “x shaves y”.

(a) Every barber shaves all persons who do not shave themselves.

(b) No barber shaves any person who shaves himself.

Convert your answers to Skolem form and use ground resolution to show that (c), given below, is

a consequence of (a) and (b).

(c) There are no barbers.

2. [1.5 marks Diwali offer: 3 marks] Fix a signature σ. Consider a relation ∼ on σ-assignments

that satisfies the following two properties.

• If A ∼ B then for every atomic formula F we have A |= F iff B |= F.

• If A ∼ B then for each variable x we have (i) for each a ∈ UA there exists b ∈ UB such that

A[x7→a] ∼ B[x7→b]

, and (ii) for all b ∈ UB there exists a ∈ UA such that A[x7→a] ∼ B[x7→b]

.

Prove that if A ∼ B then for any formula F, A |= F iff B |= F. You may assume that F is built

from atomic formulas using the connectives ∧ and ¬, and the quantifier ∃.

3. [1 marks Diwali offer: 2 marks] Express the following by formulas of first-order logic, using

predicates H(x) for “x is happy”, R(x) for “x is rich”, G(x) for “x is a graduate”, and C(x, y) for “y

is a child of x”.

(a) Any person is happy if all their children are rich.

(b) All graduates are rich.

(c) Someone is a graduate if they are a child of a graduate.

(d) All graduates are happy.

Use first-order resolution to show that (d) is entailed by (a), (b), and (c). Indicate the substitutions

in each resolution step.

4. [1 marks Diwali offer: 2 marks] Let A(x1, . . . , xn) be a formula with no quantifiers and no

function symbols. Prove that ∀x1 . . . ∀xnA(x1, . . . , xn) is satisfiable if and only if it is satisfiable in an

interpretation with there being just one element in the universe.

5. In this question, we work with first-order logic without equality.

(a) [1 marks Diwali offer: 2 marks] Consider a signature σ containing only a binary relation

R. For each positive integer n show that there is a satisfiable σ-formula Fn such that every model

A of Fn has at least n elements.

(b) [1.5 marks Diwali offer: 3 marks] Consider a signature σ containing only unary predicate

symbols P1, . . . , Pk. Using the question 2 (above), or otherwise, show that any satisfiable σformula has a model where the universe has at most 2k

elements.