$\begingroup$

I'm trying to show that P→Q ≡ (P∧¬Q)→(Q∧¬Q)

I think I've shown it, but am not 100% sure all my steps are legal.

(P∧¬Q)→(Q∧¬Q)

 Step 1) ¬(P∧¬Q) ∨ (Q∧¬Q) (conditional law) Step 2) (¬P∨Q) ∨ (Q∧¬Q) (deMorgan's law) Step 3) ¬P∨Q ∨ Q∧¬Q (removing parthenses) Step 4) P∨Q∧¬Q (idempotent law) Step 5) Q ∨ (P∧¬Q) (commutative law) Step 6) (Q∨¬P)∧ (Q∨¬Q) (distribution law) Step 7) (Q∨¬P) (tautology law) Step 8) P → Q (conditional law) 

My question is weather or not step 5 is legal. Can I just invoke the commutative law, and group with parenthesis any way I choose?

$\endgroup$

2 Answers

$\begingroup$

The proof is not correct, starting in step 3). You may not have an expression $P\vee Q \wedge R$ since it is not clear what it means without parentheses. That is $P\vee (Q\wedge R)$ is not the same thing as $(P \vee Q)\wedge R$.

Rather in step 3) note that $Q\wedge \neg Q \equiv \bot$ and thus $(\neg P\wedge Q) \vee (Q\wedge \neg Q) \equiv (\neg P\wedge Q)\vee \bot \equiv (\neg P \wedge Q) \equiv P\rightarrow Q$

$\endgroup$ $\begingroup$

5 is illegal. The grouping is wrong. $(A\vee B)\wedge C \neq A\wedge(B\vee C)$

It follows the deMorgan's law: $(A\vee B)\wedge C = (A\wedge C)\vee(B\wedge C)$

In addition, step 3 is already wrong.

$(A\vee B)\vee C = A\vee(B\vee C), (A\wedge B)\wedge C = A\wedge(B\wedge C)$ (Associative Law)

$(A\vee B)\wedge C = (A\wedge C)\vee(B\wedge C), (A\wedge B)\vee C = (A\vee C)\wedge(B\vee C)$ (deMorgan's law)

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy