Computer Science 260

Assignment 3

1. Consider the following expression

∀xP(x) ∧ Q(x) ↔ (∃xR(x) → ∀x((S(x) ∧ Y (y)) ∨ ∃y(U(y) ∨ ∼ T(x))))

(a) For each occurrence of each variable, indicate whether the variable is free or bound.

If the variable is bound, indicate whether it is bound to a ∀ or to a ∃.

(b) Rename the variables so that distinct names are used for each distinct variable.

2. Show formally that ∼ ∃y(∀x∃zP(x, y, z) ∨ ∃x∀zQ(x, y, z)) is logically equivalent to

∀y(∃x∀z ∼P(x, y, z) ∧ ∀x∃z ∼Q(x, y, z)).

State the reason for each step.

3. Find an interpretation to show that the following argument form is not valid.

(∀x(P(x) → Q(x)) ∧ (∀x(P(x) → R(x)))) → ∀x((Q(x) → R(x))).