### Procedure Solver

Can you think like a computer and work out what this flow diagram does?

Can you set the logic gates so that this machine can decide how many bulbs have been switched on?

### Not Another NAND!

Prove that you can make any type of logic gate using just NAND gates.

# Circular Circuitry

##### Stage: 5 Challenge Level:

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$
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.