Boolean expression of 3 input xor gate

Question

how is it equal
$A$ xor $B$ xor $C = A'BC' + AB'C' + A'B'C + ABC.$
can someone explain using with boolean algebra rules.

Answer 1

You can either understand $A \oplus B \oplus C$ to mean $(A \oplus B) \oplus C$, in which case you can use the definition of $A \oplus B \equiv A \cdot \bar B + \bar A \cdot B$ to get your result.

Or you can understand the $n$-input XOR to return true iff an odd number of $1$'s are supplied to its input, in which case you should try to see why your expression is valid for a $3$-input XOR.

Answer 2

Think of xor in terms of and and or using: $$A \text{ xor } B = AB'+BA'.$$ This should make sense as this is valid because it will return true when exactly one of $A$ and $B$ is true.

To derive the expression in question, simply apply this identity twice.

Answer 3

You can verify that this is true using a truth-table, but you can also understand it as follows:

First of all, the $xor$ is an associative operator: $A \ xor \ (B \ xor \ C)$ is equivalent to $(A \ xor \ B) \ xor \ C$.

Because of this, you can actually drop parentheses and just write $A \ xor B \ xor \ C$

In fact, because of its associative property the $xor$ can take any numer of arguments, and by induction you can prove that it will be true if and only if an odd number of those arguments are true:

Base: An $xor$ with one argument $P$ is true of and only if $P$ is true, i.e. if and only if an odd number of that $1$ statement $P$ is true.

Step: Assume (Inductive Hypothesis) that an $xor$ with $n$ arguments is true iff and an odd number of those $n$ arguments are true. Now take an $xor$ with $n+1$ arguments. It will be of the form $\phi_1 \ xor \ \phi_2 \ xor \ ... \ xor \ \phi_n \ xor \ \phi_{n+1}$, and that will be true if and only if either $\phi_1 \ xor \ \phi_2 \ xor \ ... \ xor \ \phi_n $ is true and $\phi_{n+1}$ is false, or if $\phi_1 \ xor \ \phi_2 \ xor \ ... \ xor \ \phi_n $ is false and $\phi_{n+1}$ is true. In the first case, by inductive assumption, an odd number of $\phi_1, ... ,\phi_n$ are true, meaning that an odd number of $\phi_1, ... ,\phi_n, \phi_{n+1}$ are true, and in the second case an even number of $\phi_1, ... ,\phi_n$ are true, meaning that an odd number of $\phi_1, ... ,\phi_n, \phi_{n+1}$ are true. And since there are no other ways to get an odd number of $\phi_1, ... ,\phi_n, \phi_{n+1}$ to be true, we thus have that $\phi_1 \ xor \ \phi_2 \ xor \ ... \ xor \ \phi_n \ xor \ \phi_{n+1}$ is true if and only an odd number of $\phi_1, ... ,\phi_n, \phi_{n+1}$ are true.

Therefore, when you give it $3$ arguments, as in this case, it will be true if either exactly one of the arguments is true, or if all three are true, and you see that expressed in $A'BC' + AB'C'+A'B'C+ABC$

Finally, if you want to derive this using Boolean Algebra rules:

$$A \ xor B \ xor \ C =$$

$$(AB' + A'B) \ xor \ C = $$

$$(AB' + A'B)C' + (AB' + A'B)'C=$$

$$AB'C'+A'BC' + ((AB')'(A'B)')C=$$

$$AB'C'+A'BC'+(A'+B)(A+B')C=$$

$$AB'C'+A'BC'+(A'A+A'B'+BA+BB')C=$$

$$AB'C'+A'BC'+(0+A'B'+AB+0)C=$$

$$AB'C'+A'BC'+(A'B'+AB)C)=$$

$$AB'C'+A'BC'+A'B'C+ABC$$

(fixed first term 5/8/18)

Answer 4

The key is that XOR is associative so $\rm(X\oplus Y)\oplus Z = X\oplus(Y\oplus Z) = X\oplus Y\oplus Z$.

Everything else is substitution and distribution.

---

Substitute using $\rm X\oplus Y = XY' + X'Y$ and $\rm (X\oplus Y)' = X'Y'+XY$ then:

$$\rm {\quad A\oplus B\oplus C \\ = (A\oplus B)\oplus C \\ = (A\oplus B)C' + (A\oplus B)'C \\ = (AB' + A'B)C' + (A'B' + AB)'C \\ = AB'C' + A'BC' + A'B'C + ABC }$$

---

Likewise, using $\rm X\oplus Y = (X+Y)(X'+Y')$ and $\rm (X\oplus Y)' =(X'+Y)(X+Y')$ then:

$$\rm {\quad A\oplus B\oplus C \\ = (A\oplus B)\oplus C \\ = ((A\oplus B)+C)((A\oplus B)'+C') \\ = ((A+B)(A'+B')+C)((A'+B)(A+B')+C') \\ = (A+B+C)(A'+B'+C)(A'+B+C')(A+B'+C') }$$

---

Interpretation: $\rm A\oplus B\oplus C$ is true only when an odd count of the variables are true, just as is the case for $\rm A\oplus B$.

PS: Weak induction can be used to show this is also so for $\bigoplus_{i=1}^n \mathrm A_i$ where $n$ is any arbitrary natural larger than one (and we can include cases for one and zero with appropriate definitions).