The question asked me to prove the following equivalence. $$(r \rightarrow p)\rightarrow (p\land q)\equiv (\lnot r \rightarrow p)\land(\lnot r \rightarrow q)\land (p \rightarrow q)$$

And I did the followings:

For L.H.S., $(r\rightarrow p)\rightarrow (p\land q)\\\equiv \lnot (\lnot r\lor p)\lor (p\land q)\\ \equiv (r \land \lnot p) \lor (p \land q)$

For R.H.S., $(\lnot r \rightarrow p)\land(\lnot r \rightarrow q)\land (p \rightarrow q)\\ \equiv (r\lor p) \land (r \lor q) \land (\lnot p \lor q)\\ \equiv (r\lor (p\land q))\land (\lnot p\lor q)\\ $

Now, I'm a bit stuck as to how to show that LHS = RHS.

  • 2
    $\begingroup$ This is not a do my homework for me site. Please add your own workings into the post. It's okay if you get stuck midway through, but you do need to show us that you're willing to meat us half-way. $\endgroup$ – Namaste Apr 21 '18 at 17:38
  • $\begingroup$ Lol actually I've been working on it and I think I did it in a wrong way so I decided not to post that up here $\endgroup$ – Cluyeia Apr 21 '18 at 17:40
  • $\begingroup$ The left hand side is equivalent to $\lnot (\lnot r\lor p)\lor (p\land q)$. Why? Then this is equivalent to $(r \land \lnot p) \lor (p \land q).$ Why. Show me some of your work on the right-hand side? $\endgroup$ – Namaste Apr 21 '18 at 17:41
  • $\begingroup$ Cluyeia It will help us understand the mistakes you may have made, so we can better help you. So please include your workings, right or wrong. And how do you know they are wrong? $\endgroup$ – Namaste Apr 21 '18 at 17:44
  • $\begingroup$ The R.H.S is equivalent to $(r\lor p)\land (r\lor q)\land (\lnot p\lor q)$ and it’s equivalent to $(r\lor (p\land q))\land (\not p\lor q)$ right? $\endgroup$ – Cluyeia Apr 21 '18 at 17:46

I’ve done the proof and here is the answer.
L.H.S. = $ (r\rightarrow p)\rightarrow (p\land q)\\ \equiv \lnot (\lnot r\lor p)\lor (p\land q)\\ \equiv (r \land \lnot p) \lor (p \land q)\\ \equiv (r\lor p)\land (\lnot p \lor p)\land (r\lor q)\land (\lnot p \lor q)\\ \equiv(r\lor p)\land T\land (r\lor q)\land(\lnot p\lor q)\\ \equiv(\lnot r\rightarrow p)\land (\lnot r\rightarrow q)\land (p\rightarrow q)\\ \equiv R.H.S. $

Thx for all your helps !

  • $\begingroup$ Excellent, Cluyeia! Your answer is correct!. Now, please feel free to accept your answer as direct and correct! (Just click on the grey arrow to the left of your answer. When you click on it, it will turn green.) Don't be bashful; If I had asked the question, I would accept your answer! $\endgroup$ – Namaste Apr 21 '18 at 22:23

After writing out the left hand side using $\;\phi \rightarrow \psi \;\equiv\; \lnot \phi \lor \psi\;$ and DeMorgan, it is an $\;\lor\;$ of $\;\land\;$'s. Similarly, the right hand side becomes a $\;\land\;$ of $\;\lor\;$'s.

How do you get from one to the other? Through distribution.

So you choose one of the two sides, and distribute $\;\land\;$ over $\;\lor\;$, or $\;\lor\;$ over $\;\land\;$, and work towards the other side.

After you completed the proof, look up conjunctive normal form and disjunctive normal form and see how those terms relate to your proof.

  • $\begingroup$ Thanks I’ve done it ;-] $\endgroup$ – Cluyeia Apr 21 '18 at 19:26

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.