Boolean Algebra: Explain why (M AND (NOT N)) OR (X AND M AND N) = (M AND NOT N) OR (X AND M)?

375 Views Asked by At

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?

1

There are 1 best solutions below

3
On BEST ANSWER

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.