The problem I would like to discuss is the following. Most people have seen a room where there are two independent light switches. For instance, in some bedrooms the light can be turned on and off at the entrance door and also at a switch next to the bed. In this case you can turn on the light when you enter the room at night and then later turn off the light when you are already in bed. You can then turn on the light again using the switch at the door. Of course you can also turn on the light again using the switch at the bed. In fact, the light can be turned on and off at any switch in any sequence – i.e. each switch works independently of the state of the other switch.
The question is, how does this work?
To illustrate, let us first draw a diagram of a circuit with one light switch.
Here are two attempts which do not work.
In Attempt 1, the light is turned on only if both Switch 1 and Switch 2 are turned on. So, for instance, if one turns off the light using Switch 1, then one cannot turn on the light using Switch 2.
In Attempt 2, the light is only turned off if both Switch 1 and Switch 2 are turned off. So, for instance, if one turns on the light using Switch 2, then one cannot turn off the light using Switch 1.
So the question then is, what does one have to do to have 2 switches where the light can be turned on and off at each switch, regardless of the state of the other switch? Can you find a solution? (A solution can be found here.)
If you have found a solution with two switches, can you design a circuit with switches?
Let denote a switch and assume that it can have two possible states, namely and as shown in the following picture.
Then let us write, if the light is turned on and if the light is turned off.
Now assume we have two switches and , each of which can take on the values or Then we want to construct a circuit such that if then, say, the light is turned on (the overall state is ) and if the light is turned off (the overall state is ). Mathematically, we can describe this using modular arithmetic by writing
which means that we calculate where is chosen such that (or we can say that if is even and if is odd.)
Notice that attempt 2 above corresponds to the function
Only if do we get i.e. only if both and are in position is the light turned off (state ). In all other cases the light is turned on (state ).
If we have switches, where denoted by then we want a circuit which represents the function
where again we have is if the sum is even and otherwise (notice this is the same as described above for ).
Notice that the modular arithmetic described above has the following properties:
- If and then
- For each state of there exists a state of such that
If you have found a circuit with switches, you can check these properties for the circuit.
Let and with Can you design circuits which “calculate” and