0

so I have been trying to learn simplifying boolean Algebra, lets look at this term : $$ (a*b)+(a*\neg b)+(\neg a * \neg b)$$

I have several questions, I know how the right solution looks like but why couldn't I collect $a$ and $\neg a$?
so :
1. $a* \neg a *(b+\neg b+\neg b)$
2. $0*(1)$

is the way I simplifyied it right, is it just non-sense doing it like this or what is I wrong with this?

Zesa Rex
  • 113
  • Because you have to collect $a$ from the first two terms... – Mauro ALLEGRANZA Apr 28 '17 at 12:15
  • I did collect $a$ and $\neg a$, can you explain it a little bit to me? – Zesa Rex Apr 28 '17 at 12:17
  • It works exactly as with numbers; you can collect $2$ from $(2 \times a) + (2 \times b)$ but you cannot colelct $2$ and $-2$ from $(2 \times a) + (-2 \times b)$ – Mauro ALLEGRANZA Apr 28 '17 at 12:17
  • They are called Laws of boolean algebra; very similar to arithmetical laws. – Mauro ALLEGRANZA Apr 28 '17 at 12:19
  • In the first equation if you set $a = 1 = b$ it evaluates to $1$, but equation $(1)$ evaluates to $0$. Here is a derivation:

    $(a\cdot b) + (a \cdot \neg b) + (\neg a)\cdot (\neg b) = (a \cdot b) + (\neg b) = (a+\neg b) \cdot (b + \neg b) = a + \neg b$

     – Mike Apr 28 '17 at 12:28
  • @MauroALLEGRANZA but why cant you collect $2$ and $-2$? I have looked up the wiki, I didn't find anything about this, I guess it is just a rule, but I need to understand it in order to use it, is it because of the same values being positive once and negative once? – Zesa Rex Apr 28 '17 at 14:00
  • Because the law (both for booleans and numbers) says : $a \times (b+c)=(a \times b) + (a \times c)$. Thus, we "collect" the element $a$ that is "distributed". – Mauro ALLEGRANZA Apr 28 '17 at 14:05
  • If we have instead $(a×b)+(d×c)$ we cannot apply distributivity law.... – Mauro ALLEGRANZA Apr 28 '17 at 14:06
  • @MauroALLEGRANZA oh well that makes sense. I didn't think about that because $a$ and $\neg a$ were two sides of the same coin for me – Zesa Rex Apr 28 '17 at 14:09

1 Answers1

1

For the derivation, notice that there are 4 possible states of $a$ and $b$:

$$a = 0, b = 0 \\ a=0, b=1 \\ a=1,b=0 \\ a=1, b=1$$

Now, the expression $(a*b)$ is true for the fourth state, the expression $(a*\neg b)$ is true for the third state and the expression $(\neg a * \neg b)$ is true for the first state. So your expression is equivalent to: $$(a*b)+(a*\neg b)+(\neg a * \neg b) \equiv \neg(\neg a * b) $$ ("Just not the second option!"). By De-Morgan's rule: $$\neg(\neg a * b) \equiv a + \neg b$$

AsafHaas
  • 769