Discussion 0B

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.

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.