This page does not represent the most current semester of this course; it is present merely as an archive.
Proof techniques we’ve learned so far:
See also MCS 3.3 and MCS 3.4.2, our list of equivalences, and our guide to direct proof.
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 to 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
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 our list of entailments.
Applying entailment is very much like applying equivalence rule, except it only needs to work in one direction. Because A \equiv B implies A \vDash B, you can use equivalence rules in a proof that applies entailment.
There are many more entailments (sometimes called proof rules
or inference rules
) than there are equivalence rules, so using them can make proof construction much easier than limiting yourself to equivalences.
A proof that only uses proof rules is sometimes called a direct proof.