Proof of (B != C) => (A XOR B) != (A XOR C)

Question

I have a conjecture: If $B \neq C$, then

$$ A\ \text{XOR}\ B \neq A\ \text{XOR}\ C $$

Is it true? If so, how to prove it?

What I tried:

I think I have proven the contrapositive qualitatively by writing a binary representation of $A$. Let $a_i, b_i, c_i$ be $i$th bit of $A, B, C$. To make $A\ \text{XOR}\ B = A\ \text{XOR}\ C$, $b_i = c_i$ shall be satisfied for all $i$.

But I have no quantitative proof.

What have you tried? Where are you stuck? You have been here long enough to know we expect some effort. -1 and vote to close — Ross Millikan, Nov 29 '22 at 04:38
You have not used the fact that $B \neq C$. Without that, how can you succeed? — Ross Millikan, Nov 29 '22 at 04:57
@RossMillikan To me, it looks like they're proving the contrapositive, which need not use $B \neq C$ to prove $B=C$. — Brian Moehring, Nov 29 '22 at 05:00
Yes. I think I have proven the contrapositive, but I'm not confident at all. — ynn, Nov 29 '22 at 05:02
@BrianMoehring: I don't see a complete argument here, just a statement. While I was writing this the question was edited to include the word contrapositive. — Ross Millikan, Nov 29 '22 at 05:03
@ynn: I don't see a proof here. You should have a chain of sentences that explain your reasoning. If you have proven the contrapositive, please show the proof. — Ross Millikan, Nov 29 '22 at 05:04

Chloe · Answer 1 · 2022-11-29T05:09:42.423

1

Suppose $A,B,C\in\{0,1\}$ and suppose $B \neq C$.

$B \neq C$ $\Rightarrow$ $B,C$ are elements of a set with at least 2 elements. So $B,C\in \{0,1\}$ $\Rightarrow$ $B=0,C=1$ or $B=1,C=0$ must be true.

Because $A\in\{0,1\}$, $A=0$ or $A=1$ must be true.

Note that $A\ \ XOR\ \ B=0 \iff A=B$ and $A\ \ XOR\ \ B=1 \iff A \neq B$. Similar relation with $A$ and $C$.

Because $B\neq C$, we have $A=B$ or $A=C$.

If $A=B$, we have $A=B\neq C \Rightarrow A\ \ XOR\ \ B=0$ and $A\ \ XOR\ \ C=1$.

Similarly, if $A=C$, we have $B\neq C=A \Rightarrow A\ \ XOR\ \ B=1$ and $A\ \ XOR\ \ C=0$.

Hence, $0\neq 1 \Rightarrow A\ \ XOR\ \ B \neq A\ \ XOR\ \ C$.

edited Nov 29 '22 at 05:09

answered Nov 29 '22 at 05:03

Chloe

166
7

For my note: Even if $A, B, C$ are unsigned integers (i.e. vector of boolean), XOR can be calculated independently for each digit. Thus this proof still works. – ynn Nov 29 '22 at 05:26
You scared me! I have never done a proof for logic gates so I was hoping that logic alone would carry me! Thanks for the comment! – Chloe Nov 29 '22 at 20:59

score 1 · Accepted Answer · answered Nov 29 '22 at 06:15

1

The standard algebraic proof is by the contrapositive and uses the following properties of XOR (which I'll denote using $\oplus$):

$\oplus$ is associative
There is an element $0$ such that $0 \oplus x = x$ for any $x$
For any $x$, $x \oplus x = 0$.

From this, we assume $A \oplus B = A \oplus C$. Then $$\begin{align*}B &= 0 \oplus B \\ &= (A \oplus A)\oplus B \\ &=A \oplus (A \oplus B) \\ &= A \oplus (A \oplus C) \\ &= (A \oplus A) \oplus C \\ &= 0 \oplus C \\ &= C. \end{align*}$$

answered Nov 29 '22 at 06:15

Brian Moehring

21,088

Beautiful. Let me accept this answer as this proof natively works both for when $A, B, C$ are boolean and when $A, B, C$ are unsigned integer (i.e. vector of booleans). – ynn Nov 29 '22 at 07:08

Proof of (B != C) => (A XOR B) != (A XOR C)

2 Answers2