1

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,
  • reductio ad absurdum,
  • conditional proof,
  • v-introduction,
  • v-elimination,
  • and introduction,
  • and elimination.

Tomassi's proof consists of 14 steps.

Thanks for the help.

3
  • 1
    You cannot..... Oct 8, 2018 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).
    – virmaior
    Oct 8, 2018 at 15:07
  • @virmaior I'm sorry, I missed a negation symbol in the premise. Oct 8, 2018 at 15:19

2 Answers 2

0

Here is first a proof using Klement's proof checker to make sure I have a correct proof.

enter image description here

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)

0
2

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].

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .