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

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.

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

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

• I've never learned about truth tables before, or even know how you construct one, so my apologies for not specifying the method I was looking for this sequent to be proved with. I'm unsure about the rule you used on line 4 and 9 (it could be something I haven't used before) and I don't know how you assumed ~P (is that RAA? or something else?) on line 2. I also updated the original post with the rules I know. – logic09 Jan 17 '16 at 5:32
• 4 and 9 is material implication en.wikipedia.org/wiki/Material_implication_(rule_of_inference) . 2 is just like 1. We are making an assumption (thus the "A") and the new vertical line ("|") symbolizes a sub-argument. – virmaior Jan 17 '16 at 5:46
• @logic09 same thing without material implication (see edit). I'm not understanding your issue regarding assumptions, we can always assume within a sub-argument (here marked by | ). I don't know how you could do reductio ad absurdum or conditional proof without some syntax for sub arguments (there are too many for me to list them all). – virmaior Jan 17 '16 at 6:16
• The truth table should have additional columns showing in steps how to arrive at the truth values for the compound statement. I would put between $Q$ and $~(P -> ~Q)$ the following 2 steps $~Q$, $P -> ~Q$. Then as long as you know the truth values for negation and implication on given input you can build the desired column. – j0equ1nn Jan 21 '16 at 21:05
• I guess that could make it clearer but it's not actually necessary on technical level. (now added). – virmaior Jan 21 '16 at 21:55

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.

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/