1. (13 points) Consider the blocks world domain (NBW), and suppose the vocabulary of the domain, LNBW includes the following symbols:

Predicate Symbols:

• above(x,y) iff x is above y, either directly or indirectly.

• under(y,x) iff ((x is the unique block immediately above block y) or (x is not above any blocks and y = x)).

• clear(x) iff no blocks are above x.

• ontable(x) iff x is not above any blocks.

Let Φ be a set containing the following sentences:

• ∀x(¬above(x,x))

• ∀x∀y∀z((above(x,y) ∧above(x,z) ∧¬(y = z)) → (above(z,y) ∨above(y,z)))

• ∀x∀y∀z((above(x,y) ∧above(y,z)) → above(x,z))

(a) (5 points) Construct a model of Φ with size three (i.e., that includes 3 blocks) which does not satisfy the English description of under.

(b) (8 points) Modify Φ, without modifying the vocabulary, so that the models of the resulting set of sentences would be those structures that satisfy the English definition of under, clear and ontable.

2. (10 points) A tautology is a formula that is true in every possible structure. The sentence (∀x)(P(x) ∨¬P(x)) is an example of a tautology.

Determine whether or not the following sentence is a tautology. Justify your answer.

∀x h∀y P1(x,y) → (P2(y) ∨P3(y))   →  ∀y(P1(x,y) → P2(y))  ∨ ∀y(P1(x,y) → P3(y))  i

3. (17 points) Consider the following vocabulary:      Murder(x,y,z, u): x murdered y at place z at time u At(x,y,z): x was at place y at time z

O(x): x had an opportunity

M(x): x had a motive.

Constant Symbols: M stands for Mr M.; P for Mrs P.; L for library; and T for 12 p.m.

(a)  (7 points)

Translate the sentences below to first-order logic using the above-mentioned vocabulary.

• Somebody murdered Mr M. in the library at 12 p.m., and there is exactly one person who is the murderer of Mr M.

• Anybody who was in the library at 12 p.m. had an opportunity to murder Mr M.

• Mrs P. was in the library at 12 p.m.

• More than one person had a motive to murder Mr M.

• A person is a murderer of Mr M. if only if they had a motive to murder Mr M. and an opportunity to do so.

(b)  (10 points)

Do the sentences from part (a) logically entail that Mrs P. murdered Mr M.? Formally justify your answer.

4. NOTE: This question is for exercise purposes only and will NOT be marked.

Do NOT include your solution to this exercise in your submission.

Given predicates P, Q,R and variables x,y,z; convert the following sentences to clausal form: (Recall that the 8 steps are: eliminate implication, move negation inward, standardize variables, skolemize, convert to prenex, distribute ∧ over ∨, flatten conjunctions and disjunctions, convert to clauses.) Clearly indicate any Skolem functions or constants used in the conversion. Note each formula

might give rise to more than one clause so number each clause generated.

(a) ∀x.R(x) → ∃y.P(x,y)

(b) ∃x, ∀y.(Q(x,y) ∧Q(y,x)) ∨¬R(y)

(c) ∀x, ∀w. ¬P(w,x) → ∃z.(R(z) ∧Q(x,z))

(d) ∃y.R(y) ∧∀x.Q(y,x)