# Universality with only two NOT gates

In a previous post we have asked how many NOTs are needed to compute an arbitrary Boolean function. In this post we will see that only two NOT gates are enough.

### Building 3 NOT gates starting from 2

If we call the inputs $X$, $Y$ and $Z$, we can make a function detecting when no more than one input is active using a single NOT gate:

$\displaystyle f(X, Y, Z) = \overline{XY + YZ + XZ}$.

Detects when no more than one input is active.

By selecting only the cases where at least one input is present, adding a term to detect when all the inputs are active and using an additional NOT gate, we can detect when exactly zero or two inputs are active:

$\displaystyle g(X, Y, Z) = \overline{f(X, Y, Z)(X + Y + Z) + XYZ}$

$\displaystyle = \overline{\overline{XY + YZ + XZ}(X + Y + Z) + XYZ}$.

Detects when zero or two inputs are active.

Now we know that if $X$ is not present, we either have:

• 0 inputs present: we can check that by simultaneously ensuring that we don’t have more than one input present and that we have either zero or two inputs present, $f(X, Y, Z)\cdot g(X, Y, Z)$.
• 1 input present: we should have no more than one input present and $Y$ or $Z$ should be present, $f(X, Y, Z)\cdot(Y + Z)$.
• 2 inputs present: we can check that by simultaneously ensuring that either zero or two inputs are present and that $Y$ and $Z$ are present, $g(X, Y, Z)\cdot YZ$.

Putting all together and adding the symmetrical cases:

$\displaystyle \overline{X} = f(X, Y, Z) \cdot (Y + Z) + (f(X, Y, Z) + YZ)\cdot g(X, Y, Z)$

$\displaystyle \overline{Y} = f(X, Y, Z) \cdot (X + Z) + (f(X, Y, Z) + XZ)\cdot g(X, Y, Z)$

$\displaystyle \overline{Z} = f(X, Y, Z) \cdot (X + Y) + (f(X, Y, Z) + XY)\cdot g(X, Y, Z)$.

Computing NOT X (the other cases are symmetrical).

### Checking the solution

To get independent confirmation, let’s check the truth tables with a simple Python script:

from itertools import product

for x, y, z in product((False, True), repeat=3):
f_xyz = not (x and y or x and z or y and z)
g_xyz = not (f_xyz and (x or y or z) or x and y and z)
not_x = f_xyz and (y or z) or (f_xyz or y and z) and g_xyz
not_y = f_xyz and (x or z) or (f_xyz or x and z) and g_xyz
not_z = f_xyz and (x or y) or (f_xyz or x and y) and g_xyz
assert (not x == not_x) and (not y == not_y) and (not z == not_z)


### Conclusion

As this technique allows us to expand two NOT gates to three and it can be applied repeatedly, we can compute an arbitrary Boolean function with a circuit containing only two NOT gates.

In a following post we will see how I arrived to the solution by using brute force.