Working with Negation Introduction and Elimination

        In the introduction we provided some examples of ~I. But recall that it and ~E differ from conditional proof in that you can only apply the rule if the last line of the subderivation is an explicit contradiction. And what you obtain if you apply ~I is the negation of the assumption you have made. Here we will study negation introduction in more detail. Recall that it is also a mode of proof. When you apply it you are appealing to the subderivation as a whole, not simply to the two lines you highlight in the builder. The builder indicates this by placing a '-' rather than a ',' between the numbers of the two lines that you highlighted. Once an assumption has been discharged the lines in the subderivation are inaccessible. Generally, though not invariably, you will set up a negation introduction when you the sentence you are trying to derive is something other than a conditional or biconditional, or when you have need of something other than a conditional or a biconditional as a step along the way toward your conclusion. Let's start off with an easy one:

Go to Lesson 1

Here are the premises we will use in a more complex derivation:

1.
2.
3.

~(P v Q)
R -› P
R v Q

Premise
Premise
Premise


Let us suppose that we are trying to show that ~(P v Q), R -› P, R v Q I- Q. Note that if we were to have ~R as an accessible line then we could obtain the conclusion we want via an application of DS. We could obtain ~R were we to have ~P. So we shall obtain ~P via negation introduction. Here is one completed derivation:

1.
2.
3.
4.
5.
6.
7.
8.
9.

~(P v Q)
R -› P
R v Q
     P
     P v Q
     (P v Q) & ~(P v Q)
~P
~R
Q

Premise
Premise
Premise
* A
* 4 vI
* 4, 5 &I
4-6 ~I
2, 7 MT
3, 8 DS


This is a fairly long derivation but it is straightforward. But there is another way. Let us still suppose that we are trying to show that ~(P v Q), R -› P, R v Q I- Q. Since we want Q let us assume ~Q. ~I would give us ~~Q, but we could get Q via ~~E. Or you could use ~E. Here is one completed derivation where we use ~I:

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

~(P v Q)
R -› P
R v Q
     ~Q
     R
     P
     P v Q
     (P v Q) & ~(P v Q)
~~Q
Q

Premise
Premise
Premise
* A
* 3, 4 DS
* 2, 5 -›E
* 6 vI
* 1, 7 &I
* 4-8 ~I
9 ~~E


You should now:

Go to Lesson 2

        Here is another example. You wish to show that P ‹-› Q, ~(~P v R), Q › ~A, W -› A I- ~W. In this case we will proceed by initially assuming W. The derivation will be long, but nonetheless not difficult.

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

P ‹-› Q
~(~P v R)
Q -› ~A
W -› A
     W
     A
     ~~A
     ~Q
     (P -› Q) & (Q -› P)
     (P -› Q)
     ~P
     ~P v R
     (~P v R) & ~(~P v R)
~W

Premise
Premise
Premise
Premise
* A
* 4, 5 -›E
* 6 ~~I
* 3, 7 MT
* 1 ‹-›I,E
* 9 &E
* 8, 10 MT
* 11 vI
* 2, 12 &I
5-13 ~I


We said that this derivation was long, but not difficult. The justification for the claim that it is not difficult is simply that, for the most part, after we made our assumption we completed it by applying rules that we could. You should now:

Go to Lesson 3


        ~E, negation elimination, works in fundamentally the same way. But it can only be applied if the assumption is some negation ~p. Here is a very simple example where we show that ~(~P v A) |- P.

1.
2.
3.
4.
5.

~(~P v A)
     ~P
     ~P v A
     (~P v A) & ~(~P v A)
P

Premise
* A
* 2 vI
* 1, 3 &I
2-4 ~E


Here is a slightly longer but easy derivation that uses a ~E along the way:

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

R -› (~P ‹-› Q)
~(~R v A) & ~P
~(~R v A)
~P
     ~R
     ~R v A
     ~(~R v A) & (~R v A)
R
~P ‹-› Q
(~P -› Q) & (Q -› ~P)
~P -› Q
Q

Premise
Premise
2 &E
2 &E
* A
* 5 vI
* 3, 6 &I
5-7 ~E
1, 8 -›E
9 ‹-›E
10 &E
4, 11 -›E


You should now:

Go to Lesson 4

Before turning to the next section let us try one more. You should now:

Go to Lesson 5


Next Section- on Multiple Assumptions      Negation Introduction Exercises      Main Menu