In previous chapters, we studied propositional logic: propositions, logical connectives, truth tables, equivalences, rules of inference, and logic circuits. All of those tools work with complete propositions represented by letters (\( p \), \( q \), \( r \)…).
However, there are everyday arguments that propositional logic simply cannot handle. In this chapter, you’ll learn why, and discover the tools that overcome this limitation: logical quantifiers.
Why Is Propositional Logic Not Enough?
Consider the most famous argument in the history of logic:
Premise 1: All men are mortal. Premise 2: Socrates is a man. Conclusion: Socrates is mortal.
This argument is clearly valid. But if we try to represent it using propositional logic with propositional variables (letters):
- \( p \): “All men are mortal”
- \( q \): “Socrates is a man”
- \( r \): “Socrates is mortal”
We’d get the structure \( p, q \vdash r \), read as “\( p \) and \( q \), therefore \( r \)” (see the chapter on logical inference). But here’s the problem: there is no rule of inference that lets us deduce \( r \) from \( p \) and \( q \), because propositional logic treats each proposition as an indivisible unit — it can’t “look inside” to see that all three share the same underlying concepts (men, mortal, Socrates).
The same issue arises with arguments that use the word “some.” Consider:
Premise 1: Some doctors are researchers. Premise 2: All researchers publish papers. Conclusion: Some doctors publish papers.
This argument is also clearly valid. But once again, if we assign \( p \), \( q \), and \( r \) to each premise and conclusion, we get \( p, q \vdash r \), and propositional logic can’t justify the deduction. It can’t see that “some doctors” from Premise 1 fall within “the researchers” of Premise 2, and therefore inherit the property of publishing papers.
If you look closely, both examples share a common pattern:
- “All elements of a set satisfy a property”
- “There exists at least one element that satisfies a property”
To express these ideas, we need a new set of tools: logical quantifiers, which we’ll study shortly.
Propositional Functions (Open Sentences)
Before studying quantifiers, we need to understand a prerequisite concept: the propositional function.
Definition
A propositional function (also called an open sentence) is an expression containing one or more variables that becomes a proposition once those variables are replaced with specific values.
It is denoted as \( P(x) \), where:
- \( P \) is the predicate (the property being evaluated)
- \( x \) is the variable
Examples
| Propositional function | Variable | What does it describe? |
|---|---|---|
| \( P(x) \): “\( x + 5 < 11 \)” | \( x \) | A numerical inequality |
| \( Q(x) \): “\( 2x – 3 = 7 \)” | \( x \) | An equation |
| \( R(x) \): “\( x \) is a prime number” | \( x \) | A numerical property |
| \( S(x) \): “\( x \) is a country in America” | \( x \) | A geographical property |
How Does It Become a Proposition?
By substituting the variable with a specific value, the propositional function becomes a proposition with a truth value:
Example 1: Let \( P(x) \): “\( x + 5 < 11 \)” with \( x \in \mathbb{Z} \)
- If \( x = 3 \): \( P(3) \): “\( 3 + 5 < 11 \)” → “\( 8 < 11 \)” → True ✓
- If \( x = 7 \): \( P(7) \): “\( 7 + 5 < 11 \)” → “\( 12 < 11 \)” → False ✗
Example 2: Let \( S(x) \): “\( x \) is a country in America”
- If \( x = \) Peru: \( S(\text{Peru}) \): “Peru is a country in America” → True ✓
- If \( x = \) Japan: \( S(\text{Japan}) \): “Japan is a country in America” → False ✗
The Domain of the Variable
The domain is the set of all values that the variable can take. It is denoted by \( D \) or with the notation \( x \in D \).
For example:
- If \( P(x) \): “\( x + 5 < 11 \)” and the domain is \( \mathbb{N} \) (natural numbers), then \( x \) can only take values 1, 2, 3, …
- If the domain is \( \mathbb{Z} \) (integers), then \( x \) can also be negative: …, -2, -1, 0, 1, 2, …
Important: A propositional function by itself is not a proposition, because it has no truth value until a value is assigned to the variable.
What Is NOT a Propositional Function?
Not every expression with variables qualifies as a propositional function. To count as one, it must produce a true or false proposition when the variable is substituted.
Example: The expression \( 2x^2 – 6 \) is not a propositional function because plugging in \( x = 3 \) gives \( 2(9) – 6 = 12 \). The result is just a number — not a claim that can be judged true or false.
From Propositional Function to Proposition: Two Methods
So far, we have seen one method for obtaining propositions from a propositional function: substituting the variable with a specific value. For example, by replacing \( x \) with 3 in \( P(x): x + 5 < 11 \), we obtain the proposition \( P(3): 8 < 11 \), which is true.
However, there’s a second, completely different method that also turns propositional functions into propositions — but without assigning any specific value to the variable. Instead, we place an expression in front of the propositional function that tells us how many elements of the domain satisfy the property: all of them? at least one?
These expressions are called quantifiers, and they are the tool we will study next.
The Universal Quantifier (∀)
The first of the two quantifiers is the universal quantifier.
Definition
The universal quantifier allows us to assert that all elements of a domain satisfy a property. It is symbolized by \( \forall \) (an inverted “A,” from “for All“).
Given a propositional function \( P(x) \) with domain \( A \), the expression:
\[ \forall x \in A: P(x) \]
is read: “For all \( x \) belonging to \( A \), \( P(x) \) holds”.
Equivalent Notations
| Notation | Reading |
|---|---|
| \( \forall x \in A: P(x) \) | “For all \( x \) in \( A \), \( P(x) \)” |
| \( \forall x \in A \mid P(x) \) | “For all \( x \) in \( A \) such that \( P(x) \)” |
| \( (\forall x \in A)(P(x)) \) | “For all \( x \) in \( A \), \( P(x) \)” |
All of these mean the same thing. In this article, we will primarily use the first notation.
Other Ways to Read It
The expression \( \forall x \in A: P(x) \) can also be read as:
- “For each \( x \) in \( A \), \( P(x) \) holds”
- “Whatever \( x \) in \( A \) may be, \( P(x) \) is true”
- “Every element of \( A \) satisfies property \( P \)”
When Is It True and When Is It False?
| Situation | Truth value |
|---|---|
| All elements of \( A \) satisfy \( P(x) \) | True |
| At least one element of \( A \) does not satisfy \( P(x) \) | False |
Key: Finding just one element that does not satisfy the property is enough to make the universal proposition false.
Examples with Finite Sets
Example 1: Let \( A = {-1, 2, 3, 4} \)
\( \forall x \in A: 3x – 2 < 12 \)
Let’s check each element:
- \( x = -1 \): \( 3(-1) – 2 = -5 < 12 \) ✓
- \( x = 2 \): \( 3(2) – 2 = 4 < 12 \) ✓
- \( x = 3 \): \( 3(3) – 2 = 7 < 12 \) ✓
- \( x = 4 \): \( 3(4) – 2 = 10 < 12 \) ✓
All of them check out → The proposition is True ✅
Example 2: Let \( A = {-1, 1, 2, 3} \)
\( \forall x \in A: x \in \mathbb{N} \) (“Every \( x \) in \( A \) is a natural number”)
- \( x = -1 \): \( -1 \in \mathbb{N} \)? Does not hold ✗
We found a counterexample → The proposition is False ❌
Example 3: Let \( A = {-1, 1, 2, 3} \)
\( \forall x \in A: x^2 + 3x + 1 > 0 \)
- \( x = -1 \): \( 1 – 3 + 1 = -1 > 0 \)? Does not hold ✗
The proposition is False ❌ (the first counterexample is sufficient).
Examples with Infinite Sets
Example 4: \( \forall x \in \mathbb{R}: x^2 + 1 > 0 \)
Since \( x^2 \geq 0 \) for every real number, we always have \( x^2 + 1 \geq 1 > 0 \). → True ✅
Example 5: \( \forall x \in \mathbb{R}: x^2 + 1 < 0 \)
Impossible, since \( x^2 + 1 \) is always positive. → False ❌
Example 6: \( \forall y \in \mathbb{R}: (y – 1)^2 \geq 0 \)
The square of any real number is always greater than or equal to zero. → True ✅
The Existential Quantifier (∃)
Definition
The existential quantifier allows us to assert that there exists at least one element of the domain that satisfies a property. It is symbolized by \( \exists \) (an inverted “E”).
Given a propositional function \( P(x) \) with domain \( A \), the expression:
\[ \exists x \in A: P(x) \]
is read: “There exists at least one \( x \) in \( A \) such that \( P(x) \) holds”.
Equivalent Notations
| Notation | Reading |
|---|---|
| \( \exists x \in A: P(x) \) | “There exists \( x \) in \( A \) such that \( P(x) \)” |
| \( \exists x \in A \mid P(x) \) | “There exists \( x \) in \( A \) such that \( P(x) \)” |
| \( (\exists x \in A)(P(x)) \) | “There exists \( x \) in \( A \) such that \( P(x) \)” |
Other Ways to Read It
- “There is at least one \( x \) in \( A \) such that \( P(x) \)”
- “For some \( x \) in \( A \), \( P(x) \) is true”
- “Some element of \( A \) satisfies \( P \)”
When Is It True and When Is It False?
| Situation | Truth value |
|---|---|
| At least one element of \( A \) satisfies \( P(x) \) | True |
| No element of \( A \) satisfies \( P(x) \) | False |
Key: Finding just one element that satisfies the property is enough to make the existential proposition true.
Examples
Example 1: Let \( A = {-2, -1, 2, 3, 4} \)
\( \exists x \in A: x^2 – 2x = 8 \)
We test several values from the set:
- \( x = -2 \): \( (-2)^2 – 2(-2) = 4 + 4 = 8 \) ✓
- \( x = -1 \): \( (-1)^2 – 2(-1) = 1 + 2 = 3 \neq 8 \) ✗
- \( x = 2 \): \( (2)^2 – 2(2) = 4 – 4 = 0 \neq 8 \) ✗
Does it matter that \( x = -1 \) and \( x = 2 \) failed? Not at all — the existential quantifier only needs at least one value to satisfy the property, and \( x = -2 \) already did. → True ✅
Example 2: \( \exists x \in \mathbb{N}: 0 < x < 2 \)
- \( x = 1 \): \( 0 < 1 < 2 \) ✓
→ True ✅
Example 3: \( \exists x \in \mathbb{Z}: 2x = 1 \)
We would need \( x = \frac{1}{2} \), but \( \frac{1}{2} \notin \mathbb{Z} \). No integer satisfies the equation. → False ❌
Example 4: \( \exists x \in \mathbb{N}: x \) is even and prime.
- \( x = 2 \): is even ✓ and is prime ✓
→ True ✅ (2 is the only number that is both even and prime)
The Uniqueness Quantifier (∃!)
There is a special variant of the existential quantifier: the uniqueness quantifier, written as \( \exists! \) and read as “there exists a unique”.
\( \exists! x \in A: P(x) \) means that there is exactly one element in \( A \) that satisfies \( P(x) \).
Example 1: \( \exists! x \in \mathbb{Z}: 2 < x < 4 \)
The only integer between 2 and 4 is \( x = 3 \). → True ✅
Example 2: \( \exists! x \in \mathbb{R}: e^{x^2 – 9} = 1 \)
We need \( x^2 – 9 = 0 \), which gives \( x = 3 \) and \( x = -3 \). Since there are two solutions (not a unique one), the proposition is False ❌.
Relationship Between ∀ and ∃
The universal and existential quantifiers are closely related:
| If… | Then… |
|---|---|
| \( \forall x \in A: P(x) \) is true | \( \exists x \in A: P(x) \) is also true |
| \( \exists x \in A: P(x) \) is false | \( \forall x \in A: P(x) \) is also false |
Put simply: if every element satisfies the property, then at least one certainly does. And if no element satisfies it, then it’s certainly not the case that all of them do.
Note: The converse does not always hold. The fact that at least one satisfies \( P(x) \) does not mean that all of them do.
Negation of Quantified Propositions
The negation of propositions with quantifiers follows two fundamental rules, known as De Morgan’s Theorems for Quantifiers (analogous to De Morgan’s laws that we studied in the chapter on logical equivalences).
Rule 1: Negation of the Universal Quantifier
\[ \neg[\forall x \in A: P(x)] \equiv \exists x \in A: \neg P(x) \]
In words: “It is not true that all satisfy \( P \)” is equivalent to “There exists at least one that does not satisfy \( P \).”
Example: Negate “All planets are habitable”:
- \( \neg[\forall x: x \text{ is habitable}] \)
- \( \equiv \exists x: x \text{ is not habitable} \)
- → “There exists at least one planet that is not habitable” ✓
Rule 2: Negation of the Existential Quantifier
\[ \neg[\exists x \in A: P(x)] \equiv \forall x \in A: \neg P(x) \]
In words: “It is not true that there exists one that satisfies \( P \)” is equivalent to “None satisfy \( P \).”
Example: Negate “There exists a habitable planet”:
- \( \neg[\exists x: x \text{ is habitable}] \)
- \( \equiv \forall x: x \text{ is not habitable} \)
- → “No planet is habitable” (or “All planets are not habitable”) ✓
Summary of the Two Rules
| Original proposition | Its negation |
|---|---|
| \( \forall x \in A: P(x) \) | \( \exists x \in A: \neg P(x) \) |
| \( \exists x \in A: P(x) \) | \( \forall x \in A: \neg P(x) \) |
Mnemonic: When negating, flip the quantifier (\( \forall \leftrightarrow \exists \)) and negate the property.
Worked Examples
Example 1: Negate \( \forall x \in \mathbb{N}: x + 3 > 5 \)
\[ \neg[\forall x \in \mathbb{N}: x + 3 > 5] \equiv \exists x \in \mathbb{N}: x + 3 \leq 5 \]
Notice that when negating \( > \) (strict greater than) we get \( \leq \) (less than or equal), not simply \( < \). This is because the opposite of “being strictly greater than 5” is “not being greater than 5,” meaning being equal to 5 or less than 5. In general:
| Original inequality | Its negation |
|---|---|
| \( > \) | \( \leq \) |
| \( < \) | \( \geq \) |
| \( \geq \) | \( < \) |
| \( \leq \) | \( > \) |
Coming back to our example, the negated proposition — “There exists at least one natural number \( x \) such that \( x + 3 \leq 5 \)” — is indeed true: \( x = 1 \) gives us \( 4 \leq 5 \) ✓.
Example 2: Negate \( \exists x \in \mathbb{R}: x^3 = x^2 \)
\[ \neg[\exists x \in \mathbb{R}: x^3 = x^2] \equiv \forall x \in \mathbb{R}: x^3 \neq x^2 \]
“For every real number, \( x^3 \neq x^2 \).” (This is false, since \( x = 0 \) and \( x = 1 \) satisfy \( x^3 = x^2 \).)
Example 3: Negate \( \forall x \in A: P(x) \rightarrow Q(x) \)
We combine both techniques: first, flip the quantifier; then, negate the conditional using the equivalence \( \neg(p \rightarrow q) \equiv p \land \neg q \):
\[ \neg[\forall x \in A: P(x) \rightarrow Q(x)] \equiv \exists x \in A: P(x) \land \neg Q(x) \]
Example 4: Negate \( \exists x \in \mathbb{R}: 1 \leq x^2 < 4 \)
\[ \neg[\exists x \in \mathbb{R}: 1 \leq x^2 < 4] \equiv \forall x \in \mathbb{R}: x^2 < 1 \lor x^2 \geq 4 \]
The compound inequality \( 1 \leq x^2 < 4 \) is negated by separating it into two conditions joined by “or.”
Propositional Functions with More Than One Variable
So far, we’ve only dealt with propositional functions of a single variable. But propositional functions can also have two or more variables.
Definition
A propositional function of \( n \) variables has the form \( P(x_1, x_2, …, x_n) \), and it becomes a proposition when values are assigned to all variables.
Examples
Example 1: \( P(x, y) \): “\( x + y = 10 \)”
- \( P(3, 7) \): “\( 3 + 7 = 10 \)” → T
- \( P(2, 5) \): “\( 2 + 5 = 10 \)” → F
Example 2: \( P(x, y) \): “\( x \) is a sibling of \( y \)”
- \( P(\text{John}, \text{Mary}) \): “John is a sibling of Mary” → T or F depending on the case
Example 3: \( P(x, y, z) \): “\( x + y + z = 1 \)”
- \( P(2, 3, -4)\): “\( 2 + 3 + (-4) = 1 \)” → T
- \( P(1, 1, 1) \): “\( 1 + 1 + 1 = 1 \)” → F
Propositions with Multiple Quantifiers
When a propositional function has two or more variables, we can apply a quantifier to each one. This leads to expressions with multiple quantifiers, such as:
\[ \forall x, \exists y: P(x, y) \]
The Fundamental Rule: Order Matters
The order of quantifiers can completely change the meaning of the proposition.
Let’s look at a classic example to see why.
Detailed Example: \( x + y + z = 1 \)
Let \( P(x, y, z) \): “\( x + y + z = 1 \)” with domain \( \mathbb{R} \).
Proposition A: \( \forall z, \exists y, \forall x: x + y + z = 1 \)
Reading: “For all \( z \), there exists a \( y \) such that, for all \( x \), \( x + y + z = 1 \) holds.”
Let’s break this down: take \( z = -3 \). The proposition claims there exists some \( y_0 \) such that for every \( x \), \( x + y_0 – 3 = 1 \), i.e., \( y_0 + x = 4 \).
- If \( x = 1 \): \( y_0 = 3 \)
- If \( x = 0 \): \( y_0 = 4 \)
The same \( y_0 \) would need to equal 3 and 4 simultaneously! Impossible. → False ❌
Proposition B: \( \forall z, \forall x, \exists y: x + y + z = 1 \)
Reading: “For all \( z \) and for all \( x \), there exists a \( y \) such that \( x + y + z = 1 \).”
Here, for each pair \( (z, x) \) we look for a \( y \) (which can be different each time):
- If \( z = 2 \), \( x = 1 \): \( y = -2 \) ✓
- If \( z = 0 \), \( x = 2 \): \( y = -1 \) ✓
- For any \( z \) and \( x \): \( y = 1 – x – z \) ✓
→ True ✅
Conclusion: Propositions A and B have the same quantifiers and the same propositional function, but by changing the order of \( \forall x \) and \( \exists y \), the truth value changes. This demonstrates that the order of quantifiers is essential.
Example with Finite Sets
Let \( H = {\text{John, Luis, Ruben}} \) and \( M = {\text{Carmen, Patricia}} \), and \( P(x, y) \): “\( x \) is a brother of \( y \).”
Proposition 1: \( \forall x \in H, \exists y \in M: P(x, y) \)
“For every man in \( H \), there exists a woman in \( M \) such that he is her brother.” → Each man is a brother of at least one of the women.
Proposition 2: \( \exists y \in M, \forall x \in H: P(x, y) \)
“There exists a woman in \( M \) who is a sister of all the men in \( H \).” → At least one woman is a sister of all the men.
Clearly, Proposition 2 is far more restrictive than Proposition 1 — they’re not the same at all.
When the Order Does NOT Matter
When both quantifiers are the same, the order does not matter:
- \( \forall x, \forall y: P(x,y) \equiv \forall y, \forall x: P(x,y) \)
- \( \exists x, \exists y: P(x,y) \equiv \exists y, \exists x: P(x,y) \)
The order only matters when \( \forall \) and \( \exists \) are mixed.
Example with Finite Sets Verified Step by Step
Let \( A = {0, 1, 2} \). Determine the truth value of:
\( \forall x \in A, \forall y \in A: y^2 \leq 4(x + 1) \)
Let’s check every possible pair:
| \( x \) | \( y \) | \( y^2 \) | \( 4(x+1) \) | \( y^2 \leq 4(x+1) \) |
|---|---|---|---|---|
| 0 | 0 | 0 | 4 | ✓ |
| 0 | 1 | 1 | 4 | ✓ |
| 0 | 2 | 4 | 4 | ✓ |
| 1 | 0 | 0 | 8 | ✓ |
| 1 | 1 | 1 | 8 | ✓ |
| 1 | 2 | 4 | 8 | ✓ |
| 2 | 0 | 0 | 12 | ✓ |
| 2 | 1 | 1 | 12 | ✓ |
| 2 | 2 | 4 | 12 | ✓ |
All satisfy the condition → True ✅
What Happens If We Don’t Quantify All Variables?
An important detail: if a propositional function has \( n \) variables and we apply a quantifier to only one of them, we do not get a proposition, but rather a propositional function with \( n – 1 \) variables. Only when we quantify all variables do we obtain a proposition.
Let’s trace this step by step with \( P(x, y, z) \): “\( x + y + z = 1 \)”:
- \( P(x, y, z) \) → Propositional function with 3 variables (not a proposition)
- \( \forall x: x + y + z = 1 \) → Propositional function with 2 variables: \( y \), \( z \) (still not a proposition)
- \( \exists y, \forall x: x + y + z = 1 \) → Propositional function with 1 variable: \( z \) (still not a proposition)
- \( \forall z, \exists y, \forall x: x + y + z = 1 \) → Proposition (no free variables remain)
Negation with Multiple Quantifiers
To negate a proposition with multiple quantifiers, we apply the same rule as before from left to right: each quantifier switches (\( \forall \leftrightarrow \exists \)) and the property at the end gets negated.
General Rule
\[ \neg[\forall x, \exists y: P(x, y)] \equiv \exists x, \forall y: \neg P(x, y) \]
\[ \neg[\exists x, \forall y: P(x, y)] \equiv \forall x, \exists y: \neg P(x, y) \]
Worked Examples
The following examples involve some logical equivalence properties that we studied previously.
Example 1: Negate \( (\forall x)(\exists y)[P(x) \rightarrow (Q(y) \rightarrow R(x))] \)
Step 1 — Switch the quantifiers: \[ (\exists x)(\forall y) \neg [P(x) \rightarrow (Q(y) \rightarrow R(x))] \]
Step 2 — Negate the outer conditional (\( \neg(p \rightarrow q) \equiv p \land \neg q \)): \[ (\exists x)(\forall y)[P(x) \land \neg(Q(y) \rightarrow R(x))] \]
Step 3 — Negate the inner conditional: \[ (\exists x)(\forall y)[P(x) \land Q(y) \land \neg R(x)] \]
Example 2: Negate \( (\forall x)(\exists y)(\exists z)[P(x, y) \rightarrow Q(x) \land R(z)] \)
Step 1 — Switch the quantifiers: \[ (\exists x)(\forall y)(\forall z) \neg [P(x, y) \rightarrow Q(x) \land R(z)] \]
Step 2 — Negate the conditional: \[ (\exists x)(\forall y)(\forall z)[P(x, y) \land \neg(Q(x) \land R(z))] \]
Step 3 — Apply De Morgan’s law to the interior: \[ (\exists x)(\forall y)(\forall z)[P(x, y) \land (\neg Q(x) \lor \neg R(z))] \]
Example 3: Negate \( \forall x \in A, \exists y \in B: E(x) \rightarrow F(y) \)
\[ \neg[\forall x \in A, \exists y \in B: E(x) \rightarrow F(y)] \equiv \exists x \in A, \forall y \in B: E(x) \land \neg F(y) \]
Steps to Negate Any Quantified Proposition
- Switch each quantifier: \( \forall \leftrightarrow \exists \)
- Negate the propositional function at the end
- If the function contains connectives, apply the known negation rules:
- \( \neg(p \rightarrow q) \equiv p \land \neg q \)
- \( \neg(p \land q) \equiv \neg p \lor \neg q \) (De Morgan)
- \( \neg(p \lor q) \equiv \neg p \land \neg q \) (De Morgan)
Applications of Quantifiers
Quantifiers aren’t just abstract theory — they show up directly in several real-world fields.
1. Formal Definitions in Mathematics
The famous definition of the limit of a function uses quantifiers:
\[ \lim_{x \to x_0} f(x) = L \iff \forall \varepsilon > 0, \exists \delta > 0: |x – x_0| < \delta \implies |f(x) – L| < \varepsilon \]
This definition says: “For every margin of error \( \varepsilon \) (no matter how small), there exists a distance \( \delta \) such that if \( x \) is within \( \delta \) of \( x_0 \), then \( f(x) \) is within \( \varepsilon \) of \( L \).”
2. Set Theory
Quantifiers are essential for defining and proving properties of sets:
| Concept | Formal definition |
|---|---|
| Subset | \( A \subseteq B \iff \forall x(x \in A \rightarrow x \in B) \) |
| Equality | \( A = B \iff \forall x(x \in A \leftrightarrow x \in B) \) |
| Empty intersection | \( A \cap B = \emptyset \iff \neg \exists x(x \in A \land x \in B) \) |
| Empty set | \( A = \emptyset \iff \forall x(x \notin A) \) |
3. Programming and Databases
In SQL (a language for querying databases), quantifiers appear directly as keywords:
Existential quantifier (∃) → EXISTS
SELECT * FROM students
WHERE EXISTS (SELECT 1 FROM grades WHERE grades.id = students.id AND grade > 90);
What does this do? It finds every student who has at least one grade above 90. The EXISTS keyword plays exactly the role of \( \exists \): the query returns a student whenever at least one matching record exists in the grades table.
Universal quantifier (∀) → NOT EXISTS ... NOT IN
SELECT * FROM students
WHERE NOT EXISTS (SELECT 1 FROM courses WHERE courses.id NOT IN
(SELECT course_id FROM enrollments WHERE enrollments.student_id = students.id));
What does this do? It finds every student who is enrolled in all courses. Interestingly, SQL has no direct keyword for “for all” (\( \forall \)), so we express it through double negation: “there is no course in which the student is not enrolled” — which, by De Morgan’s theorems, is equivalent to “enrolled in every course” — exactly \( \forall x: P(x) \equiv \neg \exists x: \neg P(x) \).
4. Artificial Intelligence
In artificial intelligence, expert systems are programs designed to make decisions the way a human specialist would in a specific domain — for example, diagnosing diseases or approving bank loans. To work, these programs store knowledge rules, expressed using logic and quantifiers.
The component that evaluates those rules and draws conclusions is called an inference engine — think of it as an automated version of the rules of inference we’ve studied (Modus Ponens, syllogisms, etc.).
For example, a medical expert system might have rules like:
- \( \forall x: \text{Human}(x) \rightarrow \text{Mortal}(x) \) → “Every human is mortal”
- \( \forall x: \text{Fever}(x) \land \text{Cough}(x) \rightarrow \text{PossibleFlu}(x) \) → “Any patient with fever and a cough may have the flu”
- \( \exists x: \text{Robot}(x) \land \text{Intelligent}(x) \) → “There exists an intelligent robot”
When the system receives data about a specific patient, the inference engine fires these rules automatically to reach a diagnosis — using exactly the same quantifier logic we’ve been studying.
Practice Exercises
Section A: Determine the Truth Value
Let \( A = {0, 1, 2, 3} \) and \( B = {4, 2, 0, -2} \). Determine whether each proposition is true or false:
- \( \forall x \in A, \forall y \in B: 2x + y = 4 \)
- \( \forall x \in A, \exists y \in B: (x – 1)^2 > y \)
- \( \exists y \in B: \forall x \in A, (x – 1)^2 > y \)
- \( \exists x \in A: x^2 = x \)
- \( \forall x \in A: x^2 \geq x \)
Section B: Negate the Following Propositions
- \( \forall x \in \mathbb{N}: x + 2 < 5 \)
- \( \exists x \in \mathbb{R}: x^2 = -1 \)
- \( \forall x \in A, \exists y \in B: (x – 1)^2 > y \)
- \( \exists y \in B: \forall x \in A, (x – 1)^2 > y \)
- \( (\forall x)(\exists y)[P(x) \rightarrow Q(y)] \)
Section C: Translate to Symbolic Language
Express the following statements using quantifiers:
- “All even numbers are divisible by 2.”
- “There exists a real number whose square equals 2.”
- “Not all triangles are equilateral.”
- “No natural number is negative.”
Answers
Section A Answers
- False. If \( x = 0 \), we need \( y = 4 \) for all \( y \in B \), but \( 2(0) + 2 = 2 \neq 4 \). It does not hold for every \( y \).
- True. For each \( x \), we verify that some \( y \) works:
- \( x = 0 \): \( (0-1)^2 = 1 > y \) → with \( y = -2 \) ✓
- \( x = 1 \): \( (1-1)^2 = 0 > y \) → with \( y = -2 \) ✓
- \( x = 2 \): \( (2-1)^2 = 1 > y \) → with \( y = -2 \) ✓
- \( x = 3 \): \( (3-1)^2 = 4 > y \) → with \( y = -2 \) ✓
- True. It suffices for a single \( y \) to work for all \( x \). With \( y = -2 \): \( (x-1)^2 > -2 \) is true for every \( x \) (because a square is always \( \geq 0 > -2 \)).
- True. \( x = 0 \): \( 0^2 = 0 \) ✓, and also \( x = 1 \): \( 1^2 = 1 \) ✓.
- True. For every \( x \in {0,1,2,3} \):
- \( 0^2 = 0 \geq 0 \) ✓
- \( 1^2 = 1 \geq 1 \) ✓
- \( 2^2 = 4 \geq 2 \) ✓
- \( 3^2 = 9 \geq 3 \) ✓
Section B Answers
- \( \neg[\forall x \in \mathbb{N}: x + 2 < 5] \equiv \exists x \in \mathbb{N}: x + 2 \geq 5 \)
- \( \neg[\exists x \in \mathbb{R}: x^2 = -1] \equiv \forall x \in \mathbb{R}: x^2 \neq -1 \)
- \( \neg[\forall x \in A, \exists y \in B: (x-1)^2 > y] \equiv \exists x \in A, \forall y \in B: (x-1)^2 \leq y \)
- \( \neg[\exists y \in B: \forall x \in A, (x-1)^2 > y] \equiv \forall y \in B, \exists x \in A: (x-1)^2 \leq y \)
- \( \neg[(\forall x)(\exists y)(P(x) \rightarrow Q(y))] \equiv (\exists x)(\forall y)(P(x) \land \neg Q(y)) \)
Section C Answers
- Let \( E \) = the set of even numbers: \( \forall x \in E: 2 \mid x \) (or: \( \forall x: \text{even}(x) \rightarrow 2 \mid x \))
- \( \exists x \in \mathbb{R}: x^2 = 2 \)
- \( \neg[\forall x: \text{triangle}(x) \rightarrow \text{equilateral}(x)] \equiv \exists x: \text{triangle}(x) \land \neg\text{equilateral}(x) \)
- \( \forall x \in \mathbb{N}: x \geq 0 \) (or: \( \neg\exists x \in \mathbb{N}: x < 0 \))
Summary
Key Concepts
| Concept | Definition |
|---|---|
| Propositional function | An expression with variables that becomes a proposition once values are substituted in. Example: \( P(x): x > 5 \) |
| Universal quantifier \( \forall \) | “For all.” \( \forall x: P(x) \) is T if all satisfy \( P(x) \) |
| Existential quantifier \( \exists \) | “There exists at least one.” \( \exists x: P(x) \) is T if some satisfy \( P(x) \) |
| Uniqueness quantifier \( \exists! \) | “There exists exactly one.” \( \exists! x: P(x) \) is T if there is a unique \( x \) |
Negation of Quantifiers
| Original | Negation |
|---|---|
| \( \forall x: P(x) \) | \( \exists x: \neg P(x) \) |
| \( \exists x: P(x) \) | \( \forall x: \neg P(x) \) |
Order of Quantifiers
- \( \forall x, \forall y \) = \( \forall y, \forall x \) → order does not matter
- \( \exists x, \exists y \) = \( \exists y, \exists x \) → order does not matter
- \( \forall x, \exists y \) ≠ \( \exists y, \forall x \) → order DOES matter
What Comes Next?
Now that you’ve learned logical quantifiers, we have all the tools we need for the next topic: Set Theory. In that series, you’ll learn how to formally define sets, prove properties like inclusion and equality, and work with operations such as union, intersection, and difference — all built on the same logic and quantifier foundations you’ve just mastered.
Found this article helpful? Drop a comment with your questions or suggestions! And don’t forget to check out the next installment of this series on mathematical logic.