3
$\begingroup$

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?

$\endgroup$
5
  • $\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$ Sep 21, 2012 at 23:02
  • $\begingroup$ I edited to make it more clear $\endgroup$
    – ಠ_ಠ
    Sep 21, 2012 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$ Sep 21, 2012 at 23:21
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Karnaugh_map $\endgroup$ Sep 21, 2012 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, 2012 at 0:29

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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