Key Takeaways: Predicate Logic and Quantifiers

A one-page reference card. Reread it before an exam, or before writing a specification or a tricky negation.

Core vocabulary

Term One-line definition Truth value on its own?
Predicate $P(x)$ A statement with a variable; a boolean-valued function No — only after $x$ is assigned
Domain The collection a variable ranges over (Part of every quantified statement's meaning)
Universal $\forall x\,P(x)$ "For all $x$, $P(x)$" — a giant $\land$ Yes (relative to domain)
Existential $\exists x\,P(x)$ "There exists $x$, $P(x)$" — a giant $\lor$ Yes (relative to domain)
Bound variable A variable controlled by a quantifier (loop variable) — renameable, local
Free variable A variable not under any quantifier (enclosing parameter) — truth depends on it
Counterexample One domain element where $P$ fails Disproves $\forall x\,P(x)$

A formula with no free variables is a proposition; with ≥1 free variable it is a predicate.

Finite-domain identities (the mental model)

$$\forall x\,P(x) \;=\; P(d_1)\land P(d_2)\land\cdots\land P(d_n), \qquad \exists x\,P(x) \;=\; P(d_1)\lor P(d_2)\lor\cdots\lor P(d_n).$$

Empty domain Value Reason
$\forall x\,P(x)$ True (vacuously) identity of $\land$ is True; no element to violate it
$\exists x\,P(x)$ False identity of $\lor$ is False; no witness can exist

Translation idioms — $\forall$ pairs with $\rightarrow$, $\exists$ pairs with $\land$

English Logic Wrong version (do NOT use)
Every $Q$ is a $P$ $\forall x\,(Q(x)\rightarrow P(x))$ $\forall x\,(Q(x)\land P(x))$ — forces all to be $Q$
Some $Q$ is a $P$ $\exists x\,(Q(x)\land P(x))$ $\exists x\,(Q(x)\rightarrow P(x))$ — trivially true via non-$Q$

Negation laws (flip the quantifier, push $\neg$ inward)

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

$$\boxed{\;\neg\,\forall x\,(Q(x)\rightarrow P(x)) \equiv \exists x\,(Q(x)\land\neg P(x))\;}\quad\text{(uses } \neg(a\rightarrow b)\equiv a\land\neg b\text{)}$$

Procedure for nested negation: push $\neg$ in one quantifier at a time, flipping each ($\forall \leftrightarrow \exists$) as it passes, until $\neg$ lands on the inner predicate. Example: $$\neg\,\forall x\,\exists y\,P(x,y)\;\equiv\;\exists x\,\forall y\,\neg P(x,y).$$

Nested quantifiers — ORDER IS MEANING

Form Reading Dependence Strength
$\forall x\,\exists y\,P(x,y)$ every $x$ has some $y$ inner $y$ may depend on outer $x$ weaker
$\exists y\,\forall x\,P(x,y)$ one $y$ works for every $x$ $y$ fixed once, before $x$ stronger
  • $\exists y\,\forall x\,P \;\Rightarrow\; \forall x\,\exists y\,P$ (one-way only; converse fails).
  • Like quantifiers commute: $\forall x\forall y \equiv \forall y\forall x$; $\exists x\exists y \equiv \exists y\exists x$.
  • Mixed quantifiers do not commute in general — never swap a $\forall$ past an adjacent $\exists$.
  • Game reading: $\forall x\,\exists y$ = adversary picks $x$, then you answer with $y$ (you can react); $\exists y\,\forall x$ = you commit to $y$ first, then adversary attacks with any $x$.

Quantifiers as code

Logic Python Short-circuit behavior
$\forall x\in D,\ P(x)$ all(P(x) for x in D) returns False at first false $P(x)$; True on empty $D$
$\exists x\in D,\ P(x)$ any(P(x) for x in D) returns True at first true $P(x)$; False on empty $D$
disprove $\forall$ find first x with not P(x) that x is the counterexample

Why early exit works: $\land$ is settled by one False; $\lor$ is settled by one True — the same fact behind short-circuit and/or (Ch. 1).

Specification (the CS payoff)

Contract part Who owes it Typical quantifier shape
Precondition the caller must ensure it on entry often $\forall$ over indices/elements (e.g. "sorted")
Postcondition the function guarantees it on return $\exists$ for "found", $\forall$ for "all outputs valid"

A passing test verifies the postcondition at one point of the domain (one conjunct of the big $\land$). A specification is the postcondition for all valid inputs — a universal claim only a proof can settle. (Theme 2.)

Decision aid: how do I attack this statement?

Goal?
 ├─ PROVE  ∀x P(x)   → must handle the ENTIRE domain (often induction, Ch. 6) — no finite test suffices
 ├─ DISPROVE ∀x P(x) → exhibit ONE counterexample c with P(c) false  ✅ done
 ├─ PROVE  ∃x P(x)   → exhibit ONE witness c with P(c) true  ✅ done
 └─ DISPROVE ∃x P(x) → show ∀x ¬P(x): rule out the WHOLE domain

Translating restricted quantifiers?
 ├─ "every Q is P"  → ∀x (Q(x) → P(x))     [arrow]
 └─ "some Q is P"   → ∃x (Q(x) ∧ P(x))     [and]

Negating? → flip each quantifier, move ¬ inward; turn (Q → P) into (Q ∧ ¬P).

Common pitfalls

  • Swapping $\rightarrow$/$\land$ between the quantifiers (see idiom table — the #1 translation bug).
  • Reordering mixed quantifiers — $\forall x\exists y$ and $\exists y\forall x$ are different claims.
  • Negating an implication wrong — $\neg(Q\rightarrow P)$ is $Q\land\neg P$, not $Q\rightarrow\neg P$.
  • Vacuous truth in code — all(... for x in []) is True; guard with xs and all(...) if the empty case matters to your logic.
  • Mistaking a finite test for a proof — "no counterexample in the slice I looped over" ≠ "true over the whole (infinite) domain."

Toolkit additions (dmtoolkit/logic.py)

Function Meaning Note
for_all(predicate, domain) $\forall x\in D,\ P(x)$ via all() vacuously True on empty domain
there_exists(predicate, domain) $\exists x\in D,\ P(x)$ via any() False on empty domain
counterexample(predicate, domain) first failing x, else None None ⟺ for_all is True (negation law, executable)