Quantifiers

About 393 wordsAbout 1 min

2025-07-29

Negating Quantifiers

A key relationship in logic is how to negate quantified statements:

$\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$ $\neg (\forall x, P (x)) \equiv \exists x, \neg P (x)$
- "It is not true that all students passed" $\equiv$ "There exists at least one student who did not pass."
$\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$ $\neg (\exists x, P (x)) \equiv \forall x, \neg P (x)$
- "There does not exist a perfect number" $\equiv$ "For all numbers, they are not perfect."

Existential Quantifier (∃): Read as "there exists". The statement

∃X,P(X) is true if there is at least one value for X in its domain that makes P(X) true. It is analogous to a logical

Universal Quantifier (∀): Read as "for all" or "for every". The statement

∀X,P(X) is true if P(X) is true for every possible value of X in its domain.

With Conjunction ( $\wedge$ ):
- $\forall X(p(X) \land q(X)) \equiv (\forall X, p(X)) \land (\forall X, q(X))$ . "Everything is a square and is blue" is the same as "Everything is a square AND everything is blue".
- $\exists X(p(X) \land q(X)) \Rightarrow (\exists X, p(X)) \land (\exists X, q(X))$ . If there exists a "blue square", then there must exist something that is blue AND there must exist something that is a square. The reverse is not true (having a blue circle and a red square doesn't mean a blue square exists).
With Disjunction ( $\vee$ ):
- $\exists X(p(X) \lor q(X)) \equiv (\exists X, p(X)) \lor (\exists X, q(X))$ . "There exists something that is a square or is blue" is the same as "There exists a square OR there exists something blue".
- $(\forall X, p(X)) \lor (\forall X, q(X)) \Rightarrow \forall X(p(X) \lor q(X))$ $(\forall X, p (X)) \lor (\forall X, q (X)) \Rightarrow \forall X (p (X) \lor q (X))$ . The reverse implication is not true.
  - Example: Let the domain be integers. Let $p(X)$ $p (X)$ be " $X$ $X$ is even" and $q(X)$ $q (X)$ be " $X$ $X$ is odd".
    - $\forall X(p(X) \lor q(X))$ means "For all integers, X is either even or odd". This is TRUE.
    - $(\forall X, p(X)) \lor (\forall X, q(X))$ means "All integers are even, OR all integers are odd". This is FALSE.

8/4/25, 11:40 AM

View All Changelog