2

I'm reading How to Prove It: A Structured Approach (Velleman) Second Ed.

Doing all the end of chapter exercises for chapter 1 and having trouble on problem 5a which reads

Show that $P \leftrightarrow Q$ is equivalent to $(P \wedge Q) \vee (\neg P \wedge \neg Q)$

Clearly they're equivalent to each other based on the truth tables. But is that really the best way to 'show' it? I was able to derive the second form from the first in all the other questions that asked to show two forms are equivalent so far.

Here's what happens when I try to derive it:

$$P \leftrightarrow Q$$ $$ \text{Form of biconditional} $$ $$(P \rightarrow Q) \wedge (Q \rightarrow P)$$ $$ \text{Form of conditional}$$ $$ (\neg P \vee Q) \wedge (\neg Q \vee P)$$

From here it appears to match the form of a distributive law but with mismatched negations. I just don't know where to go from here...

Obrazi
  • 23

1 Answers1

1

So far, so good. To continue...

$\vdots \\ (\neg P \vee Q)\wedge (\neg Q\vee P) \\ \Updownarrow (\text{Distribute})\\ (\neg P\wedge (\neg Q\vee P)) \vee (Q\wedge (\neg Q\vee P)) \\ \Updownarrow (\text{Distribute, twice})\\ (\neg P\wedge \neg Q)\vee(\neg P\wedge P)\vee (Q\wedge \neg Q)\vee (Q\wedge P) \\ \Updownarrow \\ \vdots $

Can you see where to go from here?

Graham Kemp
  • 129,094
  • 1
    You'd remove the two contradictions because of the contradiction laws and be left with (not P && not Q) || (Q && P), then use commutative laws to arrive at exactly the answer? – Obrazi Mar 12 '15 at 01:23
  • Yes, that's correct. Are you comfortable with the distributions? – Graham Kemp Mar 12 '15 at 01:28
  • Yes I worked out your answer. I was going to edit the question mark and say thanks when my internet went out, so thanks for that. – Obrazi Mar 12 '15 at 06:16