Predicate Logic and Quantifiers

Statements About Everything and Something

Propositional logic cannot express general statements like "every integer has a successor." Predicate logic solves this by adding predicates $P(x)$—statements with variables that are true or false depending on $x$—and quantifiers.

Common pitfall: A universal claim ($\forall x\, P(x)$) is disproved by a single counterexample where $P(x)$ fails.

Order and Negation

The order of quantifiers matters enormously. $\forall x\, \exists y\, P(x,y)$ means "every $x$ has some $y$," which is very different from $\exists y\, \forall x\, P(x,y)$, meaning "some single $y$ works for all $x$."

For example, "every person has a mother" is true, but "there is one mother of everyone" is false. Swapping quantifiers silently alters meaning.

To negate quantifiers, flip the quantifier and negate the inner predicate:

• $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$
• $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$

Common pitfall: $\neg \forall x\, P(x)$ means "not all" ($+\text{at least one isn't}$), not "none is."