# Proof techniques

## Direct

To prove $P \Rightarrow Q$, begin with $P$ and derive more facts until you reach $Q$. Often, direct proofs apply to questions of the form $P_0 \land P_1 \land \cdots \land P_n \Rightarrow Q$ because the various $P_i$s together can lead to intermediate logical steps.

## Contraposition

Since an implication $P \Rightarrow Q$ and its contrapositive $\lnot Q \Rightarrow \lnot P$ are equivalent, you can prove the contrapositive instead. Proof by contraposition can be useful for questions of the form $P \Rightarrow Q_0 \lor Q_1 \lor \cdots \lor Q_n$ for the same reason as above because this is equivalent to $\lnot Q_0 \land \lnot Q_1 \land \cdots \land \lnot Q_n \Rightarrow \lnot P$.

To prove $P$, assume $P$ is false and that results in something known to be false $(\lnot P \Rightarrow \text{false})$. Proof by contradiction is a type of proof by contraposition because $\text{true} \Rightarrow P$ is equivalent to $\lnot P \Rightarrow \text{false}$.
Suppose there are cases $C_0, C_1, \cdots, C_n$ of which at least one must be true. You can prove $P$ by showing $P \land C_i$ is true for each of the $C_i$ when $C_i$ is true. This is because $P \equiv P \land (C_0 \lor \cdots \lor C_n) \equiv (P \land C_0) \lor \cdots (P \land C_n)$. Proof by cases is helpful when knowing $C_i$ gives you information to complete the proof that $P$ alone does not.