I need help with proving $\neg a \vee b$ is logically equivalent to $$ \neg (((a \vee b) \wedge \neg (a \wedge b)) \wedge (a \vee ~b)) $$ by using logical equivalence law. I have tried multiple times but I can't seem to simplify them further than $$ \neg (a \vee b) \vee (a \wedge b) \vee \neg (a \vee \neg b)$$


$¬(a∨b)∨(a∧b)∨¬(a∨¬b) = (\lnot a \land \lnot b) \lor (a \land b) \lor (\lnot a \land b) = [(\lnot a \land \lnot b) \lor (\lnot a \land b)] \lor (a \land b) = [\lnot a \land (\lnot b \lor b)] \lor (a \land b) = [\lnot a \land T] \lor (a \land b) = \lnot a \lor (a \land b) = (\lnot a \lor a ) \land (\lnot a \lor b) = T \land (\lnot a \lor b) = (\lnot a \lor b)$.

In addition to De Morgan, you need Distributivity and : $x \land T = x$.

  • $\begingroup$ Thank you for the quick reply. I am still a bit uncertain about how this works [(¬a∧¬b)∨(¬a∧b)]∨(a∧b)=[¬a∧(¬b∨b)]∨(a∧b) $\endgroup$ – yociyoci Sep 19 '15 at 18:47
  • $\begingroup$ @yociyoci - Distributivity : $(P \land (Q \lor R)) \Leftrightarrow ((P \land Q) \lor (P \land R))$. $\endgroup$ – Mauro ALLEGRANZA Sep 19 '15 at 18:49

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.