2
$\begingroup$

(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:

$(x'y'+xy)'z'+(x'y'+xy)z$

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)
$=(x'y')'(xy)'z'+(x'y'+xy)z$
$=(x+y)(x'+y')z'+(x'y'+xy)z$
$\require{enclose}=\enclose{updiagonalstrike}{xx'z}+xy'z'+x'yz'+\enclose{updiagonalstrike}{yy'z'}+x'y'z+xyz$
$=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?

$\endgroup$
  • $\begingroup$ The expansion of $x \oplus y \oplus z$ introduces an error in the second line (should be $= (x'y+xy')\oplus z$) and carries it through until a second error cancels it out in the fifth line ($= (x+y')(x'+y)z+(x'y+xy')z'$). $\endgroup$ – Peter Taylor Aug 21 '18 at 16:44
  • $\begingroup$ I fixed it, but I believe the problem stays. $\endgroup$ – anir Aug 21 '18 at 18:22
2
$\begingroup$

Since $X \odot Y = X \oplus Y \oplus 1$, we see that $$ A \odot B \odot C = A \oplus B \oplus 1 \oplus C \oplus 1 = A \oplus B \oplus C. $$

$\endgroup$
2
$\begingroup$

Yes, $x\odot y\odot x = x\oplus y\oplus z$, where $\oplus$ is the XOR operator and $\odot$ is the XNOR operator.

In fact, it is easy to see that both sides of the equation are always equal. Note that $a\odot b$ tests whether $a$ is the same as $b$ while $a\oplus b$ tests whether $a$ is different from $b$. So we know $a\odot b= \overline{a\oplus b} = \overline a\oplus b$. So, $x\odot y\odot z = (x\odot y)\odot z =\overline{x\oplus y}\odot z = \overline{\overline{x\oplus y}}\oplus z = x\oplus y\oplus z$. (We do not even use the associativity of $\odot$ nor that of $\oplus$.)

Let $n\geq 1$. We can show the following easily by induction on $n$. $$x_1\oplus x_2\oplus\cdots\oplus x_n = (\text{ number of true's in } \{x_1,\, x_2,\, \cdots,\, x_n\} \text { is odd }) $$ $$x_1\odot x_2\odot\cdots\odot x_n\, = (\text{ number of false's in } \{x_1,\, x_2,\, \cdots,\, x_n\} \text { is even }) $$

So in general, we have the following, which can be shown directly by induction on $n$ as well. $$\begin{align} \text{for odd } n,\ \ &x_1\oplus x_2\oplus\cdots\oplus x_n = x_1\odot x_2\odot\cdots\odot x_n\\ \text{for even } n,\ \ &x_1\oplus x_2\oplus\cdots\oplus x_n = \overline{x_1\odot x_2\odot\cdots\odot x_n} \end{align}$$


Now let us come to the real question. Why does wolfram alpha give a completely different output for $x\odot y\odot z$ at http://www.wolframalpha.com/input/?i=x+xnor+y+xnor+z?

As Peter Taylor has noticed on that web page, Wolfram parses "x xnor y xnor z" very differently from what we might have expected, "(x xnor y) xnor z". Wolfram parses it as "Not(x Xor y Xor z)" in text notation or, what is the same, "¬($x \underline\vee y\underline\vee z)$" in symbolic notation. This is not mentioned in its documentation for Xnor operator at http://mathworld.wolfram.com/XNOR.html nor at http://www.wolframalpha.com/input/?i=xnor. One might suspect this is an implementation bug of Wolfram.

However, it turns out this is a feature by design (or possibly an unintentional side-effect) of Wolfram. Its documentation for Operator Input Forms shows the following lines, where the small wedges at the end of each line means "built-in meaning exist". wolfram documentation on Xor and Xnor So after all Wolfram has decided to treat "x xnor y xnor z" as "not(xor(x,y,z))" instead of the more common "(x xnor y) xnor z" as a surprise to unsuspecting users such as OP and me! (Of course, "more common" is only in the eyes of some people. It is quite possible Wolfram's interpretation is more common in other situations.)

One might wonder why Wolfram has made such a strange and uncommon choice. Here is my speculation, my pure shallow speculation.

Wolfram defines Xor for multiple argument as "true if an odd number of its arguments are true and false otherwise", probably along the approach of a BooleanCountingFunction. It also parses and evaluates expressions such as "x1 xor x2 xor x3 xor x4 xor x5" (which everyone agree must be "((((x1 xor x2) xor x3) xor x4) xor x5)") as "Xor(x1, x2, x3, x4, x5)", which is easier to define and faster to compute especially when the number of arguments becomes larger. All is going well without inconsistency for Xnor. Xnor looks very similar to Xor. So, (again just my speculation), Wolfram chooses to define Xnor in a similar way to Xor ( and in fact, in a similar way to Or, And, too). Since BooleanCountingFunction only deals with the number of true values, it choose to to define and compute both Xnor(x1,x2,...,xn) and "x1 xnor x2 xnor ... xnor xn" as whether the number of the true values are even, which is also the negation of Xor and which is, at least indeed, the same as x1$\odot$x2 in the case when $n=2$. However, the resulting value of, for example, "x1 xnor x2 xnor x3" as computed by the negation of Xor(x1,x2,x3) is exactly the opposite of the value of "(x1 xnor x2) xnor x3"! In fact, Wolfram's value of "x1 xnor ... xnor xn" and our value of x1$\odot\cdots\odot$xn are the same when n is even and different when n is odd, for any truthy value of x1, ... and xn.

Moreover, there exists a somewhat similar problem for the NAND operator, but to a much less extent since NAND is not associative. Wolfram treats "x nand y nand z" as "x nand (y nand z)" instead of "(x nand y) nand z" (probably for another good reason). You can check the outputs by Wolfram, http://www.wolframalpha.com/input/?i=x+nand+y+nand+z, http://www.wolframalpha.com/input/?i=(x+nand+y)+nand+z and http://www.wolframalpha.com/input/?i=x+nand+(y+nand+z)

In conclusion, be careful when you use Wolfram to compute logic formula involving XNOR and NAND, especially if you have more than one such operator or more than three arguments. You will want to double check.

$\endgroup$
1
$\begingroup$

The discrepancy is that Wolfram Alpha's interpretation of x xnor y xnor z is not the same as yours. Compare x xnor y xnor z with (x xnor y) xnor z, looking both at the truth tables and at the logic gate. You consider them to be equivalent, but WA is parsing x xnor y xnor z as a single three-input gate not(xor(x, y, z)), and it parses x xor y xor z as xor(x, y, z), so naturally the outputs are inverted.

$\endgroup$

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.