Predicates and Quantifiers

13 min read

Quick Reference

Before You Start: Prerequisite Check

Try This First

Read each row of the table out loud and decide, before any formula appears, whether the sentence is true or false. The variable $x$ ranges over the whole numbers $1, 2, 3, 4, 5$.

Why Predicates and Quantifiers Matter

A proposition such as “$5$ is greater than $3$” already has a fixed truth value, so propositional logic cannot say anything about a variable. Mathematics is full of statements about variables: “every integer has a successor”, “some real number squares to $2$”, “for each input there is an output”. These statements cannot be written with propositional connectives alone.

A predicate is a process: it takes an input and gives back a proposition. Feed it the value $5$ and the process returns the true proposition “$5 > 3$”; feed it the value $2$ and the process returns the false proposition “$2 > 3$”. A quantifier then collapses all of those individual propositions into one claim about the whole domain. The universal quantifier asks whether the predicate holds for every input. The existential quantifier asks whether it holds for at least one input.

This pairing (a predicate that responds to inputs, and a quantifier that sweeps the domain) is the language used to state every definition, theorem, and proof in the rest of the course.

Prerequisite Hub

Predicates and quantifiers belong to the logic strand of discrete mathematics. The map shows what to master first and what this skill opens up next.

graph LR
    subgraph Builds On
        A["Propositional<br/>Logic"]
        B["Propositional<br/>Equivalences"]
        C["Set-Builder and<br/>Roster Notation"]
    end

    subgraph ThisSkill["This Skill"]
        D["Predicates and<br/>Quantifiers"]
    end

    subgraph Unlocks
        E["Nested<br/>Quantifiers"]
        F["Rules of<br/>Inference"]
    end

    A --> D
    B --> D
    C --> D
    D --> E
    D --> F

    style D fill:#d1fae5,stroke:#a565f0,stroke-width:3px

    click E "../ch1-sec5/nested-quantifiers.html"

Builds on (master these first):

Unlocks (these come next):

Cross-course prerequisites: none.

Official Definitions

The definitions below are quoted from Rosen 8th edition, Section 1.4, on the pages noted.

Predicate (propositional function)

A statement such as “$x$ is greater than $3$” has two parts: the variable $x$, the subject of the statement, and the predicate “is greater than $3$”, which refers to a property the subject can have. The statement is denoted $P(x)$, where $P$ is the predicate and $x$ is the variable. The statement $P(x)$ is the value of the propositional function $P$ at $x$; once a value is assigned to $x$, $P(x)$ becomes a proposition with a truth value.

Cite: Rosen 8e, Section 1.4, subsection 1.4.2 Predicates, p.41.

Domain of discourse (domain)

A statement that is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), is expressed using universal quantification. The domain specifies the possible values of the variable and must always be specified when a quantifier is used.

Cite: Rosen 8e, Section 1.4, p.44.

Universal quantifier (universal quantification)

The universal quantification of $P(x)$ is the statement “$P(x)$ for all values of $x$ in the domain.” The notation $\forall x\, P(x)$ denotes the universal quantification of $P(x)$. Here $\forall$ is called the universal quantifier. An element for which $P(x)$ is false is called a counterexample to $\forall x\, P(x)$.

Cite: Rosen 8e, Section 1.4, Definition 1, p.44.

Existential quantifier (existential quantification)

The existential quantification of $P(x)$ is the proposition “There exists an element $x$ in the domain such that $P(x)$.” The notation $\exists x\, P(x)$ denotes the existential quantification of $P(x)$. Here $\exists$ is called the existential quantifier.

Cite: Rosen 8e, Section 1.4, Definition 2, p.45.

Truth conditions at a glance

Truth conditions follow Table 1, Rosen 8e, Section 1.4.

A reminder that quantification depends on the domain: $\forall x\, (x > 3)$ is false over the integers (take $x = 0$) and true over the domain $\{4, 5, 6\}$. State the domain before judging a quantified statement.

Key Theorem: De Morgan’s Laws for Quantifiers

De Morgan’s Laws for Quantifiers. Negating a quantified statement swaps the quantifier and pushes the negation onto the predicate:

$$\boxed{\;\lnot\,\forall x\, P(x) \;\equiv\; \exists x\, \lnot P(x) \qquad\text{and}\qquad \lnot\,\exists x\, Q(x) \;\equiv\; \forall x\, \lnot Q(x)\;}$$

Statement: $\lnot\,\forall x\, P(x)$ is logically equivalent to $\exists x\, \lnot P(x)$, and $\lnot\,\exists x\, Q(x)$ is logically equivalent to $\forall x\, \lnot Q(x)$.

Cite: Rosen 8e, Section 1.4, Table 2 (De Morgan’s Laws for Quantifiers), p.55.

Reading the laws in words. The statement “not everything has the property” means the same as “something fails to have the property.” The statement “nothing has the property” means the same as “everything fails to have the property.” Each law turns a $\forall$ into an $\exists$ (or the reverse) and moves the negation inside.

Worked Examples

Example 1: A predicate is a process, not yet a proposition

Let the domain be the integers, and let $P(x)$ be the predicate “$x^2 \geq x$.”

Predict first. Before computing, guess whether $P(x)$ has a single truth value as written. Then test it at two inputs.

Check.

• At $x = 3$: $P(3)$ is “$3^2 \geq 3$”, that is “$9 \geq 3$”, which is true.
• At $x = 0$: $P(0)$ is “$0^2 \geq 0$”, that is “$0 \geq 0$”, which is true.
• At $x = -2$: $P(-2)$ is “$(-2)^2 \geq -2$”, that is “$4 \geq -2$”, which is true.

The predicate $P(x)$ on its own has no fixed truth value; it returns a different proposition for each input. Only after an input is supplied does it become a proposition. The prediction that “$P(x)$ already has one truth value” is the misconception this example targets.

Example 2: Reading $\forall$ and finding a counterexample

Let the domain be the integers $\{1, 2, 3, 4, 5\}$, and let $Q(x)$ be “$x$ is greater than $3$.” Decide the truth value of $\forall x\, Q(x)$.

Predict first. The claim says every listed integer exceeds $3$. Scan the list and predict true or false.

Check. Evaluate $Q$ at each element:

The value $x = 1$ makes $Q(x)$ false, so $x = 1$ is a counterexample. A single counterexample is enough to make $\forall x\, Q(x)$ false. Notice that $x = 2$ and $x = 3$ are also counterexamples; the universal statement fails the moment the first one appears.

Example 3: Reading $\exists$

Keep the same domain $\{1, 2, 3, 4, 5\}$ and the same predicate $Q(x): x > 3$. Decide the truth value of $\exists x\, Q(x)$.

Predict first. This claim asks only for one success. Predict before checking.

Check. From the table in Example 2, $Q(4)$ is true. One witness is enough, so $\exists x\, Q(x)$ is true. The existential statement needs only a single value that works, while the universal statement needed every value to work.

Example 4: Negating a universal statement with De Morgan

Let the domain be all students in a class, and let $S(x)$ be “$x$ has taken a calculus course.” Consider the statement $\forall x\, S(x)$ (“every student has taken a calculus course”). Write its negation as an existential statement.

Predict first. In plain words, what would make “every student has taken calculus” false? Predict the English sentence, then convert it to symbols.

Check. The statement is false exactly when at least one student has not taken calculus. By De Morgan for quantifiers:

$$\lnot\,\forall x\, S(x) \;\equiv\; \exists x\, \lnot S(x).$$

In words: “There is a student who has not taken a calculus course.” The negation turned $\forall$ into $\exists$ and pushed the negation onto the predicate $S(x)$, giving $\lnot S(x)$.

Example 5: Negating an existential statement, two ways

Let the domain be the real numbers, and let $R(x)$ be “$x^2 = -1$.” Consider $\exists x\, R(x)$ (“some real number squares to $-1$”). Negate it.

One way to see this. Apply De Morgan for quantifiers directly:

$$\lnot\,\exists x\, R(x) \;\equiv\; \forall x\, \lnot R(x),$$

which reads “for every real number $x$, it is not the case that $x^2 = -1$”, that is “every real number has $x^2 \neq -1$.”

Another way to see this. Reason about the original statement first. Over the reals, $x^2 \geq 0$ for every $x$, so no real number squares to $-1$; the existential statement $\exists x\, R(x)$ is false, and its negation is therefore true. The De Morgan form $\forall x\, (x^2 \neq -1)$ agrees: it is a true statement over the reals. Which path feels clearer to you, the symbolic rewrite or the reasoning about values? Both reach the same equivalent statement.

Common Misconceptions

Practice Problems

Mastery Checklist

Novice (Level 1-2):

• I can evaluate a predicate $P(x)$ at a given value and report the truth value of the resulting proposition
• I can explain why a predicate is not a proposition until a value is supplied
• I can determine the truth value of $\forall x\, P(x)$ over a small finite domain and produce a counterexample when one exists

Competent (Level 3-4):

• I can determine the truth value of $\exists x\, P(x)$ and name a witness when the statement is true
• I can state how much evidence a universal statement needs compared with an existential statement
• I can negate $\forall x\, P(x)$ and $\exists x\, P(x)$ using De Morgan’s laws for quantifiers

Proficient (Level 5):

• I can negate a quantified statement, simplify the negated predicate, and report the truth value of both forms
• I can explain in words why $\lnot\,\forall x\, P(x)$ becomes $\exists x\, \lnot P(x)$
• I can choose a domain that changes the truth value of a quantified statement and explain the change

Mental Model

The domain sweep. Picture the domain as a row of boxes, one box per element. A predicate $P$ is a stamp that prints “true” or “false” on a box once a value is dropped in. The universal quantifier $\forall$ walks the whole row and reports “true” only if no box came back false. The existential quantifier $\exists$ walks the row and reports “true” the moment one box comes back true. Negation flips the report and switches which quantifier is doing the walking: “not every box is true” is the same as “some box is false.”

Connections

Looking back:

• Propositional Logic supplies the truth values that a predicate produces once a value is fixed
• Propositional Equivalences supplies the De Morgan laws that extend to quantifiers
• Set-Builder and Roster Notation supplies the domain of discourse a quantifier ranges over

Looking ahead:

• Nested Quantifiers: two or more quantifiers in one statement, where the order of $\forall$ and $\exists$ changes the meaning
• Rules of Inference: universal and existential instantiation and generalization inside formal proofs

Real-world connections:

• A database query “return every record where the balance is negative” is a universal check, and “does any record have a negative balance” is an existential check
• A safety claim “all units passed inspection” is refuted by one failing unit, the counterexample

Resources

Last updated: 2026-06-16