[Math] Boolean expression of 3 input xor gate

boolean-algebralogic

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.

Best Answer

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).

Related Question