Project ForgeWhich one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
(A) ∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W (B) ∃x(p(x) ∧ W) ≡ ∃x p(x) ∧ W (C) ∀x(p(x) → W) ≡ ∀x p(x) → W (D) ∃x(p(x) → W) ≡ ∀x p(x) → W
- A∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W
- B∃x(p(x) ∧ W) ≡ ∃x p(x) ∧ W
- ∀x(p(x) → W) ≡ ∀x p(x) → W
- D∃x(p(x) → W) ≡ ∀x p(x) → W
Explanation
Since W has no free x, quantifiers distribute cleanly over ∨ and ∧ (options A, B, D are standard valid identities — D in particular follows from ∃x(p(x)→W) ≡ ∃x(¬p(x)∨W) ≡ (∀x¬p(x))∨W ≡ ¬(∀x p(x))∨W ≡ ∀x p(x)→W). But for →, the antecedent-side quantifier FLIPS: ∀x(p(x)→W) ≡ ∀x(¬p(x)∨W) ≡ (∀x¬p(x))∨W ≡ ¬(∃x p(x))∨W ≡ (∃x p(x))→W — an EXISTENTIAL on the right, not the universal claimed in option C. So ∀x(p(x)→W) is equivalent to (∃x p(x))→W, not (∀x p(x))→W in general — option C is the one that is NOT logically valid.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.