2
$\begingroup$

I have to show that two compound statements are equivalent without using truth tables. I.e. $$(\lnot p \; \land \; (p \; \to \; q)) \; \to \; \lnot q \ \equiv \ p \; \lor \; \lnot q$$

I first start out saying the left hand side is equivalent to $$(\lnot p \; \land \; (\lnot p \; \lor \; q)) \; \to \; \lnot q$$ by implication laws.

Next we can distribute $\lnot p$ and get $$((\lnot p \; \land \; \lnot p)\; \lor \; (\lnot p \; \land \; q)) \; \to \; \lnot q$$

By the idempotent property, we get $(\lnot p \; \land \; \lnot p) \ \equiv \ \lnot p$ making the statement $$(\lnot p \lor \; (\lnot p \; \land \; q)) \; \to \; \lnot q$$

This is where my visual impairment really shows because anything I come up with sends me back to the original statement. I have verified where I'm stuck with a truth table, I just can't see any moves with equivalence laws. I am not looking to have it solved for me, just maybe a hint, or two, would greatly help.

$\endgroup$
5
  • 2
    $\begingroup$ Hint: use the fact that $A\to B\equiv (\lnot A)\lor B$ and use de Morgan's laws. $\endgroup$
    – Shaun
    Sep 17, 2021 at 20:13
  • 3
    $\begingroup$ Do you know the absorption laws? $A\lor (A \land B)$ and $A\land (A\lor B)$ are both equivalent to $A$. $\endgroup$ Sep 17, 2021 at 20:22
  • $\begingroup$ So I had asked my professor about absorption, but he said absorption would not work because of the negations. However I took a step back to get some food and was able to use implication laws to take care of the outer most implication and then used de morgan's to further break it down. $\endgroup$
    – Anonymous
    Sep 17, 2021 at 21:10
  • 1
    $\begingroup$ If you convert both implications to disjunctions, with some simplification you get$$(p \lor (p\land \neg q)) \lor \neg q$$I would suggest reviewing the properties of disjunction for the next step. $\endgroup$
    – user170231
    Sep 17, 2021 at 21:54
  • $\begingroup$ You need to share the list of logical equivalences you're allowed to use. $\endgroup$ Sep 18, 2021 at 0:22

1 Answer 1

2
$\begingroup$

If you're not allowed to use an absorption law, then, ploughing through,

$$(\lnot p \lor \; (\lnot p \; \land \; q)) \; \to \; \lnot q\\ \lnot (\lnot p \lor \; (\lnot p \; \land \; q))\lor \lnot q\\ (p\land (p\lor \lnot q))\lor \lnot q\\ (p\lor \lnot q)\land (p\lor \lnot q\lor\lnot q)\\ p\lor \lnot q\\$$

(Please fill in the missing steps as required.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .