Which one of the following predicate formulae is NOT logically valid ? Note…
2020
Which one of the following predicate formulae is NOT logically valid ?
Note that \(W\) is a predicate formula without any free occurrence of \(x\).
- A.
\(\forall x (p(x) \vee W) \equiv \forall x \: ( px) \vee W\) - B.
\(\exists x(p(x) \wedge W) \equiv \exists x \: p(x) \wedge W\) - C.
\(\forall x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W\) - D.
\(\exists x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W\)
Attempted by 94 students.
Show answer & explanation
Correct answer: C
Answer: The formula ∀x(p(x) → W) ≠ ∀x p(x) → W is not logically valid.
Reason (algebraic):
Rewrite p(x) → W as ¬p(x) ⋁ W. Then ∀x(p(x) → W) is ∀x(¬p(x) ⋁ W), which (since W has no free x) is equivalent to (∀x ¬p(x)) ⋁ W.
But ∀x p(x) → W is equivalent to ¬∀x p(x) ⋁ W, i.e. (∃x ¬p(x)) ⋁ W.
Since (∀x ¬p(x)) and (∃x ¬p(x)) are not equivalent generally, the two sides above are not logically equivalent.
Concrete counterexample:
Take a domain with at least two elements, let W be false, let p hold of one element and fail for another.
Then for the left formula ∀x(p(x) → W) we get ∀x ¬p(x) (because W is false), which is false because p holds for some element.
For the right formula ∀x p(x) → W we get ¬∀x p(x) (since W is false), which is true because not every element satisfies p. Thus left is false and right is true, proving the inequivalence.
Brief notes on the other formulae:
∀x(p(x) ∨ W) is equivalent to (∀x p(x)) ∨ W because W is x-free, so the distribution holds.
∃x(p(x) ∧ W) is equivalent to (∃x p(x)) ∧ W because W does not depend on x.
∃x(p(x) → W) is equivalent to (∃x ¬p(x)) ∡ W, which equals ∀x p(x) → W; hence that equivalence holds.