Consider the following well-formed formulae: Which of the above two are…

Correct equivalence: ¬∀x P(x) is equivalent to ∃x ¬P(x).

• Reason: Use quantifier negation (De Morgan for quantifiers). ¬∀x φ(x) ≡ ∃x ¬φ(x). Applying with φ(x)=P(x) gives the equivalence.

• Therefore the pair of formulas "not all x satisfy P" and "there exists an x such that not P(x)" express the same property.

Why the other pairs are not equivalent:

• ¬∃x P(x) is equivalent to ∀x ¬P(x), while ¬∃x ¬P(x) is equivalent to ∀x P(x). These two are generally different; e.g., with a single element domain and P(true), the first is false and the second is true.

• ¬∃x P(x) and ∃x ¬P(x) are not equivalent either. Example: domain {a,b} with P(a)=true, P(b)=false gives ¬∃x P(x) false but ∃x ¬P(x) true.

• Thus the only equivalent pair among the listed formulas is ¬∀x P(x) and ∃x ¬P(x).