(The notations used:

I was solving a problem, where they asked which of the given options give equation for the difference of full subtractor. The circuit in the solution option was:

enter image description here

For me the first line:


looked more like $x\odot y\odot z$. But I know the difference of full subtractor is $x\oplus y\oplus z$. So I tried to evaluate both separately:

$x\oplus y\oplus z$
$= (x'y+xy')\oplus z$
$= (x'y+xy')'z+(x'y+xy')z'$
$= (x'y)'(xy)'z+(x'y+xy')z'$
$= (x+y')(x'+y)z+(x'y+xy')z'$
$\require{enclose}= \enclose{updiagonalstrike}{xx'z}+xyz+x'y'z+\enclose{updiagonalstrike}{yy'z}+x'yz'+xyz'$
$= xyz+x'y'z+x'yz'+xy'z'$ ...equation$(I)$

$x\odot y\odot z$
$=(x'y'+xy)\odot z$
$=(x'y'+xy)'z'+(x'y'+xy)z$ (This is same as first line in the equations given in the figure above)
$=xy'z'+x'yz'+x'y'z+xyz$ ...equation$(II)$

To my eyes, both equations $(I)$ and $(II)$ looks the same. So I went to wolframalpha and prepared truth table for both of them.

$x\oplus y\oplus z$
enter image description here

$x\odot y\odot z$
enter image description here

And they correctly look complement of each other. Then why the given answer and my calculations equates $x\odot y\odot z$ with $x\oplus y\oplus z$? What stupidity I am doing here?

  • 1
    $\begingroup$ @MichaelBurr: The two-input operations here are all both commutative and associative. However it looks like Wolfram interprets the second expression as something different from a tree of binary operations. $\endgroup$ – Henning Makholm Aug 21 '18 at 16:40

You're not doing anything wrong.

Negation commutes with XOR -- in other words, $(\neg x)\oplus y = \neg(x\oplus y) = x\oplus(\neg y)$. So when you change two XORs to XNORs you're adding two negations that can find each other and annihilate.

Wolfram Alpha seems to be using an unusual interpretation of $a\overline\veebar b \overline\veebar c$ where it interprets it as a three-input XNOR, apparently understood as $\overline{a\veebar b\veebar c}$, instead of as $(a\overline\veebar b)\overline\veebar c$ or $a\overline\veebar (b\overline\veebar c)$.

Compare Wolfram's interpretation of p XNOR q XNOR r with p XNOR (q XNOR r).

This arguably makes sense if you're thinking of digital logic -- asking for an $n$-input XNOR gate and getting the same as XOR if $n$ happens to be odd would not be terribly useful -- but is certainly confusing from an algebraic point of view.

  • $\begingroup$ Do you mean to say $x\odot y\odot z=(x\odot y)\odot z=\neg(\neg(x\oplus y)\oplus z)=\neg(x\oplus(\neg y)\oplus z)=x\oplus(\neg\neg y)\oplus z=x\oplus y\oplus z$ (when you said "... can find each other and annihilate...")? $\endgroup$ – anir Aug 21 '18 at 16:40
  • $\begingroup$ Yes, for example. $\endgroup$ – Henning Makholm Aug 21 '18 at 16:41
  • $\begingroup$ Is it exactly whats going on in my problem? Are those equations in my comment (especially $\neg(x\oplus(\neg y)\oplus z)=x\oplus(\neg\neg y)\oplus z$) perfectly correct (just want to reconfirm as I am coming across this first time)? $\endgroup$ – anir Aug 21 '18 at 16:43
  • 1
    $\begingroup$ @anir: It is correct but a bit of a detour. I would just write $$ \neg(\neg(x\oplus y)\oplus z) = (\neg\neg(x\oplus y))\oplus z = (x\oplus y)\oplus z$$ $\endgroup$ – Henning Makholm Aug 21 '18 at 16:48
  • $\begingroup$ Ohh yess this looks more correct!!! $\endgroup$ – anir Aug 21 '18 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.