Quantifiers (Concept) — Beginner-Friendly Notes

1. What Quantifiers Do

Quantifiers say how many objects a statement applies to:

• $\forall$ (universal): "for all" — applies to every object.
• $\exists$ (existential): "there exists" — applies to at least one object.

2. Semantics (meaning with domain)

Given a domain (set of objects) and interpretation:

• $\forall x\ P(x)$ is true iff $P(c)$ true for every object $c$ in domain.
• $\exists x\ P(x)$ is true iff $P(c)$ true for at least one object $c$.

Example domain = {Tweety, Penguin}:

• $\forall x\ Bird(x) \Rightarrow Flies(x)$ is false (Penguin is bird but doesn't fly).
• $\exists x\ Bird(x) \land Flies(x)$ is true (Tweety flies).

3. Patterns You Must Get Right (common exam error)

English	Wrong	Correct	Why?
Every bird flies	$\forall x\ Bird(x) \land Flies(x)$	$\forall x\ (Bird(x) \Rightarrow Flies(x))$	$\land$ would mean every object is a bird
Some bird flies	$\exists x\ (Bird(x) \Rightarrow Flies(x))$	$\exists x\ (Bird(x) \land Flies(x))$	$\Rightarrow$ would be true for any non-bird

Rule: $\forall$ goes with $\Rightarrow$, $\exists$ goes with $\land$ — memorise!

4. Nesting & Order Matters

• $\forall x\ \exists y\ Loves(x,y)$: "Everyone loves someone" (each may love different person) — true in many worlds.
• $\exists y\ \forall x\ Loves(x,y)$: "There is one person loved by everyone" — much stronger.

Swapping $\forall$ and $\exists$ changes meaning.

5. De Morgan for Quantifiers

• $
  eg \forall x\ P(x) \equiv \exists x\
  eg P(x)$
• $
  eg \exists x\ P(x) \equiv \forall x\
  eg P(x)$

6. Connection to CS

• $\forall$ ≈ for all loop must be true for every iteration.
• $\exists$ ≈ exists search — stop when one found.

7. One-Line Summary

$\forall x$ means the sentence holds for every domain element and pairs with $\Rightarrow$, while $\exists x$ means it holds for some element and pairs with $\land$, with nesting order determining strength and meaning.

8. Quick Self-Check

1. Write "Every student has a mentor" correctly.
2. Negate $\forall x\ \exists y\ Likes(x,y)$.