1
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$
    – LuxuryMode
    Commented Jun 25, 2021 at 4:50
  • $\begingroup$ Yes, well, to be precise using the rule of: $\phi\vee(\phi\wedge\psi)\equiv \phi$ . $\endgroup$ Commented Jun 25, 2021 at 4:56
  • $\begingroup$ Oh apologies, that is what I meant. Thank you! $\endgroup$
    – LuxuryMode
    Commented Jun 25, 2021 at 4:58
  • $\begingroup$ 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. $\endgroup$ Commented Jun 25, 2021 at 5:01
  • $\begingroup$ Right because in our case we have $((\lnot p \land \lnot q) \vee \lnot p)$ $\endgroup$
    – LuxuryMode
    Commented Jun 25, 2021 at 5:05
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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