2.3 Predicates and Quantifiers

Section 2.1 introduced the open statement $x>4$. It was not yet a proposition because the value of $x$ was missing. We now need a compact way to talk about a property that different objects may or may not have, and then make a complete claim about those objects.

A predicate records the property. A quantifier states how many objects in a chosen domain must satisfy it.

By the end of this section, you will be able to:

• identify a predicate and its domain;

• evaluate universal and existential statements using counterexamples and witnesses;

• negate quantified statements correctly;

• explain why changing the order of two quantifiers can change meaning and truth.

A predicate becomes true or false after substitution

A predicate is a sentence containing one or more variables that becomes a proposition when values are substituted for those variables.

Let

The notation $P(x)$ names the predicate and shows that its truth depends on $x$. Substitution produces propositions:

Before evaluating a predicate, specify its domain (also called the universe of discourse): the set of values the variable is allowed to take.

If the domain is

then $P(x)$ may be tested only at those six values. Changing the domain can change a quantified statement’s truth. For example, “every number is positive” is true over $\{1,2,3\}$ but false over $\{-1,1,2,3\}$.

Predicates need not concern numbers. If $D$ is a set of devices, we may define

The expression $Online(d_2)$ is then a proposition about one particular device $d_2$.

Universal quantification checks every object

The universal quantifier is written $\forall$ and read “for every” or “for all.” The statement

means “for every $x$ in domain $D$, $P(x)$ is true.”

Using $D=\{1,2,3,4\}$ and

check the objects one at a time:

Every row passes, so $\forall x\in D,\;P(x)$ is true.

To show that a universal statement is false, we do not need to inspect forever. One failing object is enough. Such an object is a counterexample. If the domain changes to $D=\{1,2,3,4,7\}$, then $x=7$ is a counterexample because $P(7)$ is false.

This gives two different workloads:

• proving a finite universal statement requires checking every domain element;

• refuting it requires finding one counterexample.

Existential quantification searches for one witness

The existential quantifier is written $\exists$ and read “there exists” or “for at least one.” The statement

means “there is at least one $x$ in $D$ for which $P(x)$ is true.”

An object that makes the predicate true is called a witness. With $D=\{1,2,3,4,7\}$ and $P(x)$ meaning $x>4$, the value $7$ is a witness. We do not need every element to pass.

To prove an existential statement, exhibit one witness. To refute it over a finite domain, show that every possible object fails.

The contrast is worth memorizing through actions rather than slogans:

Boundary case: the empty domain

If $D=\emptyset$, there is no object that can violate a universal statement, so $\forall x\in D,\;P(x)$ is treated as true. There is also no object that can serve as an existential witness, so $\exists x\in D,\;P(x)$ is false.

This is the same pattern used in Chapter 1 to explain why $\emptyset\subseteq A$: no element exists that could violate the requirement.

The habitat lets you change both the predicate and its domain. Do not watch only the final true/false badge. Locate the highlighted object: under $\exists$ it is a witness that makes the statement true; under a false $\forall$ it is a counterexample that breaks the statement.

Translate quantified language in a fixed order

Natural language often hides the domain and predicate. Translate it in three steps:

1. identify the domain;

2. define the predicate in plain language;

3. choose the quantifier that matches “every,” “some,” or “no.”

Suppose $S$ is the set of students and

Then

means “every student submitted,” while

means “at least one student submitted.”

The sentence “no student submitted” says that no witness exists:

It can also be written as

These two forms have the same meaning.

Negating a quantifier swaps the search

To negate a universal statement, we need one counterexample:

Read this as: “it is not true that every object has property $P$” means “there exists an object that does not have property $P$.”

To negate an existential statement, every candidate must fail:

These are quantifier versions of De Morgan’s laws. Negation crosses the quantifier, changes $\forall$ to $\exists$ or $\exists$ to $\forall$, and then negates the predicate.

A frequent error is to negate only the predicate while leaving the quantifier unchanged. For example, the negation of “every sensor is active” is not “every sensor is inactive.” The correct negation is “at least one sensor is inactive.” A group containing both active and inactive sensors makes the difference visible.

Predicates with two variables describe pairwise relationships

A predicate may depend on more than one variable. Let

Once both $k$ and $r$ are supplied, $Unlocks(k,r)$ has a definite truth value. The ordered pair $(k,r)$ connects this idea to the Cartesian products from Section 1.3: all possible key–robot pairs form a product, and the true pairs form a relation.

Now compare two quantified statements:

and

Read quantifiers from left to right.

The first statement says:

> For every robot $r$, we can find some key $k$ that unlocks that robot.

The chosen key may be different for different robots.

The second statement says:

> There is one key $k$ that unlocks every robot $r$.

Now the same single key must work for all robots. This is a stronger requirement.

Consider three robots and three keys where $K_1$ opens $R_1$, $K_2$ opens $R_2$, and $K_3$ opens $R_3$. Every robot has some key, so the first statement is true. No single key opens all three, so the second statement is false. The order of quantifiers therefore cannot be swapped casually.

Paint the key–robot relation rather than merely reading it. First create a distributed solution in which each robot has access but no master key exists. Then fill one entire key column and observe exactly which quantified statement changes.

From logical statements to digital decisions

We can now write precise claims, negate them, and identify the evidence that would establish or refute them. Section 2.4 returns to the two truth values from the start of this chapter and treats them as $0$ and $1$. Boolean algebra will turn logical connectives and truth tables into rules that digital circuits can calculate.