How to show -(P -> -Q) ⊢ P&Q?

Question

I'm unsure how to prove -(P -> -Q) ⊢ P&Q

I know I can assume -(P -> -Q) and use RAA to assume -(P&Q), but from there I'm stuck on how to proceed because of the negations on the outside of the parentheses.

edit: I also keep reading something about DeMorgan's Law, but we haven't learned that yet in class so that's not something I can use (even if it does help in solving this proof).

edit 2: the only rules I know are: assumptions, modus ponendo ponens, modus tollendo tollens, double negation, reductio ad absurdum, conditional proof, v-introduction, v-elimination, &introduction, and &elimination.

Answer 1

1) ¬(P → ¬ Q) --- premise

2) ¬(P & Q) --- assumed [a]

3) P --- assumed [b]

4) Q --- assumed [c]

5) (P & Q) --- from 3) and 4) by &introduction

6) contradicition from 2) and 5)

7) ¬Q --- from 4) and 7) by Indirect Proof, discharging [c]

8) P → ¬ Q --- from 3) and 7) by Conditional Proof, discharging [b]

9) contradicition from 1) and 8)

10) (P & Q) --- from 2) and 9) by Double Negation, discharging [a].

---

Note : for Conditional Proof and Indirect Proof, see e.g. :

• Patrick Hurley, A Concise Introduction to Logic (11th ed - 2012), page 427 and page 432.

Answer 2

As shown elsewhere on this SE, there's two general methods for proofs in sentential logic: truth tables and inference rules. Well for starters, let's just prove exhaustively that the equivalence is true using a truth table:

P | Q | ~Q  | P -> ~Q | ~(P -> ~Q) |  P & Q
--------------------------------------------
T | T |  F  |    F    |   T        |    T
T | F |  T  |    T    |   F        |    F
F | T |  F  |    T    |   F        |    F
F | F |  T  |    T    |   F        |    F

(in this truth table, I've spelled out (a) the variables involved, (b) the steps involved to build ~(P -> ~Q), (c) ~(P -> ~Q) and (d) P & Q. Intermediary steps are a pretty common feature in truth tables especially in classwork).

Given that, we know that the inference is provably, one thing that isn't at all clear from your question is which rules you do know and are allowed to use (you indicate you don't know DeMorgan's or are not allowed to use it).

Here's one proof:

1. | ~(P -> ~Q) A
2. | | ~P A
3. | | ~P v ~Q vI 2
4. | | P -> ~Q Mat. Imp 3
5. | | (P -> ~Q) & ~(P -> ~Q) &I 1,4
6. | P Contra. Elim 2-5
7. | | ~Q A
8. | | ~P v ~Q vI 7
9. | | P -> ~Q Mat. Imp 8
10. | | (P -> ~Q) & ~(P -> ~Q) &I 1,9
11. | Q Contra. Elim 7-10
12. | P & Q &I 6,11
13. ~(P- > ~Q) -> P & Q Conditional Proof 1-12

and there you go.

Edit: here's how to do material implication using conditional proof:

1. | ~(P -> ~Q) A
2. | | ~P A

3. | | ~P v ~Q vI 2

4. | | | P A

5. | | | ~~P DN 4
6. | | | ~Q vE 5,3
7. | | P -> ~Q CP 4-6

... (repeat for the other one and adjust line numbers).

Answer 3

The OP notes the following:

I know I can assume -(P -> -Q) and use RAA to assume -(P&Q), but from there I'm stuck on how to proceed because of the negations on the outside of the parentheses.

Also the OP does not have De Morgan's laws.

Here is a proof that gets around using an indirect proof on -(P&Q), by doing two indirect proofs, first on ~P and then on ~Q.

---

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

Answer 4

I know I can assume -(P -> -Q) and use RAA to assume -(P&Q), but from there I'm stuck on how to proceed because of the negations on the outside of the parentheses.

That's a good start. Just continue on in the same vein.

 |_ ¬(P → ¬Q)        Premise
 |  |_ ¬(P & Q)      Assumption
  :  :  :
 |  |  #             ¬ Elimination
 |  ¬¬(P & Q)        ¬ Introduction  }
 |  P & Q            ¬¬ Elimination  }= Reduction to Absurdity

Your target is to derive a contradiction from assuming ¬(P → ¬Q) and ¬(P & Q). Well, those are the only things you have to contradict so obviously you need to derive either P → ¬Q or P & Q (maybe both, along the line).

Clearly you might derive P → ¬Q by a conditional proof: where you further assume P aiming to derive ¬Q, if possible.

 |_ ¬(P → ¬Q)        Premise
 |  |_ ¬(P & Q)      Assumption
 |  |  |_ P          Assumption
  :  :  :  :
 |  |  |  ¬Q         ¬ Introduction
 |  |  P → ¬Q        → Introduction
 |  |  #             ¬ Elimination
 |  ¬¬(P & Q)        ¬ Introduction  }
 |  P & Q            ¬¬ Elimination  }= Reduction to Absurdity

Well, now, how could you prove that negation of Q? Of course, by further assuming Q aiming to derive the other contradiction P & Q, ie a proof of negation !

 |_ ¬(P → ¬Q)        Premise
 |  |_ ¬(P & Q)      Assumption
 |  |  |_ P          Assumption
 |  |  |  |_ Q       Assumption
 |  |  |  |  P & Q   & Introduction
 |  |  |  |  #       ¬ Elimination
 |  |  |  ¬Q         ¬ Introduction
 |  |  P → ¬Q        → Introduction
 |  |  #             ¬ Elimination
 |  ¬¬(P & Q)        ¬ Introduction  }
 |  P & Q            ¬¬ Elimination  }= Reduction to Absurdity

Done.