Predicate Logic & Quantifiers

Discrete Mathematics Fundamentals

Chapter 3 · Predicate Logic & Quantifiers

Chapter 2 flagged x > 3 as not a proposition — its truth depends on a variable that hasn't been given a value yet. This chapter covers exactly that case properly: predicates, and the two quantifiers that turn a predicate into an actual, honest-to-goodness proposition.

What a Predicate Actually Is

A predicate is a statement containing one or more variables, which becomes a genuine proposition — true or false — the moment those variables are given specific values. Written P(x), a predicate is a template for a proposition, not a proposition itself.

ExpressionWhat it is
P(x): x > 3A predicate — no fixed truth value yet
P(5)A proposition — true
P(2)A proposition — false

This is already exactly what a boolean-returning function is in code — a predicate, parameterized truth, written in a different notation:

def is_adult(age): return age >= 18 # is_adult is the predicate P(x). is_adult(20) is a proposition (True).

The Universal Quantifier — ∀ ("for all")

∀x P(x) means P(x) is true for every value of x in whatever domain you're considering. This is exactly what Python's all() computes.

∀x P(x) — "for every x, P(x) holds" all(is_adult(age) for age in ages) # True only if every single age satisfies is_adult

The Existential Quantifier — ∃ ("there exists")

∃x P(x) means P(x) is true for at least one value of x in the domain — not necessarily all, just one is enough. This is exactly what Python's any() computes.

∃x P(x) — "there exists an x such that P(x) holds" any(is_adult(age) for age in ages) # True if at least one age satisfies is_adult
A quantifier is meaningless without a stated domain
∀x P(x) only makes sense once you've said what x ranges over — "for all x" in what set, exactly? In code, the domain is simply whatever you're iterating over — ages in the examples above. Leaving the domain unstated (in math or in code) is a genuine, common source of confusion.

Combining Quantifiers: "Every P Is a Q" vs. "Some P Is a Q"

In practice, quantifiers almost always pair with a specific second connective, and the pairing is easy to get backwards:

EnglishCorrect translationWhy this connective
"Every P is a Q"∀x (P(x) → Q(x))For any x, if it's a P, then it must also be a Q
"Some P is a Q"∃x (P(x) ∧ Q(x))There's an x that is both a P and a Q, at the same time
The classic translation mistake
Writing ∀x (P(x) ∧ Q(x)) for "every P is a Q" is a genuine, common error — it actually claims that every single x in the entire domain is both a P and a Q, which is a far stronger (and usually false) statement. "Every student who submitted on time gets full marks" does not mean every person in existence submitted on time and got full marks — it means if someone submitted on time, then they got full marks. ∀ pairs with →; ∃ pairs with ∧ — mixing these up is the single most common predicate-logic translation mistake.

Negating Quantified Statements

Predicate logic has its own version of Chapter 2's De Morgan's Laws — negating a quantifier flips it to the other quantifier:

StatementNegationPlain English
¬(∀x P(x))≡ ∃x ¬P(x)"Not all" means "at least one fails"
¬(∃x P(x))≡ ∀x ¬P(x)"None exist" means "all fail"
# These two are logically equivalent — a genuinely useful real refactor: not all(is_verified(u) for u in users) any(not is_verified(u) for u in users)
Combining this with Chapter 2's own ¬(p → q) rule
Negating "every P is a Q" — ¬(∀x (P(x) → Q(x))) — becomes ∃x ¬(P(x) → Q(x)), and Chapter 2 already established that ¬(p → q) ≡ p ∧ ¬q. Chaining both rules together: ¬(∀x (P(x) → Q(x))) ≡ ∃x (P(x) ∧ ¬Q(x)) — "not every P is a Q" means "there's a P that is not a Q." This is exactly the two-step reasoning a proof by contradiction (Chapter 7) often starts with: to disprove "every P is a Q," it's enough to produce a single counterexample — one P that isn't a Q.

Nested Quantifiers — Order Genuinely Changes the Meaning

When two quantifiers appear together, swapping their order can produce a completely different statement:

StatementMeaning
∀x ∃y Mother(y, x)Every person x has some mother y — a possibly different y for each x
∃y ∀x Mother(y, x)There's one single y who is the mother of every person x

The first is an ordinary true fact about the world. The second claims one person is literally everyone's mother — obviously false. Same symbols, same predicate, reversed order, opposite truth value. When both quantifiers are the same type (∀∀ or ∃∃), order doesn't matter; the moment they're mixed (∀∃ or ∃∀), it does.

Hands-On Exercises

Exercise 1

Translate "every function in this module has a docstring" into quantified predicate logic, clearly stating the domain and which two predicates you're using. Then explain why using ∧ instead of → would be a translation mistake here.

📄 View solution
Exercise 2

A test asserts not any(order.total < 0 for order in orders). Rewrite this using De Morgan's Law for quantifiers so it reads as an ∀ statement instead of a negated ∃ statement, and state in plain English what the rewritten version says.

📄 View solution
Exercise 3

For the two statements ∀x ∃y Likes(x, y) ("everyone likes someone") and ∃y ∀x Likes(x, y) ("there's someone everyone likes"), explain in your own words why these are genuinely different claims, and give an example of a group of people for which the first is true but the second is false.

📄 View solution

Chapter 3 Quick Reference