2

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.

2

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

1

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
-2

In philosophy I was taught rules of inference. The proof is short as this: 1. ~(p -> ~q). Premise given 2. ~ (~p V ~q) Material implication rule 3. ~ ~ p & ~ ~ q Demorgan's theorem rule 4. P & Q. Double negation rule & conclusion reached.

Solved.

  • 1
    Did you read the question carefully? He doesn't have DeMorgan. – virmaior Oct 21 '17 at 3:29

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.