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

Question

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

https://i.stack.imgur.com/1zMnZ.jpg

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?

Mauro ALLEGRANZA · Accepted Answer · 2016-03-09T10:35:56.900

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.

edited Mar 09 '16 at 10:35

answered Mar 09 '16 at 07:07

Mauro ALLEGRANZA

35,764
3
35
79

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

score 0 · Answer 2 · answered Mar 08 '16 at 23:18

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

George Chen · Answer 3 · 2016-10-23T01:02:28.943

0

Hint:

P -> Q ≡ ~Q -> ~P

Thus

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

(P-> ~Q) ^ (~Q -> ~P)  ⇒ P -> ~P

edited Oct 23 '16 at 01:02

answered Oct 22 '16 at 23:17

George Chen

2,178
1
13
23

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

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

3 Answers3