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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.