Self-Assessment Quiz: Direct Proof and Contraposition

Twenty questions to check your grip on definitions, the two strategies, and the mistake catalog. Answer each from memory before opening the key. Aim for 16+.

Question 1

A proof of a universally quantified statement differs from testing because:

A) a proof checks more cases than any test suite B) a proof establishes the statement for every case at once, with no input left unchecked C) a proof is faster to write than a test D) a proof only needs to handle the cases the tests missed

Question 2

By the chapter's definition, an integer $n$ is even iff:

A) $n$ is divisible by 4 B) $n / 2$ is a number C) there exists an integer $k$ with $n = 2k$ D) $n$ is not odd, by assumption

Question 3

The statement "$a \mid b$" means:

A) the number $a / b$ B) there exists an integer $c$ with $b = ac$ (and $a \neq 0$) C) $a$ is less than or equal to $b$ D) the remainder of $b \div a$ is nonzero

Question 4

"$3 \mid 12 = 4$" is best described as:

A) a true statement B) a correct computation C) a type error — it equates a true/false statement with a number D) the definition of divisibility

Question 5

In a direct proof of $P \rightarrow Q$, you:

A) assume $\neg Q$ and derive $\neg P$ B) assume $P$ and derive $Q$ C) assume $\neg(P \rightarrow Q)$ and derive a contradiction D) check $P \rightarrow Q$ for several values

Question 6

The contrapositive of "if $P$ then $Q$" is:

A) if $Q$ then $P$ B) if $\neg P$ then $\neg Q$ C) if $\neg Q$ then $\neg P$ D) if $P$ then $\neg Q$

Question 7

The converse of "if $P$ then $Q$" is:

A) logically equivalent to the original B) "if $Q$ then $P$," and not logically equivalent to the original C) "if $\neg Q$ then $\neg P$" D) always false

Question 8

You want to prove "for every integer $n$, if $n^2$ is odd then $n$ is odd." The recommended strategy is:

A) a direct proof, by taking a square root B) proof by contraposition, because the direct attack can't extract $n$ from $n^2$ C) proof by example, checking $n = 1, 3, 5$ D) a vacuous proof

Question 9

The contrapositive of "$\forall x,\ P(x) \rightarrow Q(x)$" is:

A) $\exists x,\ \neg Q(x) \rightarrow \neg P(x)$ B) $\forall x,\ \neg Q(x) \rightarrow \neg P(x)$ C) $\forall x,\ Q(x) \rightarrow P(x)$ D) $\exists x,\ \neg P(x) \land \neg Q(x)$

Question 10

A vacuous proof of $P \rightarrow Q$ works by showing:

A) $Q$ is always true B) $P$ is always false C) both $P$ and $Q$ are true D) $P$ and $Q$ are equivalent

Question 11

A trivial proof of $P \rightarrow Q$ works by showing:

A) $Q$ is always true, without using $P$ B) $P$ is always false C) $P$ implies $\neg Q$ D) the statement is a tautology of Chapter 1

Question 12

Writing $a = 2k$ and $b = 2k$ to represent two arbitrary even integers is a mistake because:

A) $2k$ is not always even B) it secretly forces $a = b$ C) $k$ might not be an integer D) you should use $2k + 1$ instead

Question 13

Which is a complete proof of "there exists an integer $x$ with $x^2 = 49$"?

A) checking $x = 1, 2, 3$ and seeing a pattern B) exhibiting $x = 7$, since $7^2 = 49$ C) assuming no such $x$ exists and deriving a contradiction only D) none — you can never prove an existential with one example

Question 14

Which biconditional was assembled in §4.3–4.4 from a direct proof (forward) and a contraposition (reverse)?

A) $n$ is even iff $n$ is divisible by 4 B) $n$ is odd iff $n^2$ is odd C) $a \mid b$ iff $b \mid a$ D) $a + b$ is even iff $a = b$

Question 15

To prove a biconditional $P \leftrightarrow Q$, you must:

A) prove only $P \rightarrow Q$ B) prove only the contrapositive C) prove both $P \rightarrow Q$ and $Q \rightarrow P$ D) build a truth table

Question 16 (True/False, justify)

True or false: If a program's correctness claim has a precondition that excludes a given input, then the claim is (vacuously) satisfied on that input. Justify in one sentence.

Question 17 (True/False, justify)

True or false: A conditional and its converse are logically equivalent. Justify in one sentence, with an everyday example.

Question 18 (True/False, justify)

True or false: Verifying the Goldbach conjecture by computer past $10^{18}$ makes it a theorem. Justify in one sentence.

Question 19 (Short answer)

In the master habit of this chapter, what are the three moves — in order — that take you from a hypothesis like "$n$ is odd" to a conclusion like "$n^2$ is odd"?

Question 20 (Short answer)

When a proof states no strategy, name the three opening moves that tell you whether it is a direct proof, a proof by contraposition, or (Chapter 5) a proof by contradiction.

Answer Key

Topics to review by question