2
$\begingroup$

So I am working on logical equivalences for the first time and it was all making sense, until I was given the exercise:

Verify the following equivalence by writing an equivalence proof. That is, start on one side and use known equivalences to get to the other side. $(p \to q) \land (p \lor q) ≡ q$.

I am aware of the various laws, however in what order do I apply these laws? Is there an order? If there is not an order then what are the steps to take in order to prove the equivalence?

$\endgroup$
  • 1
    $\begingroup$ It's not entirely clear to me what you mean, but have you tried replacing $(p\to q)$ by $(\neg p \vee q)$ and then apply a distributivity law ? $\endgroup$ – Mathieu Huot Feb 6 '18 at 17:44
  • $\begingroup$ I am mainly wanting to know if there is a formula to proof an equivalence or do I just have to compare already known logical equivalences? $\endgroup$ – Danny Sanderson Feb 6 '18 at 17:53
  • $\begingroup$ What have you tried so far? What are the various laws you're aware of? It's not the purpose of this forum to just dump your problems for others to solve - especially when you don't share information about what you actually know about the problem so far. $\endgroup$ – skyking Feb 6 '18 at 17:54
  • 1
    $\begingroup$ Associative, distribute, identity, negation, double negation, idempotent, De Morgans. Sorry that my post isn't up to your standards, skyking. I do not want this exercise solved for me, I simply want to know how I can solve it myself. $\endgroup$ – Danny Sanderson Feb 6 '18 at 17:58
4
$\begingroup$

\begin{align} (p \to q) \land (p \lor q) &\equiv (\lnot p \lor q) \land (p \lor q) &&\text{classical definition of }\to \\ &\equiv (\lnot p \land p) \lor q &&\text{distributivity of } \lor \text{ over } \land \\ &\equiv \bot \lor q \equiv q \end{align} where $\bot$ is the absurdity, i.e. a proposition that is always false.

$\endgroup$

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.