2

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

Chappers
  • 67,606
yociyoci
  • 69

1 Answers1

1

$¬(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$.

Mauro ALLEGRANZA
  • 94,169
  • 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) – yociyoci Sep 19 '15 at 18:47
  • @yociyoci - Distributivity : $(P \land (Q \lor R)) \Leftrightarrow ((P \land Q) \lor (P \land R))$. – Mauro ALLEGRANZA Sep 19 '15 at 18:49