5

I am so close to solving this problem: (Language Logic and Proof 8.36).

http://imgur.com/a/nzYCU

All I need to do to complete the proof is show that P <-> Q and P -> ~Q is a contradiction (the problem has a similar form to this)

How can I do this? Intuitively, P <-> Q is (P -> Q) ^ (Q -> P) which can be translated to

(~P V Q) ^ (~Q V P) and that

P->~Q has this form (~P V ~Q) which is not equivalent to either of the above expressions (let alone both of them!).

Am I missing something really obvious? Is there another way to complete this problem?

9

We cannot derive a contradiction from P ↔ Q and P → ¬Q, because the the two formuale are simultaneously satisfiable.

It is enough to consider a truth assignment v such that:

v(P)=v(Q)=false.

  • Gotcha! That's where the intuition (when I tried the neg. intro) was pointing to. – Jerry Qu Mar 10 '16 at 16:40
0

We have P <-> Q and P -> ~Q, and we want to derive a contradiction.

Maybe you could try to show ~(P <-> Q)?

One suggestion here might be to try supposing P.

Then we have ~Q by detachment, implying ~(P -> Q) -- which looks like possibly a counterexample to P <-> Q, maybe helping to get you to ~(P <-> Q)?

0

Hint:

P -> Q ≡ ~Q -> ~P          

Thus

If P -> ~Q, then by Syllogism we have:

(P-> ~Q) ^ (~Q -> ~P)  ⇒ P -> ~P
  • 1
    True but P -> ~P is not a contradiction. It is satisfiably true when P is false. P ^ (P -> ~P) would be a contradiction. – virmaior Oct 23 '16 at 3:15
  • @virmaior - Good point. Strictly speaking, ~P^P is called a contradiction, and yes it is not the same as P -> ~P. – George Chen Oct 23 '16 at 13:15
  • 1
    P -> ~P is simply a proof of not ~P. There's no contradiction involved. – virmaior Oct 23 '16 at 13:44
  • @virmaior - ~P v ~P. Excellent point. – George Chen Oct 23 '16 at 13:46

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.