1

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?

user2055216
  • 119
  • 1
  • 7

1 Answers1

1

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.

Sp3000
  • 1,562
  • 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. – user2055216 Sep 13 '13 at 05:04
  • How did you replace $N' + N$ with $1$? – goblin GONE Sep 13 '13 at 05:39
  • (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. – Sp3000 Sep 13 '13 at 05:43