Conditional-disjunction equivalence:

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

To show:

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


$\lnot$($\lnot$q $\implies$ p) $\lor$ (p $\implies$ $\lnot$q) by conditional-disjuction equivalence

$\equiv$ $\lnot$($\lnot$($\lnot$q) $\lor$ p) $\lor$ ($\lnot$p $\lor$ $\lnot$q) by conditional-disjunction equivalence

$\equiv$ $\lnot$(q $\lor$ p) $\lor$ ($\lnot$p $\lor$ $\lnot$q) by double negation law

$\equiv$ ($\lnot$q $\land$ $\lnot$p) $\lor$ ($\lnot$p $\lor$ $\lnot$q) by DeMorgan law

I am stuck at the last step.


You are nearly there.

$(\neg q\wedge\neg p)\vee(\neg p\vee\neg q)\equiv[(\neg q\wedge\neg p)\vee\neg p]\vee\neg q$ by the associativity of $\vee$.

$\color{red}{[(\neg q\wedge\neg p)\vee\neg p]}\vee\neg q\equiv\neg p\vee \neg q$ by absorption on the red term.

  • $\begingroup$ I Never saw ($\lnot$q $\lor$ $\lnot$p) as a single term to which the a law can be applied. Thank you. $\endgroup$ – Haslo Vardos Nov 7 '20 at 11:10
  • $\begingroup$ If you are satisfied with my answer consider accepting it by clicking the tick-mark button next to it. $\endgroup$ – Shubham Johri Nov 7 '20 at 11:11

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.