0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Fill out a truth table and see that they match? $\endgroup$ – Henning Makholm Oct 19 '17 at 21:42
  • $\begingroup$ i want to see with boolean algebra rules like (A+B)(A+C) = A + BC. when i product (A+B)(A+C) with boolean algebra rules i find the result. $\endgroup$ – Heisenberg Oct 19 '17 at 21:47
  • $\begingroup$ I suggest you edit your question to add that request. As clearly as possible. $\endgroup$ – Joffan Oct 19 '17 at 21:48
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ @Heisenberg You're welcome! $\endgroup$ – Bram28 Oct 20 '17 at 2:26
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\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.