Ch 3. Logic and Proofs
3.4 Quantifiers
A predicate (or propositional function) is a statement that contains a variable and becomes a proposition when the variable is given a specific value. The set of all possible values a variable can take is called its domain of discourse.
Example 3.15
Let [latex]P(x)[/latex] be the predicate “[latex]x[/latex] is a registered user.”
If the domain is all users of a website, then [latex]P(\text{Aiden})[/latex] is a proposition that is either true or false, depending on whether Aiden is registered.
A universally quantified statement asserts that a predicate is true for all elements in the domain. It is written as [latex]\forall x P(x)[/latex], meaning “for all [latex]x[/latex], [latex]P(x)[/latex] is true.”
The statement is false if [latex]P(x)[/latex] is false for at least one element in the domain.
Example 3.16
Programming Example 3.5 (Pseudocode)
IF ALL users ARE IN accepted_terms THEN
DISPLAY "All users have accepted the terms."
ELSE
DISPLAY "Not all users have accepted the terms."
A free variable is a variable not bound by a quantifier and does not form a complete proposition. A bound variable is quantified and forms a proposition.
Example 3.17
[latex]P(x)[/latex]: “[latex]x[/latex] is online” [latex]\rightarrow[/latex] [latex]x[/latex] is free
[latex]\forall x P(x)[/latex]: “All users are online” [latex]\rightarrow[/latex] [latex]x[/latex] is bound
An existentially quantified statement asserts that there is at least one element in the domain for which the predicate is true. It is written as [latex]\exists x P(x)[/latex], meaning “there exists an [latex]x[/latex] such that [latex]P(x)[/latex] is true.”
The statement is false if [latex]P(x)[/latex] is false for every element in the domain.
Example 3.18
Let [latex]P(x)[/latex] be “[latex]x[/latex] has admin privileges.”
Then [latex]\exists x P(x)[/latex] means “There is at least one user with admin privileges.”
Programming Example 3.6 (Pseudocode)
IF ANY user IS IN admins THEN
DISPLAY "At least one user has admin privileges."
ELSE
DISPLAY "No user has admin privileges."
Theorem 3.2: Generalized De Morgan’s Laws
The Generalized De Morgan’s Laws extend De Morgan’s Laws (Equations (3.1) and (3.2)) to quantified statements:
- [latex]\neg \forall x P(x) \equiv \exists x \neg P(x)[/latex]
- [latex]\neg \exists x P(x) \equiv \forall x \neg P(x)[/latex]
Proof
a) Suppose that [latex]\neg \forall x P(x)[/latex] is true. Then [latex]\forall x P(x)[/latex] is false. By the definition of a universal quantifier, [latex]\forall x P(x)[/latex] is false if there exists at least one element [latex]x[/latex] in the domain such that [latex]P(x)[/latex] is false. That means [latex]\neg P(x)[/latex] is true for at least one [latex]x[/latex]. Therefore, [latex]\neg \exists x P(x)[/latex] is true.
Conversely, suppose that [latex]\neg \exists x P(x)[/latex] is true. Then there exists at least one [latex]x[/latex] such that [latex]\neg P(x)[/latex] is true, i.e., [latex]P(x)[/latex] is false. Therefore, [latex]P(x)[/latex] is not true for all [latex]x[/latex], so [latex]\forall x P(x)[/latex] is false. Hence, [latex]\neg \forall x P(x)[/latex] is true.
Thus, [latex]\neg \forall x P(x) \equiv \exists x \neg P(x)[/latex].
[latex]\square[/latex]
b) Suppose [latex]\neg \exists x P(x)[/latex] is true. Then [latex]\exists x P(x)[/latex] is false. By the definition of an existential quantifier, [latex]\exists x P(x)[/latex] is false if [latex]P(x)[/latex] is false for all [latex]x[/latex]. That means, [latex]\neg P(x)[/latex] is true for all [latex]x[/latex]. Therefore, [latex]\forall x \neg P(x)[/latex] is true.
Conversely, suppose that [latex]\forall x \neg P(x)[/latex] is true. Then for every [latex]x[/latex], [latex]\neg P(x)[/latex] is true, i.e., [latex]P(x)[/latex] is false for all [latex]x[/latex]. Therefore, [latex]\exists x P(x)[/latex] is false, and [latex]\neg \exists x P(x)[/latex] is true.
Thus, [latex]\neg \exists x P(x) \equiv \forall x \neg P(x)[/latex].
[latex]\square[/latex]
Example 3.19
Let [latex]P(x)[/latex] be the predicate: “User [latex]x[/latex] has verified their email address.” Let the domain be all users of an online platform.
Using Theorem 3.2(a),
[latex]\neg \forall x P(x)[/latex]: “It is not true that all users have verified their email.”
[latex]\exists x \neg P(x)[/latex]: “There exists at least one user who has not verified their email.”
These two statements are logically equivalent. If not all users have verified their email, then at least one user hasn’t, and vice versa.
Using Theorem 3.2(b),
[latex]\neg \exists x P(x)[/latex]: “There does not exist a user who has verified their email.”
[latex]\forall x \neg P(x)[/latex]: “All users have not verified their email.”
Again, these are logically equivalent. If no user has verified their email, then no user has verified it.
Rules of Inference for Quantified Statements
| Rule Name | Form | Description |
|---|---|---|
| Universal Instantiation | [latex]\forall x P(x) \Rightarrow P(d)[/latex] | If [latex]P[/latex] is true for all [latex]x[/latex], then it is true for any specific [latex]d[/latex] |
| Universal Generalization | [latex]P(d)[/latex] for arbitrary [latex]d \Rightarrow \forall x P(x)[/latex] | If [latex]P[/latex] is true for any arbitrary [latex]d[/latex], then it is true for all [latex]x[/latex] |
| Existential Instantiation | [latex]\exists x P(x) \Rightarrow P(d)[/latex] | If there exists an [latex]x[/latex] such that [latex]P(x)[/latex], then [latex]P[/latex] is true for some specific [latex]d[/latex] |
| Existential Generalization | [latex]P(d) \Rightarrow \exists x P(x)[/latex] | If [latex]P[/latex] is true for some specific [latex]d[/latex], then there exists an [latex]x[/latex] such that [latex]P(x)[/latex] |
Example 3.20
Suppose [latex]\forall x[/latex] ([latex]x[/latex] is a user [latex]\rightarrow x[/latex] has a password). Then, if Aiden is a user, we can conclude Aiden has a password (Universal Instantiation).
Nested quantifiers involve more than one quantifier in a statement. The order of quantifiers matters and can change the meaning of the statement.
| Form | Meaning |
|---|---|
| [latex]\forall x \forall y P(x, y)[/latex] | For all [latex]x[/latex] and for all [latex]y[/latex], [latex]P(x, y)[/latex] is true |
| [latex]\exists x \exists y P(x, y)[/latex] | There exists an [latex]x[/latex] and a [latex]y[/latex] such that [latex]P(x, y)[/latex] is true |
| [latex]\forall x \exists y P(x, y)[/latex] | For every [latex]x[/latex], there exists a [latex]y[/latex] such that [latex]P(x, y)[/latex] is true |
| [latex]\exists x \forall y P(x, y)[/latex] | There exists an [latex]x[/latex] such that for all [latex]y[/latex], [latex]P(x, y)[/latex] is true |
Example 3.21
Consider the statement: “Every user can message every other user.”
This statement, [latex]\forall x \forall y P(x, y)[/latex], can be interpreted as, for all users [latex]x[/latex] and all users [latex]y[/latex], user [latex]x[/latex] can send a message to user [latex]y[/latex]. This includes the possibility of messaging oneself unless explicitly excluded.
A scenario where this occurs is in a company using an internal messaging system. The system is configured so that every employee can message every other employee.
Now, consider the statement: “There exists at least one user who can message at least one other user.”
This statement, [latex]\exists x \exists y P(x, y)[/latex], can be interpreted as there is some user [latex]x[/latex] and some user [latex]y[/latex] such that [latex]x[/latex] can message [latex]y[/latex].
A scenario where this occurs is a restricted system in which only managers can message others. We want to check if at least one user has messaging privileges.
Now, consider the statement: “Every user can message at least one other user.”
This statement, [latex]\forall x \exists y P(x, y)[/latex], can be interpreted as for each user [latex]x[/latex], there exists one user [latex]y[/latex] such that [latex]x[/latex] can message [latex]y[/latex].
A scenario where this occurs is in a team chat app where each user must be able to message at least one teammate (not necessarily everyone).
Finally, consider the statement: “There exists a user who can message every other user.”
This statement, [latex]\exists x \forall y P(x, y)[/latex], can be interpreted as there is some user [latex]x[/latex] such that for all users [latex]y[/latex], [latex]x[/latex] can message [latex]y[/latex].
A scenario where this occurs is in a support system where we want to check if there is a super-admin who can message everyone.
Programming Example 3.7 (Pseudocode)
Consider the statement: “Every user can message every other user.”
SET all_can_message_all TO TRUE
FOR EACH user_x IN users:
FOR EACH user_y IN users:
IF NOT can_message(user_x, user_y) THEN
SET all_can_message_all TO FALSE
DISPLAY all_can_message_all
Now, consider the statement: “There exists at least one user who can message at least one other user.”
SET exists_pair TO FALSE
FOR EACH user_x IN users:
FOR EACH user_y IN users:
IF can_message(user_x, user_y) THEN
SET exists_pair TO TRUE
DISPLAY exists_pair
Now, consider the statement: “Every user can message at least one other user.”
SET each_can_message_someone TO TRUE
FOR EACH user_x IN users:
SET can_message_someone TO FALSE
FOR EACH user_y IN users:
IF user_x ≠ user_y AND can_message(user_x, user_y) THEN
SET can_message_someone TO TRUE
IF NOT can_message_someone THEN
SET each_can_message_someone TO FALSE
DISPLAY each_can_message_someone
Finally, consider the statement: “There exists a user who can message every other user.”
SET exists_super_sender TO FALSE
FOR EACH user_x IN users:
SET can_message_all TO TRUE
FOR EACH user_y IN users:
IF user_x ≠ user_y AND NOT can_message(user_x, user_y) THEN
SET can_message_all TO FALSE
IF can_message_all THEN
SET exists_super_sender TO TRUE
DISPLAY exists_super_sender
Real-World Example 3.4: Multiplayer Game Logic
Suppose you are playing Mario Kart 8 Deluxe on Nintendo Switch. Consider the following rules:
- In local multiplayer, any player profile can join any race: [latex]\forall x \forall y P(x, y)[/latex]
- At least one player can join at least one race: [latex]\exists x \exists y P(x, y)[/latex]
- Every player can join at least one race: [latex]\forall x \exists y P(x, y)[/latex]
- A player who owns the game and has Nintendo Switch Online can join every available race: [latex]\exists x \forall y P(x, y)[/latex]
These logical structures help Mario Kart have open matchmaking with minimal restrictions and demonstrate a maximally permissive system, close to universal access, which is a feature Nintendo strives to achieve with its video games.
