## 28-08-2011 Fun with logic gates

When I was in college, I took a rather enjoyable math course that was taught by a professor named Gerry Dworschak. 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 its 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 Associative 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:

Prove that (A ⊕ B) ⊕ C ≡ A ⊕ (B ⊕ C) | ||
---|---|---|

(A ⊕ B) ⊕ C | A ⊕ (B ⊕ C) | |

(A'B + AB')'C + (A'B + AB')C' | A'(B'C + BC') + A(B'C + BC')' | |

((A'B)'(AB')')C + A'BC' + AB'C' | A'B'C + A'BC' + A((B'C)'(BC')') | |

(A + B')(A' + B)C + A'BC' + AB'C' | A'B'C + A'BC' + A(B + C')(B' + C) | |

(AA' + AB + A'B' + BB')C + A'BC' + AB'C' | A'B'C + A'BC' + A(BB' + BC + B'C' + CC') | |

(AB + A'B')C + A'BC' + AB'C' | A'B'C + A'BC' + A(BC + B'C') | |

ABC + A'B'C + A'BC' + AB'C' | A'B'C + A'BC' + ABC + AB'C' | |

ABC + A'B'C + A'BC' + AB'C' | ABC + A'B'C + A'BC' + AB'C' | |

q.e.d. |

With that proven, we can now say:

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