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))).
