Exercise · ZW-ORDER-OF-QUANTIFIERS-004 · ★☆☆ Basic
Which pair is not equivalent in general?
Choose one option.
Show answer
- C. ∀x∃y P(x,y) and ∃y∀x P(x,y)
Explanation
Swapping quantifiers can change the truth value, so \(\forall x\,\exists y\,P(x,y)\) and \(\exists y\,\forall x\,P(x,y)\) are not equivalent in general. Combining a formula with itself, such as P and P, always gives an equivalence.
Review the concept: Order of quantifiers
For a predicate \(P(x,y)\), the order of the quantifiers can change the truth value of a formula.
\[\begin{gathered}\forall x\,\exists y\,P(x,y)\\\not\equiv\exists y\,\forall x\,P(x,y)\end{gathered}\]
More practice problems: order of quantifiers
- ZW-ORDER-OF-QUANTIFIERS-001 In general, changing the order of ∀ and ∃...
- ZW-ORDER-OF-QUANTIFIERS-002 ∀x ∃y P(x,y) allows...
- ZW-ORDER-OF-QUANTIFIERS-003 ∃y ∀x P(x,y) states that...
- ZW-ORDER-OF-QUANTIFIERS-005 The order of quantifiers matters especially when...
- ZW-ORDER-OF-QUANTIFIERS-006 In general, ∀x∃y R(x,y) and ∃y∀x R(x,y)...
- ZW-ORDER-OF-QUANTIFIERS-007 ∀x∃y R(x,y) allows...
- ZW-ORDER-OF-QUANTIFIERS-008 ∃y∀x R(x,y) states that...
- ZW-ORDER-OF-QUANTIFIERS-009 Select true statements about order.