This document presents a collection of Logical Quantifiers exercises with practical and pedagogical solutions designed to reinforce and consolidate the theoretical skills acquired during the study of this fundamental branch of mathematics and philosophy.
The exercises developed here complement the theoretical content covered in the following reference document:
Logical Quantifiers: A Complete Guide — Propositional functions, universal quantifier (∀), existential quantifier (∃), uniqueness quantifier (∃!), negation of quantifiers, and multiple quantifiers.
Objective
This collection is designed to give you systematic practice in:
- Evaluating the truth value of quantified propositions
- Identifying counterexamples to refute universal propositions
- Formalizing verbal statements into expressions with quantifiers and predicates
- Correctly negating simple and compound quantified propositions
- Distinguishing between propositions and propositional functions
- Analyzing propositions with multiple quantifiers and the effect of their order
- Integrating all concepts in higher-complexity exercises
Document Structure
The exercises are organized into several sections and increase in difficulty as the user progresses through each exercise, The document includes a theoretical reference summary at the beginning that condenses the key concepts needed to solve the exercises.
Theoretical Summary
Quantifiers extend propositional logic to analyze arguments involving “all” or “some” — situations that simple propositional variables (\( p \), \( q \), \( r \)) cannot capture.
Propositional function (open statement)
A propositional function is an expression with one or more variables that becomes a proposition (true or false) when the variables are replaced by concrete values from a domain.
Example: \( P(x) \): “\( x + 5 < 11 \)” with \( x \in \mathbb{Z} \)
- If \( x = 3 \): \( P(3) \): “\( 8 < 11 \)” → True ✓
- If \( x = 7 \): \( P(7) \): “\( 12 < 11 \)” → False ✗
Universal quantifier (∀)
Asserts that all elements in the domain satisfy a property.
\[ \forall x \in A: P(x) \]
Read as: “For all \( x \) belonging to \( A \), \( P(x) \) holds.”
Key: Finding just one element that does not satisfy the property is enough to make the statement false.
Existential quantifier (∃)
Asserts that at least one element satisfies the property.
\[ \exists x \in A: P(x) \]
Read as: “There exists at least one \( x \) in \( A \) such that \( P(x) \) holds.”
Key: Finding just one element that satisfies the property is enough to make the statement true.
Uniqueness quantifier (∃!)
Asserts that exactly one element satisfies the property.
\[ \exists! x \in A: P(x) \]
Example: \( \exists! x \in \mathbb{Z}: 2 < x < 4 \) → Only \( x = 3 \) satisfies the condition. True ✓
Relationship between ∀ and ∃
| If… | Then… |
|---|---|
| \( \forall x: P(x) \) is true | \( \exists x: P(x) \) is also true |
| \( \exists x: P(x) \) is false | \( \forall x: P(x) \) is also false |
💡 If everyone satisfies the property, then at least one satisfies it. And if no one satisfies it, then not everyone satisfies it. (The converse does not always hold.)
Negation of quantifiers
| Original | Negation |
|---|---|
| \( \forall x: P(x) \) | \( \exists x: \neg P(x) \) |
| \( \exists x: P(x) \) | \( \forall x: \neg P(x) \) |
In words:
- “It is not true that all satisfy \( P \)” ≡ “There exists at least one that does not satisfy \( P \)”
- “It is not true that there exists one satisfying \( P \)” ≡ “None satisfy \( P \)”
Negation with connectives: When negating quantified propositions that contain connectives, follow two steps in order:
- First switch each quantifier (\( \forall \leftrightarrow \exists \))
- Then negate the final predicate, applying the known laws:
- \( \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)
Multiple quantifiers
When a propositional function has two or more variables, a quantifier is applied to each:
\[ \forall x, \exists y: P(x, y) \]
Fundamental rule — Order matters:
| Combination | Does order matter? |
|---|---|
| \( \forall x, \forall y \) = \( \forall y, \forall x \) | No |
| \( \exists x, \exists y \) = \( \exists y, \exists x \) | No |
| \( \forall x, \exists y \) ≠ \( \exists y, \forall x \) | Yes ⚠️ (when mixing \( \forall \) with \( \exists \)) |
Negation with multiple quantifiers: Switch each quantifier (\( \forall \leftrightarrow \exists \)) from left to right and negate the predicate at the end:
\[ \neg[\forall x, \exists y: P(x, y)] \equiv \exists x, \forall y: \neg P(x, y) \]
Section 1: Truth value with ∀ and ∃
Exercise 1.
If \( p(x) \) denotes the statement “\( x + 2 > 5 \)”, determine whether \( p(x) \) is or is not a logical function over each of the following sets:
(1) \( \mathbb{N} \), the set of natural numbers
(2) \( M = {-1, -2, -3, \ldots} \)
(3) \( \mathbb{C} \), the set of complex numbers
Solution:
💡 Recall: An expression is a logical function over a set if, by substituting the variable with any element of the set, we obtain a proposition (true or false). If the substitution does not produce T or F, it is not a logical function over that set.
(1) Yes. Substituting any \( x \in \mathbb{N} \) yields a proposition:
- \( x = 1 \): \( 1 + 2 > 5 \) → \( 3 > 5 \) is False ✗
- \( x = 4 \): \( 4 + 2 > 5 \) → \( 6 > 5 \) is True ✓
A truth value is always obtained → it is a logical function over \( \mathbb{N} \).
(2) Yes. Although \( p(x) \) is false for every element of \( M \) (for example: \( x = -1 \): \( -1 + 2 = 1 \not> 5 \)), this does not matter. What matters is that each substitution does produce a truth value (False). A logical function can always be false and still be a logical function.
(3) No. If \( x = 2i \), the expression \( 2i + 2 > 5 \) makes no sense because the inequality \( > \) is not defined between complex numbers. The substitution produces neither T nor F → it is not a logical function over \( \mathbb{C} \).
Exercise 2.
Determine the truth value of each of the following statements where \( x \in \mathbb{R} \)
(1) \( \forall x, |x| = x \)
(2) \( \exists x, x^2 = x \)
(3) \( \forall x, x + 1 > x \)
(4) \( \exists x, x + 2 = x \)
(5) \( \exists x, |x| = 0 \)
Solution:
💡 Strategy: To disprove a \( \forall \), one counterexample is all you need. To prove a \( \exists \), one witness — a single value that works — is enough.
(1) False. Counterexample: \( x = -3 \) → \( |-3| = 3 \neq -3 \). With a single negative value, the \( \forall \) statement is already false.
(2) True. Witness: \( x = 1 \) → \( 1^2 = 1 \) ✓. Also works with \( x = 0 \): \( 0^2 = 0 \). One is enough.
(3) True. Simplifying: \( x + 1 > x \iff 1 > 0 \), which is always true regardless of the value of \( x \).
(4) False. The equation \( x + 2 = x \) reduces to \( 2 = 0 \), which is a contradiction. No real \( x \) satisfies it.
(5) True. Witness: \( x = 0 \) → \( |0| = 0 \) ✓. Moreover, it is the only value that satisfies it (\( \exists! \)).
Exercise 3.
Given \( A = {1, 2, 3, 4, 5} \), find the truth value of the following statements.
(1) \( (\exists x \in A)(x + 3 = 10) \)
(2) \( (\forall x \in A)(x + 3 < 10) \)
(3) \( (\exists x \in A)(x + 3 < 5) \)
(4) \( (\forall x \in A)(x + 3 = 7) \)
Solution:
💡 Since \( A \) is finite, we can check each element directly. For \( \exists \), you just need one that works; for \( \forall \), every element must satisfy it.
(1) False. We need \( x + 3 = 10 \), i.e., \( x = 7 \). But \( 7 \notin A \) → no element of \( A \) satisfies the equation.
(2) True. Check: \( 1+3=4 \), \( 2+3=5 \), \( 3+3=6 \), \( 4+3=7 \), \( 5+3=8 \). All are \( < 10 \) ✓
(3) True. We need \( x + 3 < 5 \), i.e., \( x < 2 \). With \( x = 1 \): \( 1 + 3 = 4 < 5 \) ✓. That one value is all we need.
(4) False. We need \( x + 3 = 7 \) for every \( x \), i.e., \( x = 4 \) for all. Counterexample: \( x = 5 \) → \( 5 + 3 = 8 \neq 7 \).
Exercise 4.
Determine the truth value where \( x \in \mathbb{R} \)
(1) \( \forall x, x^2 = x \)
(2) \( \exists x, 2x = x \)
(3) \( \exists x, x^3 + 3x – 2 = 0 \)
(4) \( \forall x, x – 3 < x \)
(5) \( \exists x, x^2 + 2x + 3 = 0 \)
(6) \( \forall x, 2x + 3x = 5x \)
Solution:
(1) False. Counterexample: if \( x = 2 \), then \( 2^2 = 4 \neq 2 \).
(2) True. If \( x = 0 \), then \( 2(0) = 0 \) ✓
(3) True. Evaluate \( f(x) = x^3 + 3x – 2 \): \( f(0) = -2 < 0 \) and \( f(1) = 1 + 3 – 2 = 2 > 0 \). Since \( f \) is continuous and changes sign, by the Intermediate Value Theorem there exists at least one \( x \in (0, 1) \) such that \( f(x) = 0 \).
📘 Note — Intermediate Value Theorem: If a continuous function goes from a negative value to a positive one, its graph must cross zero at some point in between. Think of it as: you cannot go from below to above without crossing the ground.
(4) True. Simplifying: \( x – 3 < x \iff -3 < 0 \), which is always true for all \( x \in \mathbb{R} \).
(5) False. Completing the square: \( x^2 + 2x + 3 = (x+1)^2 + 2 \). Since \( (x+1)^2 \geq 0 \), then \( (x+1)^2 + 2 \geq 2 > 0 \) for all \( x \in \mathbb{R} \). The equation is never satisfied.
(6) True. By the distributive property: \( 2x + 3x = (2+3)x = 5x \) for all \( x \in \mathbb{R} \).
Exercise 5.
Let \( {1, 2, 3, 4} \) be the universal set. Determine the truth value:
(1) \( \forall x, x + 3 < 6 \)
(2) \( \exists x, x + 3 < 6 \)
(3) \( \forall x, x^4 – 10 = 8 \)
(4) \( \exists x, 2x^4 + x = 15 \)
Solution:
(1) False. Test each \( x \):
- \( x = 1 \): \( 4 < 6 \) ✓
- \( x = 2 \): \( 5 < 6 \) ✓
- \( x = 3 \): \( 6 < 6 \) ✗ — fails here
(2) True. With \( x = 1 \): \( 1 + 3 = 4 < 6 \) ✓. That’s enough.
(3) False. We need \( x^4 = 18 \) for every \( x \):
- \( x = 1 \): \( 1^4 – 10 = -9 \neq 8 \) ✗ — already fails
(4) False. Test each \( x \):
- \( x = 1 \): \( 2(1) + 1 = 3 \neq 15 \)
- \( x = 2 \): \( 2(16) + 2 = 34 \neq 15 \)
- \( x = 3 \): \( 2(81) + 3 = 165 \neq 15 \)
- \( x = 4 \): \( 2(256) + 4 = 516 \neq 15 \)
No \( x \) satisfies the equation.
Section 2: Counterexamples
Exercise 6.
Find a counterexample for each of the following statements. Here \( B = {2, 3, \ldots, 8, 9} \).
(1) \( \forall x \in B, x + 5 < 12 \)
(2) \( \forall x \in B, x \) is prime
(3) \( \forall x \in B, x^2 > 1 \)
(4) \( \forall x \in B, x \) is even
Solution:
A counterexample is a value that shows a \( \forall \) statement is false. Finding just one element that does not satisfy the property is enough:
(1) If \( x_0 = 7 \), 8, or 9, then \( x_0 + 5 < 12 \) is not true; any of 7, 8, or 9 serves as a counterexample.
(2) Since 4 is not prime, 4 is a counterexample.
(3) The statement is true; so there is no counterexample.
(4) Since 3 is odd, 3 is a counterexample.
Exercise 7.
Give a counterexample for each false statement. Here \( {3, 5, 7, 9} \) is the universal set.
(1) \( \forall x, x + 3 \geq 7 \)
(2) \( \forall x, x \) is odd
(3) \( \forall x, x \) is prime
(4) \( \forall x, |x| = x \)
Solution:
(1) False. Counterexample: \( x = 3 \) → \( 3 + 3 = 6 \not\geq 7 \)
(2) True. All elements of \( {3, 5, 7, 9} \) are odd. No counterexample.
(3) False. Counterexample: \( x = 9 \) → \( 9 = 3 \times 3 \), not prime.
(4) True. All elements are positive, so \( |x| = x \) for all \( x \in {3, 5, 7, 9} \). No counterexample.
Section 3: Formalization with predicates and quantifiers
Exercise 8.
Represent in predicate calculus: “Some are friends of Luis”
Solution:
Step 1 — Identify the quantifier: The key word is “some”, indicating that at least one satisfies the property. This corresponds to the existential quantifier \( \exists \).
Step 2 — Define predicates and constants:
- \( l \): Luis (constant, a specific individual)
- \( A(x, y) \): “\( x \) is a friend of \( y \)”
Step 3 — Build the formula:
\( \exists x , A(x, l) \)
Verification (reverse reading): “There exists at least one \( x \) such that \( x \) is a friend of Luis” ✓ — matches the original statement.
Exercise 9.
Represent in predicate calculus: “Everyone is a sibling”
Solution:
Step 1 — Identify the quantifier: The key word is “everyone”, indicating the property holds for each one. This corresponds to the universal quantifier \( \forall \).
Step 2 — Analyze the relation: “Everyone is a sibling” implies that each individual is a sibling of every other individual. Since the relation involves two participants (\( x \) is a sibling of \( y \)), we need two universal quantifiers.
Step 3 — Define predicates:
- \( H(x, y) \): “\( x \) is a sibling of \( y \)”
Step 4 — Build the formula:
\( \forall x , \forall y , H(x, y) \)
Verification (reverse reading): “For all \( x \) and for all \( y \), \( x \) is a sibling of \( y \)” ✓
💡 Note: This formula includes the case \( x = y \), which would mean “\( x \) is a sibling of themselves”. To exclude that case, write: \( \forall x , \forall y , (x \neq y \rightarrow H(x, y)) \)
Exercise 10.
Represent in predicate calculus:
a) “Some fish are yellow”
b) “All fish are yellow”
Solution:
Predicates:
- \( P(x) \): “\( x \) is a fish”
- \( A(x) \): “\( x \) is yellow”
a) “Some fish are yellow” → We want individuals that are both fish and yellow.
Formula: \( \exists x (P(x) \land A(x)) \)
b) “All fish are yellow” → If an individual is a fish, then it is yellow.
Formula: \( \forall x (P(x) \rightarrow A(x)) \)
⚠️ Common mistake: A student might write \( \forall x (P(x) \land A(x)) \), but this would say “every individual in the universe is a fish and yellow” — including people, objects, etc. The correct approach is to use the conditional (→) because we only care about what happens with individuals that are already fish.
💡 Practical rule:
- With ∃ (existential) → use ∧ (conjunction): “there exists something that is A and B”
- With ∀ (universal) → use → (conditional): “for all x, if it is A then it is B”
Exercise 11.
Represent in predicate calculus: “Some sailors only date girls who are fans of Julio Iglesias”
Solution:
Step 1 — Identify the structure: The sentence has two parts:
- “Some sailors…” → \( \exists x \) with the property of being a sailor
- “…only date girls who are fans of Julio Iglesias” → restriction over all their partners
Step 2 — Interpret “only”: The word “only” indicates an exclusive restriction. If a sailor \( x \) dates someone \( y \), then \( y \) must be a fan of Julio Iglesias. This translates as a conditional: \( N(x, y) \rightarrow JI(y) \)
Step 3 — Define predicates:
- \( M(x) \): “\( x \) is a sailor”
- \( N(x, y) \): “\( x \) dates \( y \)”
- \( JI(y) \): “\( y \) is a fan of Julio Iglesias”
Step 4 — Build the formula:
\( \exists x [M(x) \land \forall y (N(x, y) \rightarrow JI(y))] \)
Verification (reverse reading): “There exists at least one \( x \) who is a sailor and for every person \( y \), if \( x \) dates \( y \), then \( y \) is a fan of Julio Iglesias” ✓
Exercise 12.
Represent in predicate calculus: “Only Spanish people are won over by Computer Science girls”
Solution:
Step 1 — Interpret “only”: The word “only” restricts who can do something. “Only Spanish people…” means: if someone is won over, they are necessarily Spanish. The conditional goes in this direction:
\( \text{is won over} \rightarrow \text{is Spanish} \)
⚠️ Caution: A common mistake is to write \( E(x) \rightarrow C(x, y) \) (“if Spanish, then won over”), but that would say that all Spanish people are won over, which is not what the statement says.
Step 2 — Identify the quantifiers: The sentence talks about every individual \( x \) and every girl \( y \), so we use \( \forall x , \forall y \).
Step 3 — Define predicates:
- \( E(x) \): “\( x \) is Spanish”
- \( C(x, y) \): “\( x \) is won over by \( y \)”
- \( I(y) \): “\( y \) is a Computer Science girl”
Step 4 — Build the formula:
\( \forall x , \forall y (C(x, y) \land I(y) \rightarrow E(x)) \)
Verification (reverse reading): “For all \( x \) and all \( y \), if \( x \) is won over by \( y \) and \( y \) is a Computer Science girl, then \( x \) is Spanish” ✓
Section 4: Negation of quantifiers
Exercise 13.
Negate the following statements.
(1) \( \forall x, |x| = x \)
(2) \( \exists x, x^2 = x \)
(3) \( \forall x, x + 1 > x \)
(4) \( \exists x, x + 2 = x \)
(5) \( \exists x, |x| = 0 \)
Solution:
Recall the rule: \( \sim\forall \equiv \exists\sim \) and \( \sim\exists \equiv \forall\sim \). Switch the quantifier and negate the predicate:
(1) \( \sim\forall x, |x| = x \equiv \exists x \sim(|x| = x) \equiv \exists x, |x| \neq x \)
(2) \( \sim\exists x, x^2 = x \equiv \forall x \sim(x^2 = x) \equiv \forall x, x^2 \neq x \)
(3) \( \sim\forall x, x + 1 > x \equiv \exists x \sim(x + 1 > x) \equiv \exists x, x + 1 \leq x \)
(4) \( \sim\exists x, x + 2 = x \equiv \forall x \sim(x + 2 = x) \equiv \forall x, x + 2 \neq x \)
(5) \( \sim\exists x, |x| = 0 \equiv \forall x \sim(|x| = 0) \equiv \forall x, |x| \neq 0 \)
Exercise 14.
Negate the following statements.
(1) \( (\exists x \in A)(x + 3 = 10) \)
(2) \( (\forall x \in A)(x + 3 < 10) \)
(3) \( (\exists x \in A)(x + 3 < 5) \)
(4) \( (\forall x \in A)(x + 3 = 7) \)
Solution:
Same rule as the previous exercise, but keeping the domain \( A \) in each quantifier:
(1) \( \sim(\exists x \in A)(x + 3 = 10) \equiv (\forall x \in A) \sim(x + 3 = 10) \equiv (\forall x \in A)(x + 3 \neq 10) \)
(2) \( \sim(\forall x \in A)(x + 3 < 10) \equiv (\exists x \in A) \sim(x + 3 < 10) \equiv (\exists x \in A)(x + 3 \geq 10) \)
(3) \( \sim(\exists x \in A)(x + 3 < 5) \equiv (\forall x \in A) \sim(x + 3 < 5) \equiv (\forall x \in A)(x + 3 \geq 5) \)
(4) \( \sim(\forall x \in A)(x + 3 = 7) \equiv (\exists x \in A) \sim(x + 3 = 7) \equiv (\exists x \in A)(x + 3 > 7) \)
Exercise 15.
Negate the statements from Exercise 4.
Solution:
Switch the quantifier and negate the predicate:
(1) \( \sim(\forall x, x^2 = x) \equiv \exists x, x^2 \neq x \)
(2) \( \sim(\exists x, 2x = x) \equiv \forall x, 2x \neq x \)
(3) \( \sim(\exists x, x^3 + 3x – 2 = 0) \equiv \forall x, x^3 + 3x – 2 \neq 0 \)
(4) \( \sim(\forall x, x – 3 < x) \equiv \exists x, x – 3 \geq x \)
(5) \( \sim(\exists x, x^2 + 2x + 3 = 0) \equiv \forall x, x^2 + 2x + 3 \neq 0 \)
(6) \( \sim(\forall x, 2x + 3x = 5x) \equiv \exists x, 2x + 3x \neq 5x \)
Exercise 16.
Negate the statements:
(1) \( \forall x , p(x) \land \exists y , q(y) \)
(2) \( \exists x , p(x) \lor \forall y , q(y) \)
Solution:
💡 Two-step process: (1) Apply De Morgan to the main connective (∧ or ∨), (2) negate each quantifier separately.
(1) The main connective is \( \land \). Apply \( \sim(p \land q) \equiv \sim p \lor \sim q \); then negate each quantifier:
\( \sim(\forall x , p(x) \land \exists y , q(y)) \equiv \sim\forall x , p(x) \lor \sim\exists y , q(y) \equiv \exists x \sim p(x) \lor \forall y \sim q(y) \)
(2) The main connective is \( \lor \). Apply \( \sim(p \lor q) \equiv \sim p \land \sim q \); then negate each quantifier:
\( \sim(\exists x , p(x) \lor \forall y , q(y)) \equiv \sim\exists x , p(x) \land \sim\forall y , q(y) \equiv \forall x \sim p(x) \land \exists y \sim q(y) \)
Section 5: Sentential negation
Exercise 17.
Negate the following statements.
(1) If there is a mutiny, someone is dead.
(2) It is daytime and everyone has gotten up.
Solution:
💡 Strategy — Sentential negation: These statements mix logical connectives (→, ∧) with words that hide quantifiers (“someone” = ∃, “everyone” = ∀). To negate them correctly, two things must be done: (1) apply the negation law of the main connective and (2) negate the hidden quantifiers in natural language.
(1) “If there is a mutiny, someone is dead.”
Step 1 — Identify the structure:
- \( p \): “There is a mutiny” (simple proposition)
- \( q \): “Someone is dead” (hides a \( \exists x: \text{Dead}(x) \))
- Main connective: conditional → Structure: \( p \rightarrow q \)
Step 2 — Negate the main connective:
\( \sim(p \rightarrow q) \equiv p \land \sim q \)
Step 3 — Negate the hidden quantifier in \( q \):
\( \sim q \) = “It is not true that someone is dead” = “Everyone is alive” (The \( \exists \) becomes \( \forall \) and “dead” is negated to “alive”)
Negation: “There is a mutiny and everyone is alive”
⚠️ Common mistake: A student might negate as: “If there is no mutiny, no one is dead.” This is incorrect because negating a conditional does not mean negating each part separately — the negation of \( p \rightarrow q \) is \( p \land \sim q \), not \( \sim p \rightarrow \sim q \).
(2) “It is daytime and everyone has gotten up.”
Step 1 — Identify the structure:
- \( p \): “It is daytime” (simple proposition)
- \( q \): “Everyone has gotten up” (hides a \( \forall x: \text{Up}(x) \))
- Main connective: conjunction → Structure: \( p \land q \)
Step 2 — Negate the main connective (De Morgan):
\( \sim(p \land q) \equiv \sim p \lor \sim q \)
Step 3 — Negate each part:
- \( \sim p \) = “It is not daytime” = “It is nighttime”
- \( \sim q \) = “It is not true that everyone has gotten up” = “Someone has not gotten up” (The \( \forall \) becomes \( \exists \) when negated)
Negation: “It is nighttime or someone has not gotten up”
Quick verification: Does the negation make sense? The original statement asserts two things at once (daytime + everyone up). Its negation must be true when at least one of those things fails — and that is exactly what the negation with “or” says. ✓
Exercise 18.
Negate the following statements:
(1) If the teacher is absent, some students do not finish their homework.
(2) All students finished their homework and the teacher is present.
(3) Some students did not finish their homework or the teacher is absent.
Solution:
💡 Notice: All three statements use the same propositions but different connectives (→, ∧, ∨) — perfect for seeing how the negation changes depending on which connective is in charge. We’ll use the same variables throughout:
- \( p \): “The teacher is absent”
- \( T(x) \): “Student \( x \) finished their homework”
(1) “If the teacher is absent, some students do not finish their homework.”
Step 1 — Identify the structure:
- Main connective: conditional (→)
- \( q \): “Some students do not finish their homework” = \( \exists x: \sim T(x) \)
- Structure: \( p \rightarrow q \)
Step 2 — Negate: \( \sim(p \rightarrow q) \equiv p \land \sim q \)
Step 3 — Interpret \( \sim q \): \( \sim q \) = “It is not true that some don’t finish” = “All students finish their homework” (\( \sim\exists x: \sim T(x) \equiv \forall x: T(x) \) — double negation: ∃ becomes ∀ and ¬T is cancelled)
Negation: “The teacher is absent and all students finish their homework”
(2) “All students finished their homework and the teacher is present.”
Step 1 — Identify the structure:
- Main connective: conjunction (∧)
- \( r \): “All students finished their homework” = \( \forall x: T(x) \)
- \( \sim p \): “The teacher is present” (opposite of “absent”)
- Structure: \( r \land \sim p \)
Step 2 — Negate (De Morgan): \( \sim(r \land \sim p) \equiv \sim r \lor p \)
Step 3 — Interpret:
- \( \sim r \) = “Some students did not finish their homework” (\( \forall \to \exists \) when negating)
- \( p \) = “The teacher is absent”
Negation: “Some students did not finish their homework or the teacher is absent”
(3) “Some students did not finish their homework or the teacher is absent.”
Step 1 — Identify the structure:
- Main connective: disjunction (∨)
- \( s \): “Some students did not finish their homework” = \( \exists x: \sim T(x) \)
- Structure: \( s \lor p \)
Step 2 — Negate (De Morgan): \( \sim(s \lor p) \equiv \sim s \land \sim p \)
Step 3 — Interpret:
- \( \sim s \) = “All students finished their homework” (\( \exists \to \forall \) when negating)
- \( \sim p \) = “The teacher is present”
Negation: “All students finished their homework and the teacher is present”
💡 Did you notice? The negation of (2) is exactly statement (3), and the negation of (3) is exactly statement (2). They are mutual negations! This makes sense: De Morgan tells us that \( \sim(p \land q) \equiv \sim p \lor \sim q \), so negating twice returns to the original.
Section 6: Statement vs. propositional function
Exercise 19.
Let \( A = {1, 2, \ldots, 9, 10} \). For each of the following formal expressions, state whether it is a statement or a propositional function; if it is a statement, indicate whether it is true or false; if it is a propositional function, determine its truth set.
(1) \( (\forall x \in A)(\exists y \in A)(x + y < 14) \)
(2) \( (\forall y \in A)(x + y < 14) \)
(3) \( (\forall x \in A)(\forall y \in A)(x + y < 14) \)
(4) \( (\exists y \in A)(x + y < 14) \)
Solution:
💡 Key rule: If all variables are quantified → it’s a statement (true or false). If some variable is free (no quantifier) → it’s a propositional function, and we find its truth set (TS).
Let’s classify each one first:
| Item | \( x \) | \( y \) | Type? |
|---|---|---|---|
| (1) | ∀ (bound) | ∃ (bound) | Statement |
| (2) | free | ∀ (bound) | Propositional function in \( x \) |
| (3) | ∀ (bound) | ∀ (bound) | Statement |
| (4) | free | ∃ (bound) | Propositional function in \( x \) |
(1) \( (\forall x \in A)(\exists y \in A)(x + y < 14) \) → Statement.
It is true: for each \( x \in A \), just pick \( y = 1 \) and \( x + 1 \leq 11 < 14 \) holds for all \( x \leq 10 \). ✓
(2) \( (\forall y \in A)(x + y < 14) \) → Propositional function in \( x \).
For \( x_0 + y < 14 \) to be true for every \( y \in A \), the most demanding case is the largest \( y \): we need \( x_0 + 10 < 14 \), i.e., \( x_0 < 4 \).
- \( x = 1 \): \( 1 + 10 = 11 < 14 \) ✓
- \( x = 3 \): \( 3 + 10 = 13 < 14 \) ✓
- \( x = 4 \): \( 4 + 10 = 14 \not< 14 \) ✗ — fails here
TS = \( {1, 2, 3} \)
(3) \( (\forall x \in A)(\forall y \in A)(x + y < 14) \) → Statement.
It is false. Counterexample: \( x = 8, y = 9 \) → \( 17 \not< 14 \). ✗
(4) \( (\exists y \in A)(x + y < 14) \) → Propositional function in \( x \).
For each \( x_0 \), just one \( y \) needs to work. Using \( y = 1 \):
- \( x_0 + 1 \leq 11 < 14 \) for all \( x_0 \in A \) ✓
TS = \( A \) (the complete set)
💡 Comparison: Notice how (1) and (4) use ∃ for \( y \) — both “pass easily” because we can pick \( y = 1 \). In contrast, (2) and (3) use ∀ for \( y \) — and the extreme case \( y = 10 \) makes them restrictive. The quantifier ∀ is always more demanding than ∃.
Exercise 20.
Let \( {1, 2, 3, 4, 5} \) be the universal set. Find the truth set:
(1) \( \exists x, 2x + y < 7 \)
(2) \( \exists y, 2x + y < 7 \)
(3) \( \forall x, 2x + y < 10 \)
(4) \( \forall y, 2x + y < 10 \)
Solution:
💡 Only the quantified variable is “bound”; the other stays free, making each expression a propositional function with a truth set (TS) to find. The approach depends on the quantifier:
- ∃ (existential): just try the best candidate (the smallest value, which minimizes the expression)
- ∀ (universal): it must work even with the worst case (the largest value, which maximizes the expression)
(1) \( \exists x, 2x + y < 7 \) — free variable: \( y \).
For each \( y \), we just need one \( x \) that works. Best candidate: \( x = 1 \) (minimizes \( 2x \)):
\( 2(1) + y < 7 \implies y < 5 \)
- \( y = 1 \): \( 2+1=3 < 7 \) ✓
- \( y = 4 \): \( 2+4=6 < 7 \) ✓
- \( y = 5 \): \( 2+5=7 \not< 7 \) ✗ (and with \( x = 2, 3, \ldots \) it’s worse)
TS = \( {1, 2, 3, 4} \)
(2) \( \exists y, 2x + y < 7 \) — free variable: \( x \).
For each \( x \), we just need one \( y \) that works. Best candidate: \( y = 1 \) (minimizes \( y \)):
\( 2x + 1 < 7 \implies x < 3 \)
- \( x = 1 \): \( 2+1=3 < 7 \) ✓
- \( x = 2 \): \( 4+1=5 < 7 \) ✓
- \( x = 3 \): \( 6+1=7 \not< 7 \) ✗ (and with \( y = 2, 3, \ldots \) it’s worse)
TS = \( {1, 2} \)
(3) \( \forall x, 2x + y < 10 \) — free variable: \( y \).
Must hold for every \( x \). Worst case: \( x = 5 \) (maximizes \( 2x \)):
\( 2(5) + y < 10 \implies y < 0 \)
No \( y \in {1, 2, 3, 4, 5} \) satisfies \( y < 0 \).
TS = \( \varnothing \) (empty)
(4) \( \forall y, 2x + y < 10 \) — free variable: \( x \).
Must hold for every \( y \). Worst case: \( y = 5 \) (maximizes \( y \)):
\( 2x + 5 < 10 \implies x < 2.5 \)
- \( x = 1 \): \( 2+5=7 < 10 \) ✓
- \( x = 2 \): \( 4+5=9 < 10 \) ✓
- \( x = 3 \): \( 6+5=11 \not< 10 \) ✗
TS = \( {1, 2} \)
💡 Comparative summary:
Item Quantifier Strategy TS (1) ∃ over \( x \) Best candidate: \( x=1 \) \( {1,2,3,4} \) (2) ∃ over \( y \) Best candidate: \( y=1 \) \( {1,2} \) (3) ∀ over \( x \) Worst case: \( x=5 \) \( \varnothing \) (4) ∀ over \( y \) Worst case: \( y=5 \) \( {1,2} \) Note how ∀ produces smaller (or empty) truth sets than ∃, because it is more demanding.
Section 7: Multiple quantifiers
Exercise 21.
Let \( {1, 2, 3} \) be the universal set. Find the truth value of the following statements.
(1) \( \exists x , \forall y, x^2 < y + 1 \)
(2) \( \forall x , \exists y, x^2 + y^2 < 12 \)
(3) \( \forall x , \forall y, x^2 + y^2 < 12 \)
(4) \( \exists x , \forall y , \exists z, x^2 + y^2 < 2z^2 \)
(5) \( \exists x , \exists y , \forall z, x^2 + y^2 < 2z^2 \)
Solution:
💡 Strategy — Multiple quantifiers: Read from left to right. Each quantifier sets a task:
- ∃: “find one value that works” (fix that value and continue)
- ∀: “verify it works for all values”
The key is that a ∃ can depend on quantifiers to its left, but a ∀ must hold regardless.
(1) \( \exists x , \forall y, x^2 < y + 1 \)
In plain English: “Is there some \( x \) such that \( x^2 < y + 1 \) for every \( y \)?”
True. Try \( x = 1 \): we need \( 1 < y + 1 \), i.e., \( 0 < y \), for all \( y \):
- \( y = 1 \): \( 0 < 1 \) ✓
- \( y = 2 \): \( 0 < 2 \) ✓
- \( y = 3 \): \( 0 < 3 \) ✓
One \( x \) that works for all \( y \) is all we need. ✓
(2) \( \forall x , \exists y, x^2 + y^2 < 12 \)
In plain English: “For every \( x \), is there some \( y \) such that \( x^2 + y^2 < 12 \)?”
True. For each \( x \), we just need at least one \( y \) (best candidate: \( y = 1 \)):
- \( x = 1 \): \( 1 + 1 = 2 < 12 \) ✓
- \( x = 2 \): \( 4 + 1 = 5 < 12 \) ✓
- \( x = 3 \): \( 9 + 1 = 10 < 12 \) ✓
(3) \( \forall x , \forall y, x^2 + y^2 < 12 \)
In plain English: “For every \( x \) and every \( y \), is \( x^2 + y^2 < 12 \) always true?”
False. Counterexample: \( x = 2, y = 3 \) → \( 4 + 9 = 13 \not< 12 \) ✗
💡 Compare (2) and (3): the same expression \( x^2 + y^2 < 12 \) goes from true to false simply by changing ∃y to ∀y. In (2) we can choose a favorable \( y \); in (3) it must hold for all.
(4) \( \exists x , \forall y , \exists z, x^2 + y^2 < 2z^2 \)
In plain English: “Is there an \( x \) such that, for every \( y \), there exists a \( z \) satisfying \( x^2 + y^2 < 2z^2 \)?”
True. Fix \( x = 1 \): for each \( y \), we need a \( z \) such that \( 1 + y^2 < 2z^2 \):
- \( y = 1 \): \( 1 + 1 = 2 \). With \( z = 2 \): \( 2 < 8 \) ✓
- \( y = 2 \): \( 1 + 4 = 5 \). With \( z = 2 \): \( 5 < 8 \) ✓
- \( y = 3 \): \( 1 + 9 = 10 \). With \( z = 3 \): \( 10 < 18 \) ✓
Note: the chosen \( z \) can change for each \( y \) (because ∃z is to the right of ∀y).
(5) \( \exists x , \exists y , \forall z, x^2 + y^2 < 2z^2 \)
In plain English: “Can we find fixed \( x \) and \( y \) such that \( x^2 + y^2 < 2z^2 \) holds for every \( z \)?”
False. The pair minimizing \( x^2 + y^2 \) is \( (1, 1) \) → \( 2 \). But with \( z = 1 \): \( 2 < 2(1) = 2 \) is false (not strictly less). No pair \( (x, y) \) survives the worst case \( z = 1 \).
⚠️ Compare (4) and (5): Both have the same quantifiers (∃x, ∃/∀y, ∃/∀z) and the same expression, but swap the quantifiers of \( y \) and \( z \). In (4), \( z \) is chosen after knowing \( y \) (can adapt). In (5), \( x \) and \( y \) are fixed before facing all \( z \) (cannot adapt). Result: (4) is T and (5) is F.
Exercise 22.
Let \( {1, 2, 3} \) be the universal set. Determine the truth value:
(1) \( \forall x , \forall y, x^2 + 2y < 10 \)
(2) \( \exists x , \forall y, x^2 + 2y < 10 \)
(3) \( \forall x , \exists y, x^2 + 2y < 10 \)
(4) \( \exists x , \exists y, x^2 + 2y < 10 \)
Solution:
💡 Trick — Use a table: With small finite sets, we can compute all possible values and then “read” the quantifiers directly from the table:
- ∀x ∀y → Does the entire table hold?
- ∃x ∀y → Is there any complete row that holds?
- ∀x ∃y → Does each row have at least one cell that holds?
- ∃x ∃y → Is there at least one cell that holds?
Compute \( x^2 + 2y \) for all combinations:
| \( y=1 \) | \( y=2 \) | \( y=3 \) | Full row < 10? | |
|---|---|---|---|---|
| \( x=1 \) | 3 ✓ | 5 ✓ | 7 ✓ | ✅ Yes |
| \( x=2 \) | 8 ✓ | 8 ✓ | 10 ✗ | ❌ No |
| \( x=3 \) | 11 ✗ | 13 ✗ | 15 ✗ | ❌ No |
(1) ∀x ∀y → False. The entire table must be < 10. The cell \( (2, 3) = 10 \not< 10 \) already fails. ✗
(2) ∃x ∀y → True. A complete row < 10 is needed. With \( x = 1 \): the row is 3, 5, 7 — all < 10. ✓
(3) ∀x ∃y → False. Each row needs at least one value < 10. With \( x = 3 \): the row is 11, 13, 15 — none < 10. ✗
(4) ∃x ∃y → True. At least one cell < 10 is needed. With \( x = 1, y = 1 \): 3 < 10. ✓
💡 Hierarchy of restrictiveness: From most to least demanding:
\( \forall\forall \) (entire table) > \( \exists\forall \) (full row) > \( \forall\exists \) (one per row) > \( \exists\exists \) (one cell)
In this example: ∀∀ = F, ∃∀ = T, ∀∃ = F, ∃∃ = T. Note that ∃∀ → T implies ∃∃ is also T (if an entire row holds, at least one cell holds).
Exercise 23.
Determine the truth value of:
\( p : \forall x \in \mathbb{Q}, \exists y \in \mathbb{Q}, x + y = 0 \) \( q : \exists y \in \mathbb{Q}, \forall x \in \mathbb{Q}, x + y = 0 \)
Solution:
💡 These two propositions share the same expression (\( x + y = 0 \)) and the same quantifiers (∀ and ∃), just in different order. This is the go-to example for showing that order matters.
Proposition \( p \): \( \forall x \in \mathbb{Q}, \exists y \in \mathbb{Q}, x + y = 0 \)
In plain English: “For every rational \( x \), is there some rational \( y \) such that \( x + y = 0 \)?”
The key is that \( y \) can depend on \( x \) (because ∃y is to the right of ∀x). For each \( x \), simply choose \( y = -x \):
- \( x = 2 \) → \( y = -2 \): \( 2 + (-2) = 0 \) ✓
- \( x = -\frac{3}{5} \) → \( y = \frac{3}{5} \): \( -\frac{3}{5} + \frac{3}{5} = 0 \) ✓
- For any \( x \in \mathbb{Q} \), its opposite \( -x \) is also rational ✓
\( p \) is True. ✓
Proposition \( q \): \( \exists y \in \mathbb{Q}, \forall x \in \mathbb{Q}, x + y = 0 \)
In plain English: “Is there some fixed rational \( y \) that works for all \( x \) simultaneously?”
Here \( y \) is chosen first (before knowing \( x \)), so it must be a fixed value. But any fixed \( y \) only cancels \( x = -y \):
- If \( y = \frac{1}{2} \): works with \( x = -\frac{1}{2} \), but fails with \( x = 3 \): \( 3 + \frac{1}{2} \neq 0 \) ✗
- If \( y = -5 \): works with \( x = 5 \), but fails with \( x = 1 \): \( 1 + (-5) \neq 0 \) ✗
No fixed \( y \) can satisfy all \( x \) simultaneously.
\( q \) is False. ✗
💡 The essential difference: In \( p \), \( y \) is chosen after knowing \( x \), so it can adapt (\( y = -x \)). In \( q \), \( y \) is fixed before, so it must work for all \( x \) at once — impossible. This is the clearest example of why \( \forall x , \exists y \neq \exists y , \forall x \).
Exercise 24.
Given the sets: \( A = {x \in \mathbb{N} / 2x \leq 13} \) \( B = {x \in A / (x^2 – 2x) \notin A} \)
Determine whether each of the following propositions is true or false: \( p : \forall x \in (A-B), \exists y \in B / x^2 – 2x \geq y – 3 \)
\( q : \exists x \in B, \exists y \in (A-B), \forall z \in B : (x + y^2 + z) \in A \)
\( r : \forall x \in (A-B) : x^2 \notin A \)
Solution:
💡 Start here: Before evaluating the propositions, build the sets \( A \), \( B \), and \( A – B \) first. You can’t do anything without them.
Step 1 — Build \( A \):
\( A = {x \in \mathbb{N} / 2x \leq 13} \) → \( x \leq 6.5 \), and since \( x \in \mathbb{N} \): \( A = {0, 1, 2, 3, 4, 5, 6} \)
Step 2 — Build \( B \): For each \( x \in A \), compute \( x^2 – 2x \) and check whether it does not belong to \( A \):
| \( x \) | \( x^2 – 2x \) | \( \in A \)? | \( \in B \)? |
|---|---|---|---|
| 0 | 0 | Yes | No |
| 1 | -1 | No | Yes |
| 2 | 0 | Yes | No |
| 3 | 3 | Yes | No |
| 4 | 8 | No | Yes |
| 5 | 15 | No | Yes |
| 6 | 24 | No | Yes |
\( B = {1, 4, 5, 6} \) and \( A – B = {0, 2, 3} \)
Step 3 — Evaluate \( p \): \( \forall x \in (A-B), \exists y \in B / x^2 – 2x \geq y – 3 \)
For each \( x \in {0, 2, 3} \), does at least one \( y \in B \) satisfy the condition?
| \( x \) | \( x^2 – 2x \) | We need \( \exists y \in B \) with \( y – 3 \leq … \) | Satisfied? |
|---|---|---|---|
| 0 | 0 | \( 0 \geq y – 3 \) → \( y \leq 3 \). With \( y = 1 \): ✓ | ✓ |
| 2 | 0 | \( 0 \geq y – 3 \) → \( y \leq 3 \). With \( y = 1 \): ✓ | ✓ |
| 3 | 3 | \( 3 \geq y – 3 \) → \( y \leq 6 \). With \( y = 4 \): ✓ | ✓ |
All \( x \) find a witness → \( p \) is True. ✓
Step 4 — Evaluate \( q \): \( \exists x \in B, \exists y \in (A-B), \forall z \in B : (x + y^2 + z) \in A \)
We need a pair \( (x, y) \) such that \( x + y^2 + z \in A = {0, …, 6} \) for every \( z \in B \).
The worst case is \( z = 6 \) (the largest in \( B \)):
\( x + y^2 + 6 \leq 6 \implies x + y^2 \leq 0 \)
But \( x \in B \implies x \geq 1 \) and \( y^2 \geq 0 \), so \( x + y^2 \geq 1 > 0 \). No pair \( (x, y) \) can satisfy the condition.
\( q \) is False. ✗
Step 5 — Evaluate \( r \): \( \forall x \in (A-B) : x^2 \notin A \)
| \( x \) | \( x^2 \) | \( \notin A \)? |
|---|---|---|
| 0 | 0 | False (\( 0 \in A \)) ✗ |
| 2 | 4 | False (\( 4 \in A \)) ✗ |
| 3 | 9 | True (\( 9 \notin A \)) ✓ |
With even one \( x \) failing, the ∀ is false. It already fails at \( x = 0 \).
\( r \) is False. ✗
Exercise 25.
If \( A={1, 2, 3, 4, 5} \) and \( B={-2, -1, 0, 5, 6} \), determine the truth value of each proposition.
\( p : \forall x \in A, \exists y \in B : x + y < 3 \)
\( q : \exists! y \in B, \forall x \in A : x – y > 1 \)
\( r : \forall x \in B, \forall y \in A : x < y \Rightarrow x^2 < y^2 \)
\( s : \exists x \in A, \exists y \in B : (x – y) \in A \)
Solution:
💡 This exercise combines several quantifier types seen so far: ∀∃, ∃!, ∀∀ with conditional, and ∃∃. Each requires a different strategy.
Proposition \( p \): \( \forall x \in A, \exists y \in B : x + y < 3 \)
In plain English: “For every \( x \in A \), is there some \( y \in B \) such that \( x + y < 3 \)?”
For each \( x \), solve: \( y < 3 – x \). Best candidate in \( B \): \( y = -2 \):
| \( x \) | Need \( y < … \) | Does \( y = -2 \) work? |
|---|---|---|
| 1 | \( y < 2 \) | \( -2 < 2 \) ✓ |
| 2 | \( y < 1 \) | \( -2 < 1 \) ✓ |
| 3 | \( y < 0 \) | \( -2 < 0 \) ✓ |
| 4 | \( y < -1 \) | \( -2 < -1 \) ✓ |
| 5 | \( y < -2 \) | \( -2 \not< -2 \) ✗ |
Fails at \( x = 5 \): no \( y \in B \) satisfies \( y < -2 \).
\( p \) is False. ✗
Proposition \( q \): \( \exists! y \in B, \forall x \in A : x – y > 1 \)
In plain English: “Is there exactly one \( y \in B \) such that \( x – y > 1 \) holds for every \( x \in A \)?”
First find which values of \( y \) work for all \( x \). The most demanding case is \( x = 1 \) (the smallest in \( A \)): \( 1 – y > 1 \implies y < 0 \).
Elements of \( B \) with \( y < 0 \): \( y = -2 \) and \( y = -1 \). Verify both:
- \( y = -2 \): \( x – (-2) = x + 2 > 1 \) → always T (since \( x \geq 1 \)) ✓
- \( y = -1 \): \( x – (-1) = x + 1 > 1 \) → always T (since \( x \geq 1 \)) ✓
Both work, but ∃! requires exactly one. Since two values satisfy it, uniqueness fails.
\( q \) is False. ✗
Proposition \( r \): \( \forall x \in B, \forall y \in A : x < y \Rightarrow x^2 < y^2 \)
In plain English: “For every \( x \in B \) and every \( y \in A \), if \( x < y \) then \( x^2 < y^2 \)?”
All we need is one counterexample where \( x < y \) is T but \( x^2 < y^2 \) is F:
With \( x = -2 \in B \) and \( y = 1 \in A \):
- \( x < y \): \( -2 < 1 \) → T ✓
- \( x^2 < y^2 \): \( 4 < 1 \) → F ✗
- The conditional \( T \rightarrow F = F \)
💡 This happens because negative numbers squared become large positives. The implication \( x < y \Rightarrow x^2 < y^2 \) is only valid when both values are non-negative.
\( r \) is False. ✗
Proposition \( s \): \( \exists x \in A, \exists y \in B : (x – y) \in A \)
In plain English: “Are there \( x \in A \) and \( y \in B \) such that \( x – y \in A \)?”
Just find one pair that works:
With \( x = 1 \) and \( y = -2 \): \( 1 – (-2) = 3 \). Is \( 3 \in A \)? Yes ✓
\( s \) is True. ✓
Exercise 26.
Let \( U={0,1,2,3,4,5,6,7,8,9,10} \). Determine whether each of the following propositions is true or false:
\( p : \forall x \in U : \exists y \in U \land \exists z \in U \text{ such that } 2x – y + z < 10 \)
\( q : \exists x \in U \text{ such that: } \forall z \in U, \exists y \in U \text{ such that } 2x – y + z < 10 \)
Solution:
💡 Both propositions use the same expression \( 2x – y + z < 10 \), but with different quantifier structures:
- In \( p \): ∀x → ∃y, ∃z (for every \( x \), search for \( y \) and \( z \))
- In \( q \): ∃x → ∀z → ∃y (fix one \( x \), then for every \( z \), search for \( y \))
Proposition \( p \): \( \forall x \in U, \exists y \in U, \exists z \in U : 2x – y + z < 10 \)
In plain English: “For every \( x \in U \), are there \( y \) and \( z \) in \( U \) such that \( 2x – y + z < 10 \)?”
Since it is ∀x, we have to check even the worst case: \( x = 10 \):
\( 2(10) – y + z < 10 \implies z – y < -10 \implies z < y – 10 \)
Since \( y \leq 10 \), then \( y – 10 \leq 0 \), and since \( z \geq 0 \), there is no way \( z < y – 10 \leq 0 \).
- \( x = 0 \): \( -y + z < 10 \). With \( y = 0, z = 0 \): \( 0 < 10 \) ✓
- \( x = 10 \): \( 20 – y + z < 10 \). Needs \( z < y – 10 \). Impossible ✗
\( p \) is False. ✗
Proposition \( q \): \( \exists x \in U, \forall z \in U, \exists y \in U : 2x – y + z < 10 \)
In plain English: “Is there some \( x \in U \) such that, for every \( z \), there exists a \( y \) satisfying \( 2x – y + z < 10 \)?”
Try \( x = 0 \): the expression simplifies to \( -y + z < 10 \), i.e., \( y > z – 10 \).
For each \( z \), is there \( y \in U \) with \( y > z – 10 \)?
- \( z = 0 \): \( y > -10 \) → any \( y \in U \) works ✓
- \( z = 5 \): \( y > -5 \) → any \( y \in U \) works ✓
- \( z = 10 \): \( y > 0 \) → with \( y = 1 \): ✓
For every \( z \in U \), the condition \( y > z – 10 \) is easily satisfied (even \( y = 10 \) always works).
\( q \) is True. ✓
💡 Compare \( p \) and \( q \): In \( p \), ∀x forces us to verify \( x = 10 \), where \( 2x = 20 \) is already so large that \( y \) and \( z \) cannot compensate. In \( q \), ∃x lets us choose \( x = 0 \), minimizing \( 2x \), and then ∃y can adapt to each \( z \).
Exercise 27.
Let propositions \( p \), \( q \), and \( r \) be:
\( p : \forall y \in \mathbb{N}, \exists x \in \mathbb{N} : x > y \land x \text{ is even} \)
\( q : \exists x \in \mathbb{N} : \forall y \in \mathbb{N} : y < x \)
\( r : \forall x \in \mathbb{N}, \forall y \in \mathbb{N} : x + y > x \)
Determine and justify the truth value of each proposition.
Solution:
💡 This exercise works with \( \mathbb{N} = {0, 1, 2, 3, \ldots} \), an infinite set — we can’t check every value. Instead, we need to reason generally or find counterexamples.
Proposition \( p \): \( \forall y \in \mathbb{N}, \exists x \in \mathbb{N} : x > y \land x \text{ is even} \)
In plain English: “For every natural \( y \), is there some even natural \( x \) such that \( x > y \)?”
For any \( y \), simply choose \( x = 2\lceil\frac{y+1}{2}\rceil \) (the smallest even number greater than \( y \)):
- \( y = 0 \): \( x = 2 > 0 \) and 2 is even ✓
- \( y = 1 \): \( x = 2 > 1 \) and 2 is even ✓
- \( y = 2 \): \( x = 4 > 2 \) and 4 is even ✓
- \( y = 100 \): \( x = 102 > 100 \) and 102 is even ✓
Since there are infinitely many even numbers, given any \( y \) there will always be an even number greater than it.
\( p \) is True. ✓
Proposition \( q \): \( \exists x \in \mathbb{N} : \forall y \in \mathbb{N} : y < x \)
In plain English: “Is there some natural \( x \) that is greater than every other natural?”
That would mean there’s a “largest natural number.” But \( \mathbb{N} \) has no maximum: for any \( x \) you pick, \( y = x + 1 \) gives \( y \not< x \).
- If \( x = 100 \): \( y = 101 \) → \( 101 < 100 \) is F ✗
- If \( x = 10^6 \): \( y = 10^6 + 1 \) → F ✗
\( q \) is False. ✗
💡 Compare \( p \) and \( q \): in \( p \), \( x \) is chosen after knowing \( y \) (can adapt). In \( q \), \( x \) is fixed before (must be greater than all). Same principle as Exercise 23.
Proposition \( r \): \( \forall x \in \mathbb{N}, \forall y \in \mathbb{N} : x + y > x \)
In plain English: “For every natural \( x \) and every natural \( y \), is \( x + y > x \)?”
Simplifying: \( x + y > x \iff y > 0 \). This should hold for every \( y \in \mathbb{N} \), but \( 0 \in \mathbb{N} \):
Counterexample: \( y = 0 \) → \( 0 > 0 \) is false ✗ (with any \( x \))
\( r \) is False. ✗
💡 If the domain were \( \mathbb{N}^* = {1, 2, 3, \ldots} \) (without zero), proposition \( r \) would be true. The truth value can depend on how the domain is defined.
Section 8: Negation with connectives and multiple quantifiers
Exercise 28.
Negate the following statements.
(1) \( \exists x , \forall y, p(x, y) \)
(2) \( \forall x , \forall y, p(x, y) \)
(3) \( \exists y , \exists x , \forall z, p(x, y, z) \)
(4) \( \forall x , \exists y , (p(x) \lor q(y)) \)
(5) \( \exists x , \forall y , (p(x, y) \rightarrow q(x, y)) \)
(6) \( \exists y , \exists x , (p(x) \land \sim q(y)) \)
Solution:
💡 Two-step recipe:
- Switch each quantifier (\( \forall \leftrightarrow \exists \)) from left to right
- Negate the final predicate, applying if needed: \( \sim(p \lor q) \equiv \sim p \land \sim q \), \( \sim(p \land q) \equiv \sim p \lor \sim q \), \( \sim(p \rightarrow q) \equiv p \land \sim q \)
Items (1)-(3) only need step 1. Items (4)-(6) need both steps.
(1) \( \sim(\exists x , \forall y, p(x, y)) \)
Switch quantifiers: \( \forall x , \exists y \). Negate predicate: \( \sim p(x, y) \).
\( \equiv \forall x , \exists y , \sim p(x, y) \)
(2) \( \sim(\forall x , \forall y, p(x, y)) \)
\( \equiv \exists x , \exists y , \sim p(x, y) \)
(3) \( \sim(\exists y , \exists x , \forall z, p(x, y, z)) \)
\( \equiv \forall y , \forall x , \exists z , \sim p(x, y, z) \)
(4) \( \sim[\forall x , \exists y , (p(x) \lor q(y))] \)
Step 1 — Quantifiers: \( \exists x , \forall y \) Step 2 — Negate \( p(x) \lor q(y) \) with De Morgan:
\( \equiv \exists x , \forall y , (\sim p(x) \land \sim q(y)) \)
(5) \( \sim[\exists x , \forall y , (p(x, y) \rightarrow q(x, y))] \)
Step 1 — Quantifiers: \( \forall x , \exists y \) Step 2 — Negate the conditional: \( \sim(p \rightarrow q) \equiv p \land \sim q \)
\( \equiv \forall x , \exists y , (p(x, y) \land \sim q(x, y)) \)
(6) \( \sim[\exists y , \exists x , (p(x) \land \sim q(y))] \)
Step 1 — Quantifiers: \( \forall y , \forall x \) Step 2 — Negate \( p(x) \land \sim q(y) \) with De Morgan: \( \sim p(x) \lor \sim(\sim q(y)) = \sim p(x) \lor q(y) \)
\( \equiv \forall y , \forall x , (\sim p(x) \lor q(y)) \)
💡 Note: In (6) a double negation appears: \( \sim(\sim q(y)) = q(y) \). Whenever you negate something that is already negated, they cancel out.
Exercise 29.
Given the following statement, which is the definition of the sequence \( a_1, a_2, \ldots \) having limit zero:
\( \forall \varepsilon > 0 , \exists n_0 , \forall n , (n > n_0 \rightarrow |a_n| < \varepsilon) \)
Negate this statement.
💡 Why is negating a limit useful? In mathematics, to prove that a sequence does not converge to zero, we need to know exactly what “not having limit zero” means. That is precisely the negation of this definition.
Solution:
The original definition says: “For every error margin \( \varepsilon \), there exists a point \( n_0 \) from which all subsequent terms are within the margin.”
Negate step by step:
| Position | Original | Negation |
|---|---|---|
| 1st quantifier | \( \forall \varepsilon > 0 \) | \( \exists \varepsilon > 0 \) |
| 2nd quantifier | \( \exists n_0 \) | \( \forall n_0 \) |
| 3rd quantifier | \( \forall n \) | \( \exists n \) |
| Predicate | \( n > n_0 \rightarrow | a_n |
Step 1 — Switch the quantifiers:
\( \exists \varepsilon > 0 , \forall n_0 , \exists n \sim(n > n_0 \rightarrow |a_n| < \varepsilon) \)
Step 2 — Negate the conditional: \( \sim(p \rightarrow q) \equiv p \land \sim q \):
\( \equiv \exists \varepsilon > 0 , \forall n_0 , \exists n , (n > n_0 \land |a_n| \geq \varepsilon) \)
In words: “There exists an error margin \( \varepsilon \) such that, no matter how far we advance in the sequence (\( \forall n_0 \)), we will always find some term (\( \exists n \)) that strays from zero by at least \( \varepsilon \).”
💡 Analogy: Imagine trying to catch a fly (the sequence) inside a box of size \( \varepsilon \) centered at zero. The original definition says that for any box size, the fly eventually stays inside. The negation says there is a box size such that the fly always escapes, no matter how long you wait.
Exercise 30.
Find the truth values of the negations of the following propositions:
\( p = (\exists x \in \mathbb{N} \mid x + 2 = 5) \land (\forall x \in \mathbb{N} \mid x^2 > x) \)
\( q = (\forall x \in \mathbb{Z} \mid -x < 0) \lor (\exists x \in \mathbb{Z} \mid -x = x) \)
\( r = \exists x \in \mathbb{R} \mid \sqrt{-x} \in \mathbb{R} \)
Solution:
💡 Two-phase strategy: (1) Negate symbolically using De Morgan and quantifier rules, (2) evaluate the truth value of the resulting negation.
Negation of \( p \):
Step 1 — Negate (De Morgan over ∧):
\( \sim p = \sim(\exists x \in \mathbb{N} \mid x + 2 = 5) \lor \sim(\forall x \in \mathbb{N} \mid x^2 > x) \)
\( = [\forall x \in \mathbb{N} \mid x + 2 \neq 5] \lor [\exists x \in \mathbb{N} \mid x^2 \leq x] \)
Step 2 — Evaluate each part:
- \( \forall x \in \mathbb{N}: x + 2 \neq 5 \) → F (because \( x = 3 \) gives \( 3 + 2 = 5 \))
- \( \exists x \in \mathbb{N}: x^2 \leq x \) → T (with \( x = 0 \): \( 0 \leq 0 \), or \( x = 1 \): \( 1 \leq 1 \))
\( V(\sim p) = V(F \lor T) = T \) ✓
Negation of \( q \):
Step 1 — Negate (De Morgan over ∨):
\( \sim q = [\sim(\forall x \in \mathbb{Z} \mid -x < 0)] \land [\sim(\exists x \in \mathbb{Z} \mid -x = x)] \)
\( = (\exists x \in \mathbb{Z} \mid -x \geq 0) \land (\forall x \in \mathbb{Z} \mid -x \neq x) \)
Step 2 — Evaluate each part:
- \( \exists x \in \mathbb{Z}: -x \geq 0 \) → T (with \( x = -2 \): \( -(-2) = 2 \geq 0 \))
- \( \forall x \in \mathbb{Z}: -x \neq x \) → F (counterexample: \( x = 0 \) → \( -0 = 0 \), so \( -x = x \))
\( V(\sim q) = V(T \land F) = F \) ✗
Negation of \( r \):
Step 1 — Negate:
\( \sim r = \forall x \in \mathbb{R} \mid \sqrt{-x} \notin \mathbb{R} \)
Step 2 — Evaluate: Is it true that no real \( x \) has \( \sqrt{-x} \in \mathbb{R} \)?
Counterexample: \( x = -1 \) → \( \sqrt{-(-1)} = \sqrt{1} = 1 \in \mathbb{R} \) ✗
\( V(\sim r) = F \) ✗
💡 Summary:
Proposition \( V(\text{original}) \) \( V(\text{negation}) \) \( p \) F T \( q \) T F \( r \) T F As expected, negation always inverts the truth value.
Exercise 31.
Negate the proposition: “For every rational number \( r \) there exists an integer \( n \) such that \( n \leq r < n+1 \)”
Solution:
Step 1 — Symbolize:
\( p = \forall r \in \mathbb{Q}, \exists n \in \mathbb{Z} \mid n \leq r < n+1 \)
💡 The compound inequality \( n \leq r < n+1 \) is a hidden conjunction: \( n \leq r \land r < n+1 \). When negating, De Morgan must be applied.
Step 2 — Negate quantifiers:
\( \sim p = \exists r \in \mathbb{Q}, \forall n \in \mathbb{Z} \mid \sim(n \leq r \land r < n+1) \)
Step 3 — Negate the conjunction (De Morgan):
\( = \exists r \in \mathbb{Q}, \forall n \in \mathbb{Z} \mid (n > r) \lor (n+1 \leq r) \)
In words: “There exists a rational \( r \) such that no integer \( n \) manages to ‘trap it’ in the interval \( [n, n+1) \).”
💡 Is the negation true? No. The original proposition is true (it is the floor property: every rational falls in some interval \( [n, n+1) \)). Therefore, its negation is false.
Exercise 32.
Sententially negate the statement: “For every real number \( x \), there exists an integer \( M \) such that \( x^2 < M+1 \) whenever \( x < M \)”
Solution:
💡 The phrase “\( x^2 < M+1 \) whenever \( x < M \)” is a conditional: \( x < M \rightarrow x^2 < M+1 \).
Step 1 — Symbolize:
\( p = \forall x \in \mathbb{R}, \exists M \in \mathbb{Z} \mid x < M \rightarrow x^2 < M+1 \)
Step 2 — Negate quantifiers:
\( \sim p = \exists x \in \mathbb{R}, \forall M \in \mathbb{Z} \mid \sim(x < M \rightarrow x^2 < M+1) \)
Step 3 — Negate the conditional: \( \sim(p \rightarrow q) \equiv p \land \sim q \)
\( = \exists x \in \mathbb{R}, \forall M \in \mathbb{Z} \mid x < M \land x^2 \geq M+1 \)
In words: “There exists a real number \( x \) such that, for every integer \( M \), both \( x < M \) and \( x^2 \geq M+1 \) hold simultaneously.”
Exercise 33.
Symbolize using quantifiers and negate the quantified proposition: “For every number \( x \) belonging to the set of real numbers, there exists a unique number \( y \) belonging to the real numbers, such that the difference of \( x \) minus \( y \) is positive”
Solution:
💡 This exercise is special because it involves \( \exists! \) (uniqueness). To negate it, first expand the definition of ∃! and then negate normally.
Step 1 — Symbolize:
\( \forall x \in \mathbb{R}, \exists! y \in \mathbb{R} \mid x – y > 0 \)
Step 2 — Expand \( \exists! \): Saying “there exists a unique \( y \)” means two things simultaneously:
- There exists at least one \( y \) satisfying the property
- If there is another value \( z \) also satisfying it, then \( y = z \) (they are the same)
Formally: \( \exists! y: P(y) \equiv \exists y: P(y) \land [\forall z: P(z) \rightarrow z = y] \)
Applied to our case: \( \forall x \in \mathbb{R}, \exists y \in \mathbb{R}: (x – y > 0) \land [\forall z \in \mathbb{R}: (x – z > 0) \rightarrow z = y] \)
Step 3 — Negate: Switch quantifiers and negate the predicate:
\( \exists x \in \mathbb{R}, \forall y \in \mathbb{R}: \sim{(x – y > 0) \land [\forall z: (x – z > 0) \rightarrow z = y]} \)
Applying De Morgan: \( \equiv \exists x \in \mathbb{R}, \forall y \in \mathbb{R}: (x – y \leq 0) \lor [\exists z \in \mathbb{R}: (x – z > 0) \land z \neq y] \)
In words: “There exists a real \( x \) such that, for any \( y \), either \( x – y \) is not positive, or there is another \( z \neq y \) for which \( x – z \) is also positive” — that is, uniqueness fails.
💡 Is the negation true? Yes. The original proposition is false: for \( x = 5 \), both \( y = 1 \) and \( y = 2 \) satisfy \( x – y > 0 \) (\( 4 > 0 \) and \( 3 > 0 \)). There is no uniqueness. Therefore, the negation is true.
Section 9: Integrating exercises
Exercise 34.
Let \( A={1,2,3,4,5} \) and the propositions:
\( p = \exists x \in A \mid (x+2=6) \rightarrow (x-5=8) \)
\( q = \forall x \in A \mid (x+2>2) \lor (x+2<2) \)
\( r = \forall x \in A, \exists y \in A \mid x+y>2 \)
Find the truth value of: \( s = \sim[(p \rightarrow q) \land (q \lor \sim r)] \)
Solution:
💡 Strategy: First evaluate each quantified proposition (\( p \), \( q \), \( r \)) separately, then substitute into the formula for \( s \).
Evaluation of \( p \): \( \exists x \in A \mid (x+2=6) \rightarrow (x-5=8) \)
⚠️ Heads up: \( p \) is a ∃ with a conditional inside. All you need is one \( x \) that makes the conditional true. Remember that \( F \rightarrow \text{anything} = T \).
- With \( x = 1 \): \( (3 = 6) \rightarrow (-4 = 8) \) = \( F \rightarrow F = T \) ✓
\( x = 1 \) is enough → \( V(p) = T \)
💡 Note that with \( x = 4 \): \( (6 = 6) \rightarrow (-1 = 8) \) = \( T \rightarrow F = F \). But since \( p \) is ∃, one true case is enough.
Evaluation of \( q \): \( \forall x \in A \mid (x+2>2) \lor (x+2<2) \)
Simplifying: \( (x > 0) \lor (x < 0) \). Every \( x \in A \) satisfies \( x > 0 \):
- \( x = 1 \): \( T \lor F = T \) ✓
- \( x = 5 \): \( T \lor F = T \) ✓
All satisfy it → \( V(q) = T \)
Evaluation of \( r \): \( \forall x \in A, \exists y \in A \mid x+y>2 \)
For each \( x \), choose \( y = 2 \): \( x + 2 \geq 3 > 2 \) ✓ for all \( x \in A \).
\( V(r) = T \)
Computing \( s \):
\( s = \sim[(p \rightarrow q) \land (q \lor \sim r)] \)
Substituting:
\( = \sim[(T \rightarrow T) \land (T \lor \sim T)] = \sim[(T) \land (T \lor F)] = \sim[T \land T] = \sim T = F \)
\( V(s) = F \)
Exercise 35.
Let \( A={x \in \mathbb{N} \mid 0 < x < 8} \), \( B={y \in \mathbb{N} \mid 0 \leq y \leq 7} \). Find the truth values of:
a) \( p = \exists x \in A \mid \forall y \in B, x+y \neq 8 \)
b) \( q = \forall x \in A, \exists y \in B \mid x+y = 5 \)
c) \( r = \exists x \in A \mid \forall y \in B, x+y > 6 \)
d) \( s = \forall x \in A, \exists y \in B \mid xy \neq 0 \)
Solution:
💡 First define the sets by extension:
- \( A = {1, 2, 3, 4, 5, 6, 7} \)
- \( B = {0, 1, 2, 3, 4, 5, 6, 7} \)
a) \( p = \exists x \in A \mid \forall y \in B, x+y \neq 8 \)
In plain English: “Is there some \( x \in A \) such that no \( y \in B \) sums to 8 with it?”
For any \( x \in A \), the value \( y = 8 – x \) belongs to \( B \) (since \( 1 \leq 8 – x \leq 7 \)), and with that \( y \), \( x + y = 8 \) holds. No \( x \) can avoid it.
\( V(p) = F \) ✗
b) \( q = \forall x \in A, \exists y \in B \mid x+y = 5 \)
We need \( y = 5 – x \) for each \( x \). Is that \( y \) in \( B \)?
- \( x = 1 \): \( y = 4 \in B \) ✓
- \( x = 5 \): \( y = 0 \in B \) ✓
- \( x = 6 \): \( y = -1 \notin B \) ✗ — fails
\( V(q) = F \) ✗
c) \( r = \exists x \in A \mid \forall y \in B, x+y > 6 \)
We need one \( x \) that works for the worst case \( y = 0 \):
With \( x = 7 \): \( 7 + 0 = 7 > 6 \) ✓ (and with any other \( y \geq 0 \) it is even better)
\( V(r) = T \) ✓
d) \( s = \forall x \in A, \exists y \in B \mid xy \neq 0 \)
For each \( x \in A \) (where \( x \geq 1 \)), choose \( y = 1 \): \( x \cdot 1 = x \geq 1 \neq 0 \) ✓
\( V(s) = T \) ✓
Exercise 36.
Let \( A = {x \in \mathbb{N} / x \leq 50} \) be the universal set and let \( p \), \( q \), and \( r \) be the following quantified propositions:
\( p : \forall x \in A, \exists y \in A / x + 2y > x^2 \)
\( q : \forall x \in A, \exists y \in A, \forall z \in A : x + y – z \leq x + y \)
\( r : \exists x \in A, \exists y \in A, \forall z \in A : x – 2y \geq x + y – z \)
Find the truth value of: \( [(p \rightarrow q) \Delta (q \rightarrow r)] \leftrightarrow [q \lor \sim r] \)
Solution:
💡 Strategy: Evaluate \( p \), \( q \), and \( r \) separately (simplifying algebraically when possible), then substitute into the compound formula.
Evaluation of \( p \): \( \forall x \in A, \exists y \in A / x + 2y > x^2 \)
Solving for \( y \): \( 2y > x^2 – x \implies y > \frac{x(x-1)}{2} \)
Worst case \( x = 50 \): need \( y > \frac{50 \cdot 49}{2} = 1225 \). But \( y \leq 50 \), so no such \( y \) exists. ✗
\( p \) is False.
Evaluation of \( q \): \( \forall x \in A, \exists y \in A, \forall z \in A : x + y – z \leq x + y \)
Simplifying: \( x + y – z \leq x + y \iff -z \leq 0 \iff z \geq 0 \)
Since every \( z \in A \) satisfies \( z \geq 0 \), the condition always holds (regardless of \( x \) or \( y \)).
\( q \) is True.
Evaluation of \( r \): \( \exists x \in A, \exists y \in A, \forall z \in A : x – 2y \geq x + y – z \)
Simplifying: \( -2y \geq y – z \iff z \geq 3y \)
Reduces to: “Does \( \exists y \in A, \forall z \in A : z \geq 3y \)?”
With \( y = 0 \): \( z \geq 0 \) for all \( z \in A \) ✓
\( r \) is True.
Final computation:
| Component | Value |
|---|---|
| \( p \) | F |
| \( q \) | T |
| \( r \) | T |
| \( p \rightarrow q \) | \( F \rightarrow T = T \) |
| \( q \rightarrow r \) | \( T \rightarrow T = T \) |
| \( (p \rightarrow q) \Delta (q \rightarrow r) \) | \( T \Delta T = F \) |
| \( q \lor \sim r \) | \( T \lor F = T \) |
| \( F \leftrightarrow T \) | F |
Result: \( [(p \rightarrow q) \Delta (q \rightarrow r)] \leftrightarrow [q \lor \sim r] = F \)
What’s Next?
With logical quantifiers mastered, we are ready for the next chapter: Set Theory, where we will explore:
- ✅ Formal definition of a set, types of sets, and mathematical notation
- ✅ Relations between sets: subset, equality, and inclusion
- ✅ Operations: union, intersection, difference, and complement
- ✅ Properties of set operations
- ✅ Formal proofs using quantifiers and logical connectives
The quantifiers you practiced in these exercises will be an essential tool: expressions like \( \forall x \in A \) or \( \exists x \in A \) will appear constantly when proving properties and equalities between sets. Without that language, many proofs simply could not be formulated with rigor.