# 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
$m$
0
$\mathscr{A}\vee\mathscr{B}$
$n$
0
$\neg\mathscr{A}$

0
$\mathscr{B}$
DS $m$, $n$

and

Line number
Subproof level
Formula
Justification
$m$
0
$\mathscr{A}\vee\mathscr{B}$
$n$
0
$\neg\mathscr{B}$

0
$\mathscr{A}$
DS $m$, $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
$m$
0
$\mathscr{A}\rightarrow\mathscr{B}$
$n$
0
$\neg\mathscr{B}$

0
$\neg\mathscr{A}$
MT $m$, $n$

As usual, the premises may occur in either order, but we always cite the conditional first.

## 19.3 Double-negation elimination

Another useful rule is double-negation elimination. It does exactly what it says on the tin:

Line number
Subproof level
Formula
Justification
$m$
0
$\neg\neg\mathscr{A}$
0
$\mathscr{A}$
DNE $m$

The justification for this is that, in natural language, double-negations 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
$i$
open subproof, 1
$\mathscr{A}$
AS
$j$
1
$\mathscr{B}$
$k$
close subproof, open subproof, 1
$\neg\mathscr{A}$
AS
$l$
1
$\mathscr{B}$

close subproof, 0
$\mathscr{B}$
LEM $i$$j$, $k$$l$

The rule is sometimes called the law of excluded middle, since it encapsulates the idea that $\mathscr{A}$ may be true or $\neg\mathscr{A}$ may be true, but there is no middle way where neither is true.11 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:

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

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\rightarrow\neg A$
PR
$2$
open subproof, 1
$A$
AS
$3$
1
$\neg A$
$\rightarrow$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
$m$
0
$\neg(\mathscr{A}\wedge\mathscr{B})$

0
$\neg\mathscr{A}\vee\neg\mathscr{B}$
DeM $m$

The second De Morgan is the reverse of the first:

Line number
Subproof level
Formula
Justification
$m$
0
$\neg\mathscr{A}\vee\neg\mathscr{B}$

0
$\neg(\mathscr{A}\wedge\mathscr{B})$
DeM $m$

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

Line number
Subproof level
Formula
Justification
$m$
0
$\neg(\mathscr{A}\vee\mathscr{B})$

0
$\neg\mathscr{A}\wedge\neg\mathscr{B}$
DeM $m$

And the fourth is the reverse of the third:

Line number
Subproof level
Formula
Justification
$m$
0
$\neg\mathscr{A}\wedge\neg\mathscr{B}$

0
$\neg(\mathscr{A}\vee\mathscr{B})$
DeM $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. 1.
Line number
Subproof level
Formula
Justification
$1$
0
$W\rightarrow\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. 2.
Line number
Subproof level
Formula
Justification
$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
$\bot$
$7$
close subproof, 0
$\neg\neg L$
$8$
0
$L$
3. 3.
Line number
Subproof level
Formula
Justification
$1$
0
$Z\rightarrow(C\wedge\neg N)$
$2$
0
$\neg Z\rightarrow(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
$\bot$
$11$
close subproof, 1
$\neg Z$
$12$
1
$N\wedge\neg C$
$13$
1
$N$
$14$
1
$\bot$
$15$
close subproof, 0
$\neg\neg(N\vee C)$
$16$
0
$N\vee C$

B. Give a proof for each of these arguments:

1. 1.

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

2. 2.

$M\vee(N\rightarrow M)\therefore\neg M\rightarrow\neg N$

3. 3.

$(M\vee N)\wedge(O\vee P)$, $N\rightarrow P$, $\neg P\therefore M\wedge O$

4. 4.

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