-1

For context: I am learning Boolean Algebra by myself for fun and one of the questions in the book I am reading was a long boolean expression and the task was to simplify it to be the XOR boolean expression. I have managed to come quite a bit but cannot progress any further.

I am unable to simplify $\overline{(a+\overline{b})\cdot (\overline{a}+b)}$ to be $a\overline{b} + \overline{a}b$.

There seem to be no laws associated with this type of boolean multiplication. Can anybody point me in the right direction? My original equation is of an XOR logical operation, but not in its "final form" so to say.

riemanneru
  • 69
  • 1
    Have you tried the distributive law? – rogerl Apr 02 '22 at 15:38
  • your expression is the inverse of the one proposed. – zwim Apr 02 '22 at 15:45
  • @rogerl I can only find examples using $a, b, c$ such as $a(b+c)$. This tells me nothing of how to multiply two parenthesis with four distinct variables. – riemanneru Apr 02 '22 at 15:45
  • @zwim You are correct, I missed the overline! Thanks for pointing it out, I have edited the post and it should be correct now. The issue still stands. – riemanneru Apr 02 '22 at 15:48
  • Well, if $p\cdot(\overline{a}+b) = p\cdot\overline{a} + p\cdot b$, substitute $a+\overline{b}$ for $p$. – rogerl Apr 02 '22 at 22:27

3 Answers3

1

XOR in conjuctive normal form is $(a+b)\cdot (\bar a+\bar b) = a\bar a + a\bar b + b\bar a + b\bar b$ by distributivity. But $a\bar a = 0 = b\bar b$ and $0+x = x$ for any Boolean expression $x$. Hence, the result is $a\bar b + \bar a b$ by commutativity.

Wuestenfux
  • 20,964
  • I am unable to find any information regarding multiplication between two parenthesis containing four distinct variables. Can you please specify the law used in this example, preferably with a source? I am unsure regular algebra simplification applies here as I have, again, not seen this type of solution method anywhere. – riemanneru Apr 02 '22 at 15:46
1

Note that $(a+b)\cdot(\overline{a} + \overline{b}) = (a+b)\cdot\overline{a} + (a+b)\cdot\overline{b}$ by the distributive property. Applying that property again to each term gives $$(a+b)\cdot\overline{a} + (a+b)\cdot\overline{b} = a\cdot\overline{a} + b\cdot\overline{a} + a\cdot\overline{b} + b\cdot\overline{b},$$ which as noted in other answers simplifies to $b\cdot\overline{a} + a\cdot\overline{b}$.

rogerl
  • 22,399
0

If you develop your product you get: $$(a+b')(a'+b)=\overbrace{aa'}^0+ab+a'b'+\overbrace{bb'}^0=ab+a'b'$$

Yet you want $a\oplus b=(ab'+a'b)$ to appear not $(ab+a'b')$.

But notice that for any $x$ then $x+x'=1$ therefore:

$$1=a'(b+b')+a(b+b')=(ab'+a'b)+(ab+a'b')$$

So in the end $(ab+a'b')=(ab'+a'b)\ '$

zwim
  • 28,563
  • I was able to follow your reasoning until the last line. $1 = (ab'+a'b)+(ab+a'b')$ is absolutely acceptable but how do you go from that to the expressions being equal? Where does the $1$ go? – riemanneru Apr 02 '22 at 16:02
  • They are not equal, they are inverse of each other (there is a prime outside the parenthesis). – zwim Apr 02 '22 at 16:03
  • so when we make the second expression (the one I had) inverse the following is true: $1 - (ab+a'b')'=0$? I do not fully understand where the $1$ goes and what each "expression part" (made up term) corresponds to but a value of either $1$ or $0$ depending on the values of $a$ and $b$. Can the expression I wrote in my original post be equal to $1$? If so, why? And how does that make sense? – riemanneru Apr 02 '22 at 16:14
  • Oh now I get it! I was unsure how an expression of multiple variables fit into the laws of boolean algebra, but they represent $x$ and $x'$ thus becoming $1$! Thus if I take the inverse of one it becomes the other! Yes now I understand! Thanks a thousand times over! – riemanneru Apr 02 '22 at 16:18