Proof techniques we’ve learned so far:

See also §3.3 and §3.4.2, as well as our list of equivalences.

In a small step proof, write an equivalent expression and cite the rule used to reach it. If several rules are needed, write them out one by one.

The following uses a note per line to show how it is equivalent to the preceding line

1 | A \lor (B \lor C) | |

2 | (A \lor B) \lor C | Associative property of \lor |

3 | (B \lor A) \lor C | Commutative property of \lor |

4 | B \lor (A \lor C) | Associative property of \lor |

5 | (\lnot (\lnot B)) \lor (A \lor C) | Double negation |

6 | (\lnot B) \rightarrow (A \lor C) | Disjunction ot implication |

In a prose proof, write the original and the new expression, separated by can be re-written as

or is equivalent to

. Only include intermediate steps or identified proof rules if you believe your audience would take more than a few minutes to figure them out themselves. Common shortcut phrases for guiding through steps include

- Rearranging
- Utilizing the associative, commutative, and distributive properties of operators
- Simplifying
- Removing double negation and the ones and zeros effects of tautologies and contradictions

This is the same example as the previous one, but written in prose style instead.

A \lor (B \lor C) can be re-written as (\lnot \lnot B) \lor (A \lor C), which is equivalent to (\lnot B) \rightarrow A \lor C by the equivalence of implication and disjuction.

See also §1.7, ∀x 17.5, and our proof of one of De Morgan’s laws

State a disjunctive tautology. For a simple tautology like P \lor \lnot P, stating it is enough; for more complicated tautologies, you may need to add a sub-proof or lemma^{1} that it *is* tautological.

Then proceed to consider several cases: one for each term of the disjunctive tautology, in each case assuming that that clause is true.

After completing all of the cases, the full proof is also completed:we may not know *which* case’s assumption is true, but because the disjunction is a tautology, we know at least one of them *must* be.

This is a full proof of one of our known equivalences

P \rightarrow Q \equiv \lnot P \lor Q

Either P is true or P is false.

- Case 1: P is true
The expression P \rightarrow Q in this case is equivalent to \top \rightarrow Q, which can be simplified to Q.

The expression \lnot P \lor Q in this case is equivalent to \bot \lor Q, which can be simplified to Q.

Since the two are equivalent to the same thing, they are equivalent to each other.

- Case 2: P is false
The expression P \rightarrow Q in this case is equivalent to \bot \rightarrow Q, which can be simplified to \top.

The expression \lnot P \lor Q in this case is equivalent to \top \lor Q, which can be simplified to \top.

Since the two are equivalent to the same thing, they are equivalent to each other.

Since P \rightarrow Q \equiv \lnot P \lor Q is true in both cases, it is true in general.

Case analysis in small-step proofs involves embedded sub-proofs, as is described in ∀x 17.5 and used in ∀x 17.1 and ∀x 19.6.

a lemma is a helper proof made before the main proof it will be used inside of↩︎