I have greatly simplified down a piece of boolean logic developed from a truth table, but I cannot figure out how to simplify it more. Two of the same variable exist in the different places, which leads me to believe that it can be simplified more.

$ (D \land (A \lor (\lnot C \land B))) \lor (C \land (A \lor \lnot B)) $

How can this be simplified?

  • $\begingroup$ Could you clarify what addition and multiplication signify here? You can use logical operators $\land$ and $\lor$ by using LaTeX, simply surround the statement with '\$''s and use \land and \lor. I have changed your ¬ to $\lnot$ for you. $\endgroup$ – quietContest Sep 21 '12 at 23:02
  • $\begingroup$ I edited to make it more clear $\endgroup$ – ಠ_ಠ Sep 21 '12 at 23:07
  • 1
    $\begingroup$ Put into a normal form (disjunctive or conjunctive, ands of ors or ors of ands) using De Morgan's laws and see what terms combine. $\endgroup$ – marty cohen Sep 21 '12 at 23:21
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Karnaugh_map $\endgroup$ – i. m. soloveichik Sep 21 '12 at 23:33
  • $\begingroup$ Thanks on the k-map suggestion, which I would have used if my basic level class didn't require me to work from the most complicated version of the logic based on a truth table and simplify from there... $\endgroup$ – ಠ_ಠ Sep 22 '12 at 0:29

What you want to use here is distributivity, $$p \wedge (q \vee r) \leftrightarrow (p \wedge q) \vee (p \wedge r)$$ Use this on both the left and right to deduce that your formula is equivalent to $$(D\wedge A) \vee (D\wedge \neg C \wedge B) \vee (C\wedge A) \vee (C\wedge \neg B)$$ This is called the "disjunctive normal form" of a formula, and it's often one of the two clearest ways to express one-the other is "conjunctive normal form," which you can pass to via a number of applications of de Morgan's laws and distributivity from here, getting $$(D\vee C) \wedge (A \vee \neg B\vee \neg C)\wedge (B\vee C\vee A)$$ In this case, the conjunctive form has less terms, but which form is simpler eventually comes down to a subjective question.


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.