# How can I prove a contradiction follows from P <-> Q and P -> ~Q?

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?

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

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)`?

Hint:

``````P -> Q ≡ ~Q -> ~P
``````

Thus

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

``````(P-> ~Q) ^ (~Q -> ~P)  ⇒ P -> ~P
``````
• 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
• 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