A Tale of Two Lights
I’m at an Airbnb. There is a stairwell that has a light at the bottom and a light at the top (the latter of which is also the hallway light). One desires to control both these lights from both ends so that you can always turn the light off after you, or turn the light on before you, regardless of which direction you’re going. There are indeed four light switches, but they don’t work like that. If they did, I wouldn’t have had to write this.
One switch is by the front door where the upper hallway is. Two are at the top of the stairs, and one at the bottom. Hm… that doesn’t sound like the pair of independent three-way switches you might expect. There’s only one switch at the bottom?
I’ve been here for literally weeks and I haven’t been able to figure out the way that these lights are connected. Most days I just mash them at random until I get them into the state I want. Yesterday I got so annoyed that I actually tabulated (and triple-checked!) data for how the switches perform. In binary.
| A | B | C | D | Top Light | Bottom Light |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
I stared at this for a while, and even drew out little truth tables for AND, OR, XOR and IMPLY (just learned about that one) as well as their NOT’d equivalents in an attempt to pattern match. The hope was to eventually draw a logic gate diagram (which I am sort of familiar with) and then back out a wiring diagram from that.
Instead, I floundered a bit on the internet and discovered that all these years that people have been saying “boolean algebra”, they literally meant that you can do algebra with it. Like numbers. But not quite, because the laws are different. Then I discovered products of sums and sums of products! I eagerly translated my data for the top light into the naive algebraic expression, and then attempted to copy-cat the simplificiations from that site:
ĀB̄CD̄ + ĀBCD̄ + AB̄C̄D + ĀB̄CD + AB̄CD + ĀBCD1
alright let’s get my hands dirty and factor some stuff out
(B̄ + B)ĀCD̄ + AB̄C̄D + (Ā + A)B̄CD + ĀBCD
cool, I just learned from The Internet that (A + Ā) is always true so we can drop that right out
ĀCD̄ + AB̄C̄D + B̄CD + ĀBCD
okay I’m out of ideas
Even a light switch system this confusing can’t be that complicated. Also, there’s no way that people who design systems of logic gates for a living still do it this way. (Yes I know the computers are actually the ones doing it for the professionals.)
As it turns out, if I had taken a digital electronics course and/or paid attention in my Discrete Algebra course, I would have learned about Karnaugh maps, which are a pretty clever trick. They encode truth tables in just such a way every move from a square to an adjacent square is a single bit flip (including falling off the edges – so it’s actually a torus!), which means that blocks of zeroes or ones that are in lines or squares are all closely related. Which is to say, they can be represented with relatively fewer terms. So I whipped up Karnaugh map for each light, because the Wikipedia page happened to have an example of how to do with 16 entries. What are the chances?
AB
CD
| 00 | 01 | 11 | 10 | |
| 00 | 0 | 0 | 0 | 1 |
| 01 | 0 | 0 | 0 | 1 |
| 11 | 1 | 1 | 0 | 1 |
| 10 | 0 | 1 | 0 | 1 |
Top Light
AB
CD
| 00 | 01 | 11 | 10 | |
| 00 | 0 | 0 | 0 | 0 |
| 01 | 0 | 0 | 0 | 1 |
| 11 | 1 | 1 | 0 | 1 |
| 10 | 1 | 1 | 0 | 0 |
Bottom Light
Then you find rectangles like they describe on Wikipedia, and back out the boolean algebra expressions that describe them:
ĀC + AB̄D
That’s the bottom light. I started with that one because it’s simpler.
AB̄ + ĀBC + ĀCD
That’s the top light. Interesting to note: the rectangles represented by the last two terms overlap. They both include the case ĀBCD.2
In fact, I was surprised by how much simpler an expression this process yielded. Scroll back up and look at my first attempts with boolean algebra expressions – it would have taken a lot of staring and comparing this group of symbols, some of which are negated just so, with that group of symbols, some of which are negated just so, in order to factor out commonalities which could be reduced.
That said, look at how ridiculous this is. Let’s attempt to interpret ĀC + AB̄D, which is the bottom light.3
First off, notice that all four symbols are present. This means that all four switches can control this light, but more importantly, it means I’m not crazy and it really is weird and confusing. Maybe the electrician was the crazy one.
Secondly, notice there are two groups, one of which has A and the other of which has Ā. The plus sign can be read as an “or”, which is to say, either the switch combination ĀC or the combination AB̄D is necessary to turn the light on. An English interpretation: if A is off, C controls the switch. If A is on, both B and D are necessary to control the switch.
Since this is the downstairs light, and the only switch downstairs is D, you better hope that A and B are set correctly when you’re downstairs – otherwise flipping D isn’t going to do anything at all. This exact experience was my daily life. Thankfully, if you’re upstairs, you can turn off the downstairs light without going downstairs – you just have to make sure you don’t try to hit C when you’re in the AB̄D state, or B while you’re in the ĀC state, since they won’t do anything.
Or you can just mash the switches and hope for the best.
-
Excuse the tiny, tiny negation bars. I couldn’t figure out why the proper combining overline
̅wouldn’t work. ↩ -
One could come up with many different representations that don’t have overlapping rectangles, up to and including one that has a term for each 1. That would be equivalent to the original, lengthy boolean algebra expression I started with, which defeats the point of Karnaugh maps. This expression has fewer terms, and simpler terms, than any other representation that doesn’t have overlapping terms. ↩
-
The interpretation of the control scheme for the top light is left as an exercise to the reader. ↩