Chapter 19 Additional rules for TFL
In chapter 17, we introduced the basic rules of our proof system for TFL. In this section, we will add some additional rules to our system. Our extended proof system is a bit easier to work with. (However, in chapter 21 we will see that they are not strictly speaking necessary.)
19.1 Disjunctive syllogism
Here is a very natural argument form.

Elizabeth is either in Massachusetts or in DC.

She is not in DC.

∴
She is in Massachusetts.
This is called disjunctive syllogism. We add it to our proof system as follows:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\vee $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$n$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$

DS $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$, $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$n$}$

and
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\vee $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$n$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$

DS $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$, $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$n$}$

As usual, the disjunction and the negation of one disjunct may occur in either order and need not be adjacent. However, we always cite the disjunction first.
19.2 Modus tollens
Another useful pattern of inference is embodied in the following argument:

If Hilary has won the election, then she is in the White House.

She is not in the White House.

∴
She has not won the election.
This inference pattern is called modus tollens. The corresponding rule is:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\to $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$n$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$

MT $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$, $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$n$}$

As usual, the premises may occur in either order, but we always cite the conditional first.
19.3 Doublenegation elimination
Another useful rule is doublenegation elimination. It does exactly what it says on the tin:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$

DNE $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$

The justification for this is that, in natural language, doublenegations tend to cancel out.
That said, you should be aware that context and emphasis can prevent them from doing so. Consider: ‘Jane is not not happy’. Arguably, one cannot infer ‘Jane is happy’, since the first sentence should be understood as meaning the same as ‘Jane is not unhappy’. This is compatible with ‘Jane is in a state of profound indifference’. As usual, moving to TFL forces us to sacrifice certain nuances of English expressions.
19.4 Excluded middle
Suppose that we can show that if it’s sunny outside, then Bill will have brought an umbrella (for fear of burning). Suppose we can also show that, if it’s not sunny outside, then Bill will have brought an umbrella (for fear of rain). Well, there is no third way for the weather to be. So, whatever the weather, Bill will have brought an umbrella.
This line of thinking motivates the following rule:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$i$}$ 
open subproof,
1

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$

AS

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$j$}$ 
1

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$k$}$ 
close subproof,
open subproof,
1

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$

AS

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$l$}$ 
1

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


close subproof,
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$

LEM $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$i$}$–$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$j$}$, $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$k$}$–$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$l$}$

The rule is sometimes called the law of excluded middle, since it encapsulates the idea that $\mathcal{A}$ may be true or $\neg \mathcal{A}$ may be true, but there is no middle way where neither is true.^{1}^{1} 1 You may sometimes find logicians or philosophers talking about “tertium non datur.” That’s the same principle as excluded middle; it means “no third way.” Logicians who have qualms about indirect proof also have qualms about LEM. There can be as many lines as you like between $i$ and $j$, and as many lines as you like between $k$ and $l$. Moreover, the subproofs can come in any order, and the second subproof does not need to come immediately after the first.
To see the rule in action, consider:
Here is a proof corresponding with the argument:
Line number

Subproof level

Formula

Justification


$1$ 
0

$P$

PR

$2$ 
open subproof,
1

$D$

AS

$3$ 
1

$P\wedge D$

$\wedge $I $1$, $2$

$4$ 
1

$(P\wedge D)\vee (P\wedge \neg D)$

$\vee $I $3$

$5$ 
close subproof,
open subproof,
1

$\neg D$

AS

$6$ 
1

$P\wedge \neg D$

$\wedge $I $1$, $5$

$7$ 
1

$(P\wedge D)\vee (P\wedge \neg D)$

$\vee $I $6$

$8$ 
close subproof,
0

$(P\wedge D)\vee (P\wedge \neg D)$

LEM $2$–$4$, $5$–$7$

Here is another example:
Line number

Subproof level

Formula

Justification


$1$ 
0

$A\to \neg A$

PR

$2$ 
open subproof,
1

$A$

AS

$3$ 
1

$\neg A$

$\to $E $1$, $2$

$4$ 
close subproof,
open subproof,
1

$\neg A$

AS

$5$ 
1

$\neg A$

R $4$

$6$ 
close subproof,
0

$\neg A$

LEM $2$–$3$, $4$–$5$

19.5 De Morgan Rules
Our final additional rules are called De Morgan’s Laws (named after Augustus De Morgan). The shape of the rules should be familiar from truth tables.
The first De Morgan rule is:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$($}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\wedge $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$)$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\vee $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$

DeM $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$

The second De Morgan is the reverse of the first:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\vee $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$($}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\wedge $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$)$}$

DeM $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$

The third De Morgan rule is the dual of the first:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$($}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\vee $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$)$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\wedge $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$

DeM $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$

And the fourth is the reverse of the third:
Line number

Subproof level

Formula

Justification


$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$ 
0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\wedge $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$


0

$\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\neg $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$($}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\vee $}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$)$}$

DeM $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$m$}$

These are all of the additional rules of our proof system for TFL.
Practice exercises
A. The following proofs are missing their citations (rule and line numbers). Add them wherever they are required:

1.Line numberSubproof levelFormulaJustification
$1$ 0$W\to \neg B$$2$ 0$A\wedge W$$3$ 0$B\vee (J\wedge K)$$4$ 0$W$$5$ 0$\neg B$$6$ 0$J\wedge K$$7$ 0$K$ 
2.Line numberSubproof levelFormulaJustification
$1$ 0$L\leftrightarrow \neg O$$2$ 0$L\vee \neg O$$3$ open subproof, 1$\neg L$$4$ 1$\neg O$$5$ 1$L$$6$ 1$\perp $$7$ close subproof, 0$\neg \neg L$$8$ 0$L$ 
3.Line numberSubproof levelFormulaJustification
$1$ 0$Z\to (C\wedge \neg N)$$2$ 0$\neg Z\to (N\wedge \neg C)$$3$ open subproof, 1$\neg (N\vee C)$$4$ 1$\neg N\wedge \neg C$$5$ 1$\neg N$$6$ 1$\neg C$$7$ open subproof, 2$Z$$8$ 2$C\wedge \neg N$$9$ 2$C$$10$ 2$\perp $$11$ close subproof, 1$\neg Z$$12$ 1$N\wedge \neg C$$13$ 1$N$$14$ 1$\perp $$15$ close subproof, 0$\neg \neg (N\vee C)$$16$ 0$N\vee C$
B. Give a proof for each of these arguments:

1.
$E\vee F$, $F\vee G$, $\neg F\therefore E\wedge G$

2.
$M\vee (N\to M)\therefore \neg M\to \neg N$

3.
$(M\vee N)\wedge (O\vee P)$, $N\to P$, $\neg P\therefore M\wedge O$

4.
$(X\wedge Y)\vee (X\wedge Z)$, $\neg (X\wedge D)$, $D\vee M\therefore M$