STEP (Sixth Term Examination Paper)

A proof is a chain of logical steps that starts from accepted facts or stated assumptions and ends at the result, with every step following from the ones before it. Examples never prove a general statement, however many there are, but a single counter-example disproves it. Most of the methods below appear in unfamiliar settings, so what matters is knowing why each one works. ## Notation for logic The symbol $\Rightarrow$ means "implies": $P \Rightarrow Q$ says that whenever $P$ is true, $Q$ is true. $P \Leftarrow Q$ is the same statement read the other way, and $P \Leftrightarrow Q$ means both hold, which is read "$P$ if and only if $Q$". $P$ is a **sufficient** condition for $Q$ when $P \Rightarrow Q$, because knowing $P$ is enough to be sure of $Q$. $P$ is a **necessary** condition for $Q$ when $Q \Rightarrow P$, because $Q$ cannot hold without $P$. When each implies the other, $P$ is necessary and sufficient, and the two statements are equivalent. For example, $x = 2$ is sufficient for $x^2 = 4$ but not necessary, since $x = -2$ also works. And $x^2 = 4$ is necessary for $x = 2$ but not sufficient. A statement and its converse are different claims. "If $n$ is a multiple of 6 then $n$ is even" is true and its converse "if $n$ is even then $n$ is a multiple of 6" is false. To prove $P \Leftrightarrow Q$ there are two separate tasks, $P \Rightarrow Q$ and $Q \Rightarrow P$, and a proof that only does one of them is incomplete. The contrapositive of $P \Rightarrow Q$ is…