I have no idea how this is true, by what theorem, and I literally have been thinking about this for 3 hours now. I know it's really simple, but I just must not be in the right mindset to discover this now.

Here is (one of) the exact places where this is occurring:

= K'L'MN + MN'
= K'L'M + MN'

So you can see that N from the first term is getting dropped, due to some logical constraint I can't seem to fathom. If you replace K'L' with X, and then use a 3-circle Venn Diagram, you'll see it's true there also. But I was hoping someone could explain it in words, or at least Boolean algebra lemmas/rules.

Can someone explain why this is true?

  • $\begingroup$ You only have three variables, $X, M, N$, so it shouldn't be too hard to check via a truth table. $\endgroup$ – Sp3000 Sep 13 '13 at 4:47
  • $\begingroup$ Oh I did, and it's true. But I can't fathom why, in my head. It's really bothering me, especially because it is so common/simple. $\endgroup$ – user2055216 Sep 13 '13 at 4:47

Let's take a look at $MN' + XMN$. We can write this as

$$\begin{align} MN' + XMN &= M(N'+XN) \\ &= M((N'+X)(N'+N)) \\ &=M((N'+X)\cdot1)\\ &=M(N'+X)\\ &=MN'+XM \end{align}$$

That's how you could do it with Boolean algebra. The only real trick was the $N'+XN=(N'+X)(N'+N)$ part, which uses the distributivity of AND and OR.

  • $\begingroup$ Good thinking to factor it that way. Anyway, I think I'm done with this lemma for now -- I'm just going to commit it to memory. It's too confusing to consistently do in your head. $\endgroup$ – user2055216 Sep 13 '13 at 5:04
  • $\begingroup$ How did you replace $N' + N$ with $1$? $\endgroup$ – goblin Sep 13 '13 at 5:39
  • $\begingroup$ (NOT N) OR N is always true. It's like saying "If it rains, I'll go to school. Or if it doesn't rain, I'll go to school." - you'll be going to school either way. $\endgroup$ – Sp3000 Sep 13 '13 at 5:43

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.