Circular circuitry

What will happen when you switch on these circular circuits?

Age

16 to 18

Challenge level

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving

Being curious Being resourceful Being resilient Being collaborative

This problem involves circuits which feed back into themselves: The output of a gate can be traced through the circuit back into the input of the same gate! This can lead to all sorts of interesting behaviour, which will be explored in this problem. Please note that the gates here are not interactive: they are thought experiments .

What will happen when you switch on these circuits?

What will happen if you change the gates to different types?

The following two circuits have the same gates. Look carefully at the wires which are switched on. What do you notice? What do you think will happen when the switches are flicked on and then flicked off?

Can you create your own feedback circuits? Investigate their properties.

Click here for a poster of this problem.

NOTES AND BACKGROUND

A key concept in computing is that of random access memory : whilst computers logically process commands they are also able to store user inputs whilst a procedure is being followed. Memory is built using logic gate circuits which feed back into themselves. The most simple of these is the 'flip-flop' which you can read about in the Wikipedia article . The flip-flop is a device which has two different stable states, and can thus 'remember' if a switch has previously been flipped.

All credit to Alex Bramham, for this excellent and complete solution;

Each wire can be either on or off. Wires that must be the same have been assigned the same variable. The variables are 1 when the wire is on, and 0 when off. Relationships between these variables model the circuit.

Circuit 1

The AND comparison can be modelled as returning a value equal to the product of the two compared wires. This is because the product is $1$ when both are on $1$ and $0$ otherwise.

$d$ is the result of an AND comparison of $a$ and $b$. $d = ab$. $b$ is the result of an AND comparison of $c$ and $d$, $b = cd$.

This can be substituted into the first equation: $d = acd$, $acd - d = 0$, $d(ac-1) = 0$. And the first can be substituted into the second: $b = abc$, $abc - b = 0$, $b(ac-1) = 0$, $ac-1$ only equals zero when both $a$ and $c$ are $1$, so unless this is the case, $b$ and $d$ will both be off. When $a$ and $c$ are both $1$, the equations simplify to $b = d$, and nothing further can be deduced about the lamps, other than that they are the same.

Circuit 2

The OR comparison returns zero when both values are zero, otherwise it returns one. Subtracting the product from the sum can be used to model this, as it returns zero when the values are zero and one otherwise.

The NOT function returns one for zero and zero for one. Subtracting the value from one models this.

$b$ is the result of an OR comparison of $a$ and $c$, $b = a + c - ac$, $c$ is a NOT function for $b$, $c = 1 - b$ This can be substituted into the first equation: $b = a + 1 - b - a(1-b), b = a + 1 - b -a + ab$ $b = 1 - b + ab$, $2b - ab = 1$, $b(2-a) = 1$. So $b = 1$ and $a = 1$. If $b = 1$, equation two gives $c = 0$, and then equation one makes $a = 1$. Conversely, if $a = 1$, equation one makes $b = 1$, and equation two makes $c = 0$. So there is a unique solution, the switch must be on, and the lamp is off.

Circuit 3

The NAND comparison returns one, unless the two values are both one. Subtracting the product from one models this. Every NAND comparison expressed as an equation involving the values it compares and the result is as follows:

$d = 1 - ac$

$f = 1 - cd$

$h = 1 - dg$

$g = 1 - fh$

$i = 1 - eh$

$j = 1 - ei$

$k = 1 - jL$

$L = 1 - ik$

The NOT functions:

$c = 1 - b$

$e = 1 - c$

If $b = 1$, then $c = 0$ and $e = 1$, the first two equations would make $d = 1$ and $f = 1$. The last three equations become: $j = 1 - i$, $k = 1 - jL$, $l = 1 - ik$ Subbing $j$ and $L$ into $k$ gives $k = 1 - (1-i)(1-ik)$, $k = 1 - (1-i-ik+iik)$, $k = 1-1+i+ik-iik$, $k = i + ik - iik$, $k = i$, $L = k$

Note: $1$ or $0$ squared is still the same value, so $ii$ can be replaced with $i$. $ik$ and $l$ can be replaced by $i$ in the last equation: $L = 1 - ik$, $i = 1 - i$, $2i = 1$. Which is not true for either $0$ or $1$.

A contradiction means that $b$ cannot equal $1$. Now that $b = 0$ is known, the original equations can be updated:

$c = 1 - b, c = 1$

$e = 1 - c, e = 0$

$d = 1 - a$

$f = 1 - d$

$h = 1 - dg$

$g = 1 - fh$

$i = 1$

$j = 1$

$k = 1 - jL$

$L = 1 - ik$

And again with the values of $i$ and $j$: $k = 1 - L$, $L= 1 - k$

So now all the known information is:

$b = 0$

$c = 1$

$e = 0$

$i = 1$

$j = 1$

$d = 1 - a$

$f = 1 - d$

$h = 1 - dg$

$g = 1 - fh$

$L = 1 - k$

If $a = 0$, then $d = 1$, $f = 0$, $g = 0$, $h = 1$.

If $a = 1$, then $d = 0$, $f = 1$, $h = 1$, $g = 0.$ (By looking at the last five equations in order). So $g = 0$ and $h = 1$.

The solution is:

$b = 0$

$c = 1$

$e = 0$

$g = 0$

$h = 1$

$i = 1$

$j = 1$

$d = 1 - a$

$f = 1 - d$

$L = 1 - k$

No more information can be derived.

Conclusion: switch $b$ must be off, switch $a$ does not affect the lamps, though it can be on or off, and exactly one lamp will always light, either one is possible.

It is not valid to consider what would happen when switch $b$ is "flicked on and then flicked off" because if $b$ is on there is a contradiction caused and some wires would be neither on nor off. If switch $a$ was flicked on and off, $i$ and $j$ would remain active, and hence no change to the end part of the circuit.

Or search by topic

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners

Circular circuitry

Why do this problem?

Possible approach

Key questions

Possible extension

Possible support