# !(ab)*(!a+b)(!b+b)=!a Boolean Algebra

How can I prove that !(ab)(!a+b)(!b+b)=!a* in boolean algebra? This is an exercise from a past paper of my teacher but I can't really find the way to the answer. I would appreciate some help.

• What did you try? May 14 at 14:32
• Since there are only two variables, you could just check the $4$ possible truth assignments May 14 at 14:59
• What do you denote a* ?
– user16034
May 14 at 15:18
• @YvesDaoust The Kleene's star, obviously, duh! (Sorry, I couldn't resist. My guess, looking at the source text ***!(ab)*(!a+b)(!b+b)=!a***, is that OP used the single * as a logical AND, and the triple *** as emphasize. Markdown came and this is the result). May 14 at 15:48
• @Nathaniel: then a second * between the next factors will fix. :-)
– user16034
May 14 at 15:53

The third factor is always $$1$$. Then

\begin{align}&a=0\to &1\,(1+b)&=1,\\&a=1\to &!b\,b&=0.\end{align}

! is a negation and will be replaced by ¬ in this answer. This would transform your equation to ¬(ab)(¬a+b)(¬b+b). "True" has a value of 1 and "False" has a value of 0. The operations are applied on these numbers in mod 2 arithmetic. The negation of 0 would be 1 and vice versa, so (¬b+b)=1. Since multiplication by 1 does not do anything, this can be removed to transform the equation to ¬(ab)(¬a+b). Adding 2 booleans together will give "True" only if they have different values, so negating one of them will mean it will return "True" if they have the same value. Multiplying 2 booleans together will return "True" only if both of them are true, so the negation of that will return "True" only if at least one of them is "False". Putting this into coding notation, this becomes (not (a and b)) and (a=b). So to return "True", a and b have to have the same value, and one of them have to be "False", so they both have to be "False" to return "True". This is equivalent to not (a or b). So the final equation (in traditional boolean algebra) is ¬(a∨b)=¬a. Let's make a truth table:

--------------------------------
| a | b | not (a or b) | not a |
--------------------------------
| 1 | 1 |      0       |   0   |
| 1 | 0 |      0       |   0   |
| 0 | 1 |      0       |   1   |
| 0 | 0 |      1       |   1   |
--------------------------------


We find that this equality is untrue in boolean algebra.

• @YvesDaoust The question stated that the RHS of the equation is the negation of a. How is it wrong? May 14 at 17:22
• Boolean arithmetic is not modulo $2$ and $\lnot a$ is not what you wrote.
• In "my" Boolean arithmetic, $+$ denotes or, not exclusive or. And please fix your truth table !