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.
2 Answers
$\begingroup$
$\endgroup$
The third factor is always $1$. Then
$$\begin{align}&a=0\to &1\,(1+b)&=1,\\&a=1\to &!b\,b&=0.\end{align}$$
$\begingroup$
$\endgroup$
10
! 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.
answered May 14, 2023 at 16:03
-
$\begingroup$ Your simplification is wrong. $\endgroup$– user16034Commented May 14, 2023 at 17:18
-
$\begingroup$ @YvesDaoust The question stated that the RHS of the equation is the negation of
a. How is it wrong? $\endgroup$ Commented May 14, 2023 at 17:22 -
$\begingroup$ Boolean arithmetic is not modulo $2$ and $\lnot a$ is not what you wrote. $\endgroup$– user16034Commented May 14, 2023 at 17:23
-
$\begingroup$ @YvesDaoust Emphasis on integer arithmetic modulo 2. $\endgroup$ Commented May 14, 2023 at 17:25
-
1$\begingroup$ In "my" Boolean arithmetic, $+$ denotes or, not exclusive or. And please fix your truth table ! $\endgroup$– user16034Commented May 14, 2023 at 17:26
***!(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). $\endgroup$*between the next factors will fix. :-) $\endgroup$