0

I have simplified a Boolean expression to $$(\lnot a \land \lnot b \land \lnot c) \lor (a \land (b \lor c)).$$ Is there any way to simplify this further, e.g. using De Morgan's or anything?

dfeuer
  • 9,069
J0FVB
  • 1
  • What do you mean by $a(b\land c)$? Do you really want $(a\land b\land c)$ here? – Brian M. Scott Nov 28 '13 at 19:20
  • Sorry, I put an "and" sign instead of an "or" sign, I've corrected it. – J0FVB Nov 28 '13 at 19:26
  • @J0FVB, you still seem to use two different notations in one expression. Should there be a symbol between $a$ and $b\lor c$? – dfeuer Nov 28 '13 at 19:28
  • It’s still not clear; are you using juxtaposition as well as $\land$ to mean and? I.e., is this $$(\neg a\land\neg b\land\neg c)\lor\big(c\land(b\lor c)\big);?$$ – Brian M. Scott Nov 28 '13 at 19:29
  • you mean a not c right? – Cruncher Nov 28 '13 at 19:31
  • 1
    @Cruncher: Yes, that was a typo. $$(\neg a\land\neg b\land\neg c)\lor\big(a\land(b\lor c)\big)$$ – Brian M. Scott Nov 28 '13 at 19:39
  • @Brian M. Scott: Yes, you are correct, I've edited the question. – J0FVB Nov 28 '13 at 19:52
  • I don't think this can really be simplified at all. Perhaps the best you can do is change the first part to: $ \neg(a\lor b\lor c) $ – Cruncher Nov 28 '13 at 19:54
  • Okay - that means I'm done (or almost done) with my simplification. Thanks. – J0FVB Nov 28 '13 at 19:58
  • You can manipulate it into other forms that might be simpler for specific purposes. For instance, $$(\neg a\land\neg b\land\neg c)\lor(a\land b)\lor(a\land c);,$$ the disjunctive normal form, might in some contexts be considered a simplification. If you have exclusive or available, which I’ll write $\oplus$, you can reduce it to $$\neg\big(a\oplus(b\lor c)\big);,$$ which some might consider a simplification. – Brian M. Scott Nov 28 '13 at 19:59
  • Yes - this is what I was looking for, I think. Thanks. – J0FVB Nov 28 '13 at 20:09
  • I'd add lastly that in circuitry these are often simplified down to using all $ \lor $ or all $ \land $ as it's cheaper to mass produce a tonne of the same logic gates. Also @BrianM.Scott I wouldn't have particularly considered xor as it's really just a shortcut for $ a\land \neg b \lor \neg a \land b $. But my heart is generally in a computer science context, where you have to implement xor in circuitry anyway. – Cruncher Nov 28 '13 at 20:10

3 Answers3

3

Your expression can no further be simplified, using only $\land,\lor, \;\text{and/or}\;\lnot$. So how you choose to present the expression depends on context and/or your preference. If you want to minimize the repetition of variables, your posted expression does so.

However, we can put the expression into one of a number of standard forms, disjunctive normal form, by merely expanding the second term, using the distributivity of conjunction over disjunction, to get:

$$(\lnot a \land \lnot b \land \lnot c) \lor (a \land (b\lor c))\equiv (\lnot a \land \lnot b \land \lnot c)\lor (a\land b) \lor (a \land c)$$

We could also reconfigurate your original post to present it in conjunctive normal form: $$(\lnot a \land \lnot b \land \lnot c) \lor (a \land (b\lor c))\equiv (\lnot a \lor b \lor c) \land (a \lor \lnot b) \land (a \lor \lnot c)$$

amWhy
  • 209,954
1

Since at the time I'm posting this, there may be a typo in the question, I'm taking the expression to be simplified to be $ (\neg a\land\neg b\land\neg c)\lor\big(a\land(b\lor c)\big) $.

Doing the prior simplification:$(\neg a\land\neg b\land\neg c)\lor\big(a\land(b\lor c)\big)=(\neg a\land\neg b\land\neg c)\lor\big((a\land b)\lor (a \land c)\big)$ and then using a karnaugh map:

$$ \begin{array}{c|c|c|c|c} a, bc & 00 & 01 & 11 & 10 \\ \hline 0 & 1 & & & \\ \hline 1 & & 1 & 1 & 1\\ \hline \end{array}=a \oplus (\neg b \land \neg c) $$

K. Rmth
  • 1,749
  • Using the actual k-map for this question gives you 1000 for top row, and 0111 for bottom row, which then evaluates to exactly the op's expression – Cruncher Nov 28 '13 at 19:49
  • Edited my answer accordingly, thanks to BrianM.Scott and Cruncher. An example of the exor(http://en.wikipedia.org/wiki/Exclusive_or) trick is http://math.stackexchange.com/a/578670/59553 – K. Rmth Nov 28 '13 at 20:06
1

The simplest way to rewrite this, if you're allowed to use something other than $\;\land,\lor,\lnot\;$, is the following: \begin{align} & (\lnot a \land \lnot b \land \lnot c) \;\lor\; \big(a \land(b \lor c)\big) \\ = & \;\;\;\;\;\text{"DeMorgan -- to make the left and right parts similar"} \\ & \big(\lnot a\land \lnot (b \lor c)\big) \;\lor\; \big(a \land(b \lor c)\big) \\ = & \;\;\;\;\;\text{"$\;(p \land q) \lor (\lnot p \land \lnot q)\;$ is one of the ways to write $\;p \equiv q\;$"} \\ & a \;\equiv\; b \lor c \\ \end{align}

MarnixKlooster ReinstateMonica
  • 5,576