How to prove each kind of sentence
Read the goal's main connective, and it tells you which rule finishes the proof.
Find the main connective of the sentence you are trying to prove. That tells you the rule most likely to finish the proof, and what you owe before you can use it.
- A conditional A \to B → open a subproof assuming A, reach B, close it with \toI.
- A negation \neg A → open a subproof assuming A, reach \bot, close it with \negI.
- A conjunction A \wedge B → prove A and prove B, then \wedgeI.
- A disjunction A \vee B → if you can prove one side, use \veeI. If you can't prove either side alone, use indirect proof: assume \neg(A \vee B) and reach \bot.
- A biconditional A \leftrightarrow B → two subproofs, A to B and B to A, then \leftrightarrowI.
- A sentence letter, or anything the steps above can't reach → indirect proof: assume its negation and reach \bot.
Also work forward from the premises. Look at what the elimination rules and the derived rules let you get from what you already have.
The goal is a conditional
Conditional introduction (\toI). If a subproof begins with the assumption A on line i and ends with B on line j, then after the subproof closes you may write A \to B, citing "\toI i–j." The assumption A is discharged.
What is this saying? To prove "if A then B," suppose A for the sake of argument, reason your way to B, then close off the supposition and write the conditional.
Why should I care? It is the standard way to prove a conditional, in logic and in mathematics, and it introduces subproofs, which the rules for \vee, \neg, and \leftrightarrow also use.
Intuition. The subproof shows that whenever A is true (together with the lines available above), B is true too. That is exactly what A \to B claims.
Ingredients.
- Assumption (AS): a line supposed without justification, starting a subproof.
- Subproof: the indented lines from the assumption to its last line.
- Discharge: once the subproof closes, its lines may not be cited individually; only the whole subproof i–j may be cited.
Example.
| # | Sentence | Justification |
|---|---|---|
| 1 | P \to Q | PR |
| 2 | Q \to R | PR |
| 3 | │ P | AS |
| 4 | │ Q | \toE 1, 3 |
| 5 | │ R | \toE 2, 4 |
| 6 | P \to R | \toI 3–5 |
What breaks. After line 6 you may not cite line 4 or 5: they depended on the assumption P, which is no longer in force. A proof may not end inside an open subproof.
Example
Show proof
Suppose that on every row making the available lines and A true, B is true. Take any row making the available lines true. If A is F there, A \to B is T. If A is T there, then B is T by the supposition, so A \to B is T again. Either way A \to B is T on every row making the available lines true.
The goal is a negation
Negation elimination (\negE). From A on line i and \neg A on line j, write \bot, citing "\negE i, j."
Negation introduction (\negI). From a subproof assuming A and ending with \bot (lines i–j), write \neg A, citing "\negI i–j."
Explosion (X). From \bot on line i, write any sentence at all, citing "X i."
What is this saying? A sentence together with its negation is a contradiction, recorded as \bot. If an assumption leads to a contradiction, the assumption is false. And from a contradiction, anything may be written.
Why should I care? These rules give proofs a way to reason about "not." \negI is how you show something is false, and explosion is what lets a proof finish off a case that can't happen.
Intuition. A and \neg A are never true together, so any line of reasoning that reaches both has started from something false. Explosion is the proof-rule version of the fact that inconsistent premises entail every sentence.
Ingredients.
- \bot: the contradiction symbol, "falsum." It stands for a sentence false on every row.
- \negE needs a sentence and its exact negation, not merely two sentences that clash in meaning.
Example.
| # | Sentence | Justification |
|---|---|---|
| 1 | P \to Q | PR |
| 2 | \neg Q | PR |
| 3 | │ P | AS |
| 4 | │ Q | \toE 1, 3 |
| 5 | │ \bot | \negE 4, 2 |
| 6 | \neg P | \negI 3–5 |
What breaks. X may be cited only from a line that is \bot. Two sentences that merely seem to disagree, like "the room is warm" and "the room is cold," are not A and \neg A.
\negI closes a subproof that assumed A and reached \bot.
Show proof
\negE: no row makes both A and \neg A true, so there is no row making the cited lines true on which \bot would need to be true; the rule never leads from true lines to a false one. \negI: the subproof shows no row making the available lines true also makes A true (such a row would make \bot true). So on every such row A is F and \neg A is T. X: no row makes \bot true, so there is nothing to check.
The goal is a conjunction or a biconditional
Theorem
The conjunction rules
Conjunction introduction (\wedgeI). From A on line i and B on line j, write A \wedge B, citing "\wedgeI i, j."
Conjunction elimination (\wedgeE). From A \wedge B on line i, write A, or write B, citing "\wedgeE i."
What is this saying? If you have both parts, you may put them together; if you have them together, you may take either one out.
Why should I care? These are the simplest rules in the system and the pattern every other pair follows: an introduction rule to build a connective, an elimination rule to use it.
Intuition. A conjunction is true exactly when both conjuncts are, so building one from both parts, or taking a part out, can never lead from truth to falsehood.
Ingredients.
- A, B: any sentences.
- Line numbers i, j: earlier lines that are still available (not inside a closed subproof).
- \wedgeE applies only when \wedge is the main connective of line i.
Example.
| # | Sentence | Justification |
|---|---|---|
| 1 | P \wedge Q | PR |
| 2 | Q | \wedgeE 1 |
| 3 | P | \wedgeE 1 |
| 4 | Q \wedge P | \wedgeI 2, 3 |
What breaks. From (P \wedge Q) \vee R you cannot write P by \wedgeE: the main connective is \vee, and the whole line can be true with P false.
Show proof
On any row where A and B are both T, A \wedge B is T, so \wedgeI never leads from true lines to a false one. On any row where A \wedge B is T, both A and B are T, so \wedgeE doesn't either.
Biconditional introduction (\leftrightarrowI). From a subproof assuming A and ending with B (lines i–j) and a subproof assuming B and ending with A (lines k–l), write A \leftrightarrow B, citing "\leftrightarrowI i–j, k–l."
Biconditional elimination (\leftrightarrowE). From A \leftrightarrow B on line i and A on line j, write B; or from A \leftrightarrow B and B, write A. Cite "\leftrightarrowE i, j."
What is this saying? To prove "A if and only if B," prove each direction. To use it, knowing either side gives you the other.
Why should I care? Definitions and "exactly when" claims are biconditionals, so these rules are how you prove and use them.
Intuition. A \leftrightarrow B says the same as (A \to B) \wedge (B \to A), so its rules are the conditional rules done in both directions.
Ingredients.
- Two subproofs for \leftrightarrowI, one for each direction.
- \leftrightarrowE works from either side, unlike \toE.
Example.
| # | Sentence | Justification |
|---|---|---|
| 1 | P \leftrightarrow Q | PR |
| 2 | Q | PR |
| 3 | P | \leftrightarrowE 1, 2 |
What breaks. One subproof gives only one direction, which proves a conditional, not a biconditional.
Two subproofs, one for each direction. One direction alone isn't enough.
Show proof
\leftrightarrowE: on any row where A \leftrightarrow B is T, A and B have the same value, so if one is T the other is. \leftrightarrowI: on any row making the available lines true, the two subproofs show that A being T forces B to be T and B being T forces A to be T, so A and B have the same value and A \leftrightarrow B is T.
The goal is a disjunction
Theorem
The disjunction rules
Disjunction introduction (\veeI). From A on line i, write A \vee B or B \vee A, where B is any sentence, citing "\veeI i."
Disjunction elimination (\veeE). From A \vee B on line i, a subproof assuming A and ending with C (lines j–k), and a subproof assuming B and ending with the same C (lines l–m), write C, citing "\veeE i, j–k, l–m."
What is this saying? From one part you may conclude any "or" that contains it. To use an "or," show that the same conclusion follows whichever part is true.
Why should I care? \veeI is addition from chapter 4. \veeE is proof by cases, one of the most common patterns in all reasoning: "either way, C."
Intuition. An inclusive "or" is true whenever one part is. And if C follows from each part, and at least one part is true, C is true.
Ingredients.
- B in \veeI: any sentence at all, even one unrelated to the proof.
- C in \veeE: must be the SAME sentence at the end of both subproofs.
- Both subproofs close, discharging A and B.
Example.
| # | Sentence | Justification |
|---|---|---|
| 1 | P \vee Q | PR |
| 2 | │ P | AS |
| 3 | │ Q \vee P | \veeI 2 |
| 4 | │ Q | AS |
| 5 | │ Q \vee P | \veeI 4 |
| 6 | Q \vee P | \veeE 1, 2–3, 4–5 |
(Lines 2–3 and 4–5 are two separate subproofs.)
What breaks. Reaching C from only one disjunct proves nothing: the other disjunct may be the true one.
\veeI works only if one disjunct can be proved on its own. Often it can't. Then use indirect proof.
Show proof
\veeI: on any row where A is T, A \vee B is T. \veeE: take a row making the available lines, including A \vee B, true. At least one of A, B is T there. If A is, the first subproof shows C is T; if B is, the second does. Either way C is T.
Nothing direct works
Theorem
Indirect proof
Indirect proof (IP). From a subproof assuming \neg A and ending with \bot (lines i–j), write A, citing "IP i–j."
What is this saying? To prove A, suppose it is false, derive a contradiction, and conclude that A is true after all.
Why should I care? Some sentences, such as P \vee \neg P, have no easy direct proof. IP is the last-resort strategy that works when nothing else does.
Intuition. If assuming "not A" leads to something impossible, then "not A" is false, so A is true.
Ingredients.
- The assumption is the NEGATION of the goal.
- The subproof must end with \bot.
How it differs from \negI. \negI assumes A and concludes \neg A. IP assumes \neg A and concludes A. Check which one the assumption is.
Example.
| # | Sentence | Justification |
|---|---|---|
| 1 | \neg\neg P | PR |
| 2 | │ \neg P | AS |
| 3 | │ \bot | \negE 2, 1 |
| 4 | P | IP 2–3 |
What breaks. Concluding \neg A from a subproof that assumed \neg A is not a rule; IP delivers A itself.
Example
Show proof
The subproof shows that no row making the available lines true also makes \neg A true. So on every such row \neg A is F, and A is T.
Section
Indirect proof
Working forward from what you have
Conditional elimination (\toE). From A \to B on line i and A on line j, write B, citing "\toE i, j."
Reiteration (R). From A on an available line i, write A again, citing "R i."
What is this saying? If you have a conditional and its antecedent, you may write its consequent. And you may always repeat a line you already have.
Why should I care? \toE is modus ponens from chapter 4, now as a rule you can cite in a proof. Reiteration looks trivial, but you need it to bring a line into a subproof or to end a subproof on a line you already have.
Intuition. The conditional's only false row has A T and B F. If both A \to B and A are true, that row is ruled out, so B is true.
Ingredients.
- A \to B: must be the whole line, with \to as its main connective.
- A: must match the antecedent exactly.
- Available: not inside a subproof that has already closed.
Example.
| # | Sentence | Justification |
|---|---|---|
| 1 | P \to Q | PR |
| 2 | Q \to R | PR |
| 3 | P | PR |
| 4 | Q | \toE 1, 3 |
| 5 | R | \toE 2, 4 |
What breaks. From A \to B and B you cannot write A: that is affirming the consequent, and the row A F, B T is a countermodel.
Show proof
On any row where A \to B and A are both T, B must be T, since the only row making A \to B false has A T and B F. Reiteration writes a line that was already true. Neither rule leads from true lines to a false one.
Each of these may be cited as a single step, because each can be replaced by a proof that uses only the basic rules.
| Rule | From | Write |
|---|---|---|
| Modus tollens (MT) | A \to B and \neg B | \neg A |
| Disjunctive syllogism (DS) | A \vee B and \neg A | B |
| A \vee B and \neg B | A | |
| Double negation elimination (DNE) | \neg\neg A | A |
| Double negation (DN) | \neg\neg A, or A | A, or \neg\neg A (either direction) |
| De Morgan (DeM) | \neg(A \vee B) | \neg A \wedge \neg B, and the reverse |
| \neg(A \wedge B) | \neg A \vee \neg B, and the reverse |
What is this saying? Patterns you would otherwise prove again and again, some of them the named forms from chapter 4, can be used in one line.
Why should I care? Derived rules make proofs shorter and easier to read, without letting you prove anything the basic rules can't.
Intuition. A derived rule is a saved proof: each time you cite it, imagine the justifying proof pasted in its place.
Ingredients.
- Basic rules: R and the introduction and elimination rules for each connective, plus X and IP.
- Derived rule: a rule whose every use can be replaced by basic-rule steps.
Example. From P \to Q and \neg Q, MT gives \neg P in one line; the negation-rules card shows the five basic-rule lines it replaces.
What breaks. A derived rule has the same fixed pattern as a basic rule. DS needs the NEGATION of a disjunct; from A \vee B and A nothing follows about B.
Shortcuts only. Each one stands for a short proof in the basic rules.
Show proof
MT. 1 A \to B (PR); 2 \neg B (PR); 3 │ A (AS); 4 │ B (\toE 1, 3); 5 │ \bot (\negE 4, 2); 6 \neg A (\negI 3–5).
DS. 1 A \vee B (PR); 2 \neg A (PR); 3 │ A (AS); 4 │ \bot (\negE 3, 2); 5 │ B (X 4); 6 │ B (AS); 7 │ B (R 6); 8 B (\veeE 1, 3–5, 6–7). The other form is symmetric.
DNE. 1 \neg\neg A (PR); 2 │ \neg A (AS); 3 │ \bot (\negE 2, 1); 4 A (IP 2–3).
DN, adding direction. 1 A (PR); 2 │ \neg A (AS); 3 │ \bot (\negE 1, 2); 4 \neg\neg A (\negI 2–3). The removing direction is DNE.
DeM, one direction. 1 \neg(A \vee B) (PR); 2 │ A (AS); 3 │ A \vee B (\veeI 2); 4 │ \bot (\negE 3, 1); 5 \neg A (\negI 2–4); 6 │ B (AS); 7 │ A \vee B (\veeI 6); 8 │ \bot (\negE 7, 1); 9 \neg B (\negI 6–8); 10 \neg A \wedge \neg B (\wedgeI 5, 9). The other three directions are proved the same way, the one from \neg(A \wedge B) using IP.
Each of these may be cited as a single step:
| Rule | From | Write |
|---|---|---|
| Hypothetical syllogism (HS) | A \to B and B \to C | A \to C |
| Constructive dilemma (CD) | A \to B, C \to D, and A \vee C | B \vee D |
| Destructive dilemma (DD) | A \to B, C \to D, and \neg B \vee \neg D | \neg A \vee \neg C |
What is this saying? The three chaining and dilemma forms you met in chapter 4 in English are now rules you may cite in a formal proof, each justified by a proof in the basic rules.
Why should I care? Long arguments often chain conditionals or reason by dilemma. Citing the rule saves a subproof each time.
Intuition. HS is two uses of \toE inside a conditional proof. CD is proof by cases with \toE in each case. DD is CD with modus tollens in place of modus ponens.
Ingredients.
- A, B, C, D: any sentences. In HS, the B in both premises must be the same sentence.
- Each rule's premises must match its pattern exactly, including which parts are negated.
Example. From P \to Q and Q \to R, HS gives P \to R; the conditional-introduction card shows the four lines it replaces.
What breaks. HS does not run backwards: from A \to B and B \to C you may not write C \to A. DD denies the consequents, not the antecedents.
Show proof
HS. 1 A \to B (PR); 2 B \to C (PR); 3 │ A (AS); 4 │ B (\toE 1, 3); 5 │ C (\toE 2, 4); 6 A \to C (\toI 3–5).
CD. 1 A \to B; 2 C \to D; 3 A \vee C (all PR); 4 │ A (AS); 5 │ B (\toE 1, 4); 6 │ B \vee D (\veeI 5); 7 │ C (AS); 8 │ D (\toE 2, 7); 9 │ B \vee D (\veeI 8); 10 B \vee D (\veeE 3, 4–6, 7–9).
DD. 1 A \to B; 2 C \to D; 3 \neg B \vee \neg D (all PR); 4 │ \neg B (AS); 5 │ \neg A (MT 1, 4); 6 │ \neg A \vee \neg C (\veeI 5); 7 │ \neg D (AS); 8 │ \neg C (MT 2, 7); 9 │ \neg A \vee \neg C (\veeI 8); 10 \neg A \vee \neg C (\veeE 3, 4–6, 7–9). MT is itself derived from the basic rules, so this is a basic-rule proof once MT's proof is pasted in.