28-08-2011

When I was in college, I took a rather enjoyable math course that was taught by a professor named Gerry Dworshak. He's the teacher who gave us the rather puzzling bonus problem that I've previously blogged about, the falling stick.

One of the subjects that was covered in that course was boolean algebra, and on the final exam, the last question was the following:

prove that (A ⊕ B) ⊕ (B ⊕ C) = A ⊕ C

The most intuitive way to do it is to simply say that the B's cancel each other out, giving you the end result in one step. The parentheses prevent it from being that simple though, so the problem needs to be done a little more carefully. One way to solve it is to simply expand the exclusive ors and reduce the expression to it's simplest terms. That's what I did at that point:

(A ⊕ B) ⊕ (B ⊕ C)
= (AB' + A'B) ⊕ (BC' + B'C)
= (AB' + A'B)(BC' + B'C)' + (AB' + A'B)'(BC' + B'C)
= (AB' + A'B)(BC')'(B'C)' + (AB')'(A'B)'(BC' + B'C)
= (AB' + A'B)(B' + C)(B + C') + (A' + B)(A + B')(BC' + B'C)
= (AB' + A'B)(B'B + B'C' + CB + CC') + (A'A + A'B' + AB + BB')(BC' + B'C)
= (AB' + A'B)(B'C' + CB) + (A'B' + AB)(BC' + B'C)
= (AB'B'C' + AB'CB + A'BB'C' + A'BCB) + (A'B'BC' + A'B'B'C + ABBC' + BAB'C)
= (AB'C' + A'BC) + (A'B'C + ABC')
= AB'C' + A'BC + A'B'C + ABC'
= B(A'C + AC') + B'(AC' + A'C)
= (B + B')(AC' + A'C)
= A'C + AC'
= A ⊕ C

And clearly that method works. Last night however, I was looking for something to do and decided to revisit this question. In doing so, I came up with a much more elegant solution. Instead of expanding and simplifying the above problem, simply prove that the Commutative property holds true for an exclusive or operator. Then the brackets can simply be removed, and the B's cancel each other out. So here's how I did it:

With that proven, we can now say:

∴(A ⊕ B) ⊕ (B ⊕ C) ≡ A ⊕ B ⊕ B ⊕ C
= A ⊕ ∅ ⊕ C
= A ⊕ C

One last thing that may be needed here is to prove that x ⊕ ∅ = x. We can show that with a simple truth table: