# Final steps to show that ($\lnot$q $\implies$ p) $\implies$ (p $\implies$ $\lnot$q) $\equiv$ ($\lnot$p $\lor$ $\lnot$q)

I am working on a problem which asks us to take the following compound proposition and use the conditional-disjunction equivalence (which states that $$p \implies q$$ and $$\lnot p \lor q$$ are logically equivalent) to find an equivalent proposition that does not involve conditionals.

The compound proposition is:

$$(\lnot q \implies p) \implies (p \implies \lnot q)$$

I approached this is as follows:

First we apply the conditional-disjunction equivalence to $$(\lnot q \implies p)$$ which yields:

$$\lnot(\lnot q) \lor p$$ which, by the double negation law, is $$q \lor p$$

Then applying the conditional-disjunction equivalence to the right side of the conditional $$(p \implies \lnot q)$$, we have:

$$\lnot p \lor \lnot q$$

At this point we have:

$$(q \lor p) \implies (\lnot p \lor \lnot q)$$

Applying the equivalence to the entire proposition, we have:

$$\lnot(q \lor p) \lor (\lnot p \lor \lnot q)$$

The answer provided in the book is that the compound proposition $$(\lnot q \implies p) \implies (p \implies \lnot q)$$ expressed without conditionals is:

$$\lnot p \lor \lnot q$$

I don't understand why we can simply get rid of the left-hand side of the disjunction in $$\lnot(q \lor p) \lor (\lnot p \lor \lnot q)$$ and end up with simply $$\lnot p \lor \lnot q$$

I created a truth table and confirmed that, indeed $$\lnot(q \lor p) \lor (\lnot p \lor \lnot q)$$ and $$\lnot p \lor \lnot q$$ agree in all cases, but I still don't understand it or how we got there. Is there some logic to this or some equivalence at use here from which we could have deduced this? I am just not seeing why the restated proposition is $$\lnot p \lor \lnot q$$ and not $$\lnot(q \lor p) \lor (\lnot p \lor \lnot q)$$

What are the final steps I am missing here?

Appreciate any insights. Thanks.

You have reached: $$\lnot (p\vee q)\vee(\lnot p\vee\lnot q)$$

Use deMorgan's Rule: $$(\lnot p\wedge\lnot q)\vee(\lnot p\vee\lnot q)$$

Use associativity: $$((\lnot p\wedge\lnot q)\vee\lnot p)\vee\lnot q$$

Remove the redundancy: $$\lnot p\vee\lnot q$$

$$\tiny{(\lnot p\wedge \lnot q)\vee \lnot p\\(\lnot p\wedge\lnot q)\vee(\lnot p\wedge\top)\\\lnot p\wedge(\lnot q\vee\top)\\\lnot p\wedge\top\\\lnot p}$$

• Oh beautiful, thank you. That last step of removing the redundancy is by the absorption law which states that $p \land (p \lor q) \equiv p$? Commented Jun 25, 2021 at 4:50
• Yes, well, to be precise using the rule of: $\phi\vee(\phi\wedge\psi)\equiv \phi$ . Commented Jun 25, 2021 at 4:56
• Oh apologies, that is what I meant. Thank you! Commented Jun 25, 2021 at 4:58
• Not a problem. Both are absorption laws - they do come in pairs after all - but its the disjunctive absorption rule that we use in this case. Commented Jun 25, 2021 at 5:01
• Right because in our case we have $((\lnot p \land \lnot q) \vee \lnot p)$ Commented Jun 25, 2021 at 5:05

So you've finally reached $$\neg(q\lor{p})\lor(\neg{p}\lor{\neg{q}})$$ you can use demorgans law to say that $$\neg(q\lor{p})\iff(\neg{q}\land\neg{p})$$ and you can finish from there.