How to use xor properly

Question

I need to know how to use XOR properly on more than two variables. I have following example.

a xor b xor c

Now, the way I understand it is that:

$a$ xor $b$ = $a$ * not $b$ + not $a$ * $b$

That part is fairly simple for me to understand but how does the next part work? I imagine it goes like this.

($a$ * not $b$ + not $a$ * $b$) xor $c$

So, how can I use XOR on more than one variable?

Answer 1

Use

a xor b = a * not b + not a * b

again, but this time, in place of b put c and in place of a put

(a * not b + not a * b)

Answer 2

NOTE: Just so you know, a XOR b is the same as $a \oplus b$. Also, here's a shortcut to XOR: If $a$ and $b$ are different, then $a \oplus b=1$. Otherwise, if they're the same, $a \oplus b=0$. Your formula works as a definition for XOR, but when you're calculating XOR in your head, I think this rule of thumb is easier.

If you know how to calculate $a \oplus b$, then you can simply calculate $a \oplus b$, set that to $d$ and then calculate $d \oplus c$. Basically, you work with two elements at a time: First, you look at the first two elements and then you take that result and use it with the third element.

Here's an example: Calculate $1 \oplus 0 \oplus 1$. Since $1$ and $0$ are different, we know that $1 \oplus 0=1$. This means that we now need to figure out $1 \oplus 1$. The first $1$ comes from the result of our first $\oplus$ calculation and the second $1$ comes from the fact that $1$ was the third element in our original expression. Since $1$ and $1$ are the same, we know that $1 \oplus 1=0$. Thus, $1 \oplus 0 \oplus 1=0$.

Answer 3

Since xor is associative (Prove XOR is commutative and associative?), there is no confusion when we write $$a \oplus b \oplus c = (a \oplus b) \oplus c,$$ which is what you've already found to be $$[(a \wedge \neg b) \vee (\neg a \wedge b)] \oplus c.$$ By the end, you get the ugly, yet valid $$\left[[(a \wedge \neg b) \vee (\neg a \wedge b)]\wedge \neg c\right] \vee \left[\neg[(a \wedge \neg b) \vee (\neg a \wedge b)] \wedge c\right].$$ I'm sure a few propositional equivalences could simplify that right up.

Why stop at three, though? You could go on and on via induction, until you have $$a \oplus b \oplus c \oplus d \oplus \dots = ((((a \oplus b) \oplus c) \oplus d) \oplus \dots)$$

And at the same time, it doesn't matter what you designate $a$, $b$, $c$, $d$, or any other variable to be because xor is commutative, as well!

Answer 4

I will use $\oplus$ for exclusive OR and $\bar x$ for NOT $x$. Just expand the expression:

$$\begin{align*} (x\oplus y)\oplus z&=(x\bar y+\bar xy)\oplus z\\ &=(x\bar y+\bar xy)\bar z+\overline{(x\bar y+\bar xy)}z\\ &=x\bar y\bar z+\bar xy\bar z+\overline{(x\bar y)}\;\overline{(\bar xy)}z\\ &=x\bar y\bar z+\bar xy\bar z+(\bar x+y)(x+\bar y)z\\ &=x\bar y\bar z+\bar xy\bar z+(\bar xx+\bar x\bar y+xy+y\bar y)z\\ &=x\bar y\bar z+\bar xy\bar z+(\bar x\bar y+xy)z\\ &=x\bar y\bar z+\bar xy\bar z+\bar x\bar yz+xyz \end{align*}$$

If you examine that final result, you’ll see that it has every product (conjunction) with an odd number of non-negated variables. This is true in general: $x_1\oplus x_2\oplus\ldots\oplus x_n$ is the sum (disjunction) of all expressions of the form $y_1y_2\ldots y_n$, where each $y_k$ is either $x_k$ or $\overline{x_k}$, and the number of $k\in\{1,\ldots,n\}$ such that $y_k=x_k$ is odd. Thus, for instance,

$$\begin{align*} w\oplus x\oplus y\oplus z&=wxy\bar z+wx\bar yz+w\bar xyz+\bar wxyz\\ &\quad+w\bar x\bar y\bar z+\bar wx\bar y\bar z+\bar w\bar xy\bar z+\bar w\bar x\bar yz\;. \end{align*}$$

This more general result can be proved by induction on the number of terms.