# How to prove ~ (~P & ~Q) : P ∨ Q by natural deduction

Here's another of Tomassi's exercises I can't solve (Logic, page 106):

~ (~P & ~Q) : P ∨ Q

I have to use natural deduction and the only rules I know are:

• assumptions,
• modus ponendo ponens,
• modus tollendo tollens,
• double negation,
• conditional proof,
• v-introduction,
• v-elimination,
• and introduction,
• and elimination.

Tomassi's proof consists of 14 steps.

Thanks for the help.

• You cannot..... Oct 8 '18 at 15:06
• Either I can't decipher what you mean by : or this is not provable. (I assumed ~P & ~Q is your premise and P v Q is your desired conclusion). Oct 8 '18 at 15:07
• @virmaior I'm sorry, I missed a negation symbol in the premise. Oct 8 '18 at 15:19

Here is first a proof using Klement's proof checker to make sure I have a correct proof. Using Tomassi's formatting, this proof might look like the following:

```¬(¬P & ¬Q) ⊢ P v Q
{1}      1.  ¬(¬P ∧ ¬Q)              Premise
{2}      2.  ¬(P v Q)                Assumption for RAA
{3}      3.  P                       Assumption for RAA
{3}      4.  P v Q                   3 vI (right-hand)
{2,3}    5.  ¬(P v Q) & (P v Q)      2,4 &I
{2}      6.  ¬P                      3,5 RAA
{7}      7.  Q                       Assumption for RAA
{7}      8.  P v Q                   7 vI (left-hand)
{2,7}    9.  ¬(P v Q) & (P v Q)      2,8 &I
{2}     10.  ¬Q                      7,9 RAA
{2}     11.  ¬P & ¬Q                 6,10 &I
{2}     12.  ¬(¬P & ¬Q) & (¬P & ¬Q)  1,11 &I
{1}     13.  ¬¬(P v Q)               2,12 RAA
{1}     14.  P v Q                   13 DNE
```

The strategy is to assume the negative of what one wants to prove, derive a contradiction and then by reduction ad absurdum (RAA) reach the desired answer. That is also done with two subproofs, one on lines 3 through 5 and the other on lines 7 through 9.

The proof uses the following rules and the page numbers where Tomassi defines them:

• Premise-Introduction, page 48
• rule of assumption, page 59
• &-introduction (and-introduction), page 49
• right handed vIntroduction, page 84
• left handed vIntroduction, page 84
• negation introduction (RAA), page 102-3
• double negation-elimination (DNE), page 79

These rules are all defined earlier than page 106 where the exercise appeared. I may have got the dependencies wrong (column 1) or other parts since these were manually inserted.

Reference

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

Tomassi, P Logic (1999)

The argument schema is not valid; check it with both P and Q false.

Thus, we cannot prove that (¬P & ¬Q) : P v Q.

What we can prove is : ¬(¬P & ¬Q) : P v Q.

Hint

1) ¬P --- assumed [a]

2) ¬Q --- assumed [b]

3) ¬(P v Q) --- assumed [c]

4) from 1) and 2) and the premise we get a contradiction, deriving P by Double Negation and discharging [a]

5) P v Q --- from 4)

6) a new contradiction from 3) and 5), deriving Q by Double Negation and discharging [b]

7) P v Q --- from 6)

8) a new contradiction from 3) and 7), deriving P v Q by Double Negation and discharging [c].