Exercises: Predicate Logic and Quantifiers
These build from mechanical translation warm-ups to full negations, code, and modeling. Difficulty:
⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the
daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — do them
before you peek. Throughout, $\mathbb{N}$ includes $0$, and "domain" always means the domain of
discourse for the quantifiers in that problem.
Part A — Warm-ups: predicates, domains, and translation (⭐)
2.1 † For each, say whether it is a proposition or a predicate, and if it is a predicate, name its free variable(s): (a) "$n$ is divisible by $3$"; (b) "$12$ is divisible by $3$"; (c) "$x + y = y + x$"; (d) "$\forall x\,(x + 0 = x)$ over the integers."
2.2 Let the domain be the integers and let $P(x)$ = "$x^2 < 10$." List every value of $x$ in the domain for which $P(x)$ is true. Is the set finite?
2.3 † Let the domain be all employees of a company, with $M(x)$ = "$x$ is a manager," $E(x,y)$ = "$x$ earns more than $y$," and $D(x,y)$ = "$x$ and $y$ work in the same department." Using $c$ = Carol and $d$ = Dan, translate into symbols: "Carol is a manager, Dan is not, and Carol earns more than Dan."
2.4 Over the domain $\{1, 2, 3\}$, write $\forall x\,(x \le 3)$ as an explicit conjunction and $\exists x\,(x > 2)$ as an explicit disjunction. State the truth value of each.
2.5 † Translate each English sentence into symbols, choosing the correct connective inside the quantifier. Domain: all people. Use $S(x)$ = "$x$ is a student," $A(x)$ = "$x$ aced the final." (a) "Every student aced the final." (b) "Some student aced the final." (c) "No student aced the final."
2.6 Give the truth value, over the domain of integers, of each, with one sentence of justification: (a) $\exists x\,(x^2 = 9)$; (b) $\forall x\,(x^2 \ge x)$; (c) $\exists x\,(2x = 7)$.
Part B — Quantifiers, nesting, and order (⭐⭐)
2.7 † Let the domain be the integers and $S(x,y)$ = "$x + y = 0$." For each statement, give its English reading and its truth value, justifying the truth value from the definitions: (a) $\forall x\,\exists y\,S(x,y)$; (b) $\exists y\,\forall x\,S(x,y)$; (c) $\exists x\,\exists y\,S(x,y)$.
2.8 Over the domain of people with $L(x,y)$ = "$x$ has met $y$," translate into careful English, and say which statement is stronger (implies the other): $\forall x\,\exists y\,L(x,y)$ versus $\exists y\,\forall x\,L(x,y)$.
2.9 † (Restriction idioms.) Domain: integers. Using $\text{Pos}(x)$ = "$x > 0$," $\text{Ev}(x)$ = "$x$ is even," and the arithmetic predicate "$x > 1$," write each in symbols, getting the $\forall$-with-$\rightarrow$ / $\exists$-with-$\land$ pairing right: (a) "every positive integer is $> 1$ or equals $1$" — actually: "every positive integer is $\ge 1$"; (b) "some even integer is positive."
2.10 Determine, over the domain of positive integers, the truth value of each, with justification: (a) $\forall x\,\exists y\,(y > x)$; (b) $\exists y\,\forall x\,(y \le x)$ ("there is a smallest positive integer"); (c) $\forall x\,\forall y\,(x + y > x)$.
2.11 † (Three quantifiers.) Domain: integers. Read $\forall x\,\forall y\,\exists z\,(x < z \land z < y)$ in plain English. Is it true over the integers? Justify, and contrast with what happens over the rationals $\mathbb{Q}$.
2.12 Show by exhibiting a domain and predicate that $\forall x\,\exists y\,P(x,y)$ can be true while $\exists y\,\forall x\,P(x,y)$ is false. (Reuse a chapter example or invent your own; state the domain explicitly.)
Part C — Prove it: scaffolded (⭐⭐)
2.13 † (Scaffolded — fill the missing step.) Prove the equivalence $\neg\,\forall x\,(Q(x) \rightarrow P(x)) \equiv \exists x\,(Q(x) \land \neg P(x))$ by pushing the negation inward one step at a time. Fill in each blank with the law used and the resulting formula:
- Start: $\neg\,\forall x\,(Q(x) \rightarrow P(x))$.
- Apply the quantifier negation law $\neg\forall x\,(\cdots) \equiv \underline{\hphantom{xxxxxx}}$, giving $\exists x\,\neg\big(Q(x) \rightarrow P(x)\big)$.
- Apply the implication-negation law from Chapter 1, $\neg(a \rightarrow b) \equiv \underline{\hphantom{xxxxxx}}$, to the body, giving $\exists x\,\big(\underline{\hphantom{xxxxxxxxxx}}\big)$.
- Conclude: the negation says "there is an $x$ that is $Q$ and \underline{\hphantom{xxxx}} $P$" — i.e., a counterexample. $\blacksquare$
2.14 (Scaffolded.) Let the domain be a finite set $D = \{d_1, \dots, d_n\}$. Prove that $\forall x\,P(x) \equiv P(d_1) \land \dots \land P(d_n)$ implies the negation law $\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)$, by applying De Morgan's law from Chapter 1 to the conjunction. Fill in: starting from $\neg\big(P(d_1) \land \dots \land P(d_n)\big)$, De Morgan gives $\underline{\hphantom{xxxxxxxxxxxx}}$, which is the disjunction $\exists x\,\neg P(x)$ over $D$. State in one sentence why this argument does not, by itself, settle the case of an infinite domain.
2.15 † (Scaffolded.) Prove that $\exists y\,\forall x\,L(x,y)$ implies $\forall x\,\exists y\, L(x,y)$ (for any predicate $L$ and any domain). Fill the gaps: "Suppose $\exists y\,\forall x\,L(x,y)$ holds, so there is a specific element $y_0$ with $\forall x\,L(x, y_0)$. To prove $\forall x\,\exists y\,L(x,y)$, take an arbitrary $x$. We must exhibit a $y$ with $L(x,y)$; choose $y = \underline{\hphantom{xx}}$. Then $L(x, y_0)$ holds because \underline{\hphantom{xxxxxxxxxx}}. Since $x$ was arbitrary, $\forall x\,\exists y\,L(x,y)$." Then explain in one sentence why the converse fails.
Part D — Implement it (⭐⭐)
Write Python for each. Do not run it — hand-trace and include an # Expected output: comment,
matching the book's convention. (Reference solutions live in code/exercise-solutions.py.)
2.16 † Write a one-line Python expression, using all, for the predicate "every element of the
list xs is strictly between 0 and 100." Then write the existential dual with any: "some element
of xs is outside the range $[0, 100]$." Trace both on xs = [10, 50, 250] and give the expected
output.
2.17 Write a function is_strictly_increasing(xs) that returns True iff
$\forall i\,(0 \le i < \text{len} - 1 \rightarrow xs[i] < xs[i+1])$, using all over range. Trace it
on [1, 4, 4, 9] and [1, 4, 7, 9]; give expected output for both.
2.18 † Write a function find_witness(predicate, domain) that returns the first element of
domain satisfying predicate (a witness to $\exists x\,P(x)$), or None if none exists. Explain in
one comment how this is the existential mirror of the chapter's counterexample function. Trace it
finding the first composite number in range(2, 8); give expected output.
2.19 Write a single expression that evaluates the nested statement
$\forall x\,\exists y\,(x + y = 0)$ over the finite domain D = range(-3, 4), using all and any.
Trace it and give the expected output. Then in a comment, explain why a True result here is not a
proof that the statement holds over all of $\mathbb{Z}$.
Part E — Find the error (⭐⭐)
Each item below is wrong. State precisely which step fails and why; give a corrected version where asked.
2.20 † Claim: "Some prime is even" is written $\exists x\,(\text{Prime}(x) \rightarrow \text{Even}(x))$. A student then "verifies" it by noting that $x = 9$ makes the implication true (since $\text{Prime}(9)$ is false), and declares the claim established. Identify the two errors: the wrong translation, and why the witness $9$ does not establish "some prime is even." Give the correct translation.
2.21 Claimed negation. A student negates "$\forall x\,(x > 0 \rightarrow x^2 > 0)$" (domain: integers) as "$\exists x\,(x > 0 \rightarrow x^2 \le 0)$." Show this is wrong by applying the implication-negation law correctly, and state the right negation. Is the original statement true?
2.22 † Order swap. A teammate argues: "Over the integers, $\forall x\,\exists y\,(y > x)$ is true, and reordering adjacent quantifiers never changes meaning, so $\exists y\,\forall x\,(y > x)$ is also true." Pinpoint the false premise and give the truth value of each statement, with a one-line reason.
2.23 Vacuous-truth bug. A reviewer writes all_paid = all(u.has_paid for u in customers) and
asserts "if all_paid is True, then we definitely have at least one paying customer." Explain why
this is wrong in terms of vacuous truth, name the value of all_paid when customers == [], and write
a one-line guard that captures the reviewer's actual intent.
Part F — Model it & Conjecture and test (⭐⭐⭐)
2.24 † (Model it.) A web service has a set Users and a set Resources. The access-control
predicate is $\text{Can}(u, r)$ = "user $u$ may access resource $r$." Translate each English policy
into a quantified statement over these domains, and for the last one, give its negation in plain
English (what a security auditor looks for):
(a) "Every user can access at least one resource."
(b) "There is a public resource every user can access."
(c) "No resource is accessible to every user" — and negate it.
2.25 (Model it.) A distributed system has a set Requests and a set Servers. Define a
predicate $\text{Handles}(s, r)$ = "server $s$ handles request $r$." Express the reliability goal
"every request is handled by some server" and the redundancy goal "every request is handled by at least
two distinct servers" (you may use $\exists s_1\,\exists s_2$ with $s_1 \ne s_2$). Which goal is
stronger, and why does the order of quantifiers matter when comparing "some server handles every
request" to your first statement?
2.26 † (Conjecture and test, then prove/disprove.) Conjecture: "Over the positive integers, for
every $n$ there exists a prime $p$ with $n < p \le 2n$." (a) Write a Python snippet using a helper
is_prime and the pattern all(... any(...) ...) to test the conjecture for all $n$ from $1$ to
$50$; give the expected output (a single boolean) and explain what it does and does not establish.
(b) State the negation of the conjecture in symbols (what a counterexample would look like). (c) Note
which famous theorem this is — you are not asked to prove it — and explain, in one sentence tying
to theme four, why your code is evidence rather than proof.
2.27 (Conjecture and test, then prove/disprove.) Conjecture: "For all integers $n$,
$n^2 + n + 41$ is prime." (a) Write code using the chapter's counterexample pattern to search
range(0, 45) for a counterexample; predict what it returns and at which $n$. (b) Using the negation
law, state precisely what a single returned value proves. (c) Prove your disproof by hand: exhibit
the counterexample and show the value is composite. (Hint: try $n = 40$.)
Part G — Interleaved (mixing earlier chapters)
Mixing techniques from Chapter 1 keeps the connectives sharp — predicate logic is built on top of them.
2.28 † (Ch. 1 + 2.) The restricted universal "every $Q$ is a $P$" is $\forall x\,(Q(x) \rightarrow P(x))$. Using the Chapter 1 equivalence $a \rightarrow b \equiv \neg a \lor b$, rewrite the body without an implication, then state in English what the resulting form says about elements that are not $Q$.
2.29 (Ch. 1 + 2.) Over the domain $\{T, F\}^2$ of truth-value pairs $(p, q)$, the statement "$\forall (p,q)\,\big((p \land q) \rightarrow (p \lor q)\big)$" claims a Chapter 1 fact. Restate the claim as "this formula is a ___," and verify it by checking all four rows. Which §1 concept is this?
2.30 † (Ch. 1 + 2.) De Morgan's laws say $\neg(p \land q) \equiv \neg p \lor \neg q$. Explain, in two or three sentences, how the quantifier negation law $\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)$ is *literally the same law* when the domain is finite. (Use the "$\forall$ is a big $\land$" reading.)
2.31 (Ch. 1 + 2.) A function's contract reads: precondition $\forall i\,(0 \le i < n-1
\rightarrow a[i] \le a[i+1])$ (the array is sorted), postcondition $\exists j\,(a[j] = t)$ ("found").
(a) Write the precondition as a all(...) expression over range. (b) Suppose a call violates the
precondition; write, in symbols, exactly what is then true (the negation), and say what a checker would
return as the witnessing object. (c) In one sentence, explain why "the function passed 100 tests" does
not establish the postcondition for all valid inputs (theme two).
Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each
translation, the rubric rewards: the correct quantifier(s) in the correct order, the correct connective
inside ($\rightarrow$ for $\forall$, $\land$ for $\exists$), an explicit domain, and — for negations —
a fully pushed-in $\neg$ that lands on the innermost predicate.