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

Question

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.

Answer 1

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}$$

Answer 2

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.