1
$\begingroup$

I was able to simplify a boolean expression $$(\neg a*\neg b*c)+(a*\neg b*\neg c)+(a*b*\neg c)+(a*b*c)$$into the form $$\neg b*(a\oplus c)+a*b$$ where $*$ is the logical and, $+$ is the logical or, and $\oplus$ is the logical XOR.

Apparently, from Wolfram Alpha, this expression can be simplified to $$\left(a\oplus c\right)\oplus(b*c)$$

I would like to know how Wolfram Alpha was able to simplify this.

$\endgroup$
  • $\begingroup$ It might help if you could spell out the steps you used to obtain your simplification. Which rules for transforming these expressions are you working with? $\endgroup$ – G Tony Jacobs May 9 '17 at 22:49
2
$\begingroup$

I'm not privy to the internals of Wolfram Alpha, but here's a way to derive the expression it produces.

First of all, it's not unreasonable to assume that if the input contains an exclusive OR, WA may decide that the user wants to see exclusive ORs in the output, or is at least OK with them.

Let $f = \neg b * (a \oplus c) + (a * b)$. Applying Reed-Muller expansion with respect to $b$, we get cofactors $f_b = a$, $f_{\neg b} = a \oplus c$, Boolean difference $\frac{\partial f}{\partial b} = c$, and hence

$$ f = f_{\neg b} \oplus b * \frac{\partial f}{\partial b} = (a \oplus c) \oplus (b * c) \enspace. $$

The choice of $b$ for the expansion is enticing when computing by hand because the cofactors and the Boolean difference are easy to find. Is this what WA does? Expansion w.r.t. $a$ produces

$$a \oplus (\neg b * c) \enspace. $$

Expansion w.r.t. $c$ also produces this result. This expression is more concise than the previous one, but not in Reed-Muller canonical form, which may be what WA is shooting for. Conversion produces

$$ a \oplus ((1 \oplus b) * c) = a \oplus c \oplus (b*c) \enspace. $$

So, no matter how we do the expansion, we end up with the expected result if we shoot for Reed-Muller canonical form. The parentheses in the expression produced by WA suggest the expansion is actually carried out w.r.t. $b$.

$\endgroup$
0
$\begingroup$

That expression you got from WA isn't the same as your original. It includes, for example, $(\neg a * b * \neg c)$, which is not included in your original expression. I figured that out by looking at a Venn diagram.


Edit: With that correction, WA's solution actually matches up. As for how they obtained it, I don't know what specific algorithm they use, but we can see that their expression is indeed equivalent to the original. It consists of two disjoint pieces: $(a\oplus c)*\neg(b*c)$, and $\neg(a\oplus c)*(b*c)$. The first piece is equivalent to $(a*\neg b*\neg c)+(a*b*\neg c)+(\neg a*\neg b*c)$, while the second is the same as $(a*b*c)$.

Again, this is probably easiest to see by drawing a Venn diagram.

$\endgroup$
  • $\begingroup$ Sorry, I made a mistake when typing the simplified expression. I have updated it now. $\endgroup$ – Jake May 9 '17 at 18:19
  • $\begingroup$ Ah, that makes more sense. $\endgroup$ – G Tony Jacobs May 9 '17 at 18:20
  • $\begingroup$ Instead of hand-waving by saying "As for how they obtained it", you ask 'how did you obtain your simplification?' (Not an answer.) And from there, what you say is just filling space. This is not an answer to the question, nor does it provide a pathway for the asker to arrive at the answer. $\endgroup$ – Namaste May 9 '17 at 21:53
  • $\begingroup$ You're right. I probably should have posted my initial "answer" as a comment. Should I delete this whole thing now, do you think? $\endgroup$ – G Tony Jacobs May 9 '17 at 22:07
  • $\begingroup$ Can you add to the portion after the horizontal line, to give some explanation as to how the asker's conclusion matches Wolfram Alpha? Then all will be fine! $\endgroup$ – Namaste May 9 '17 at 22:10

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.