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 , and , we can make a function detecting when no more than one input is active using a single NOT gate:

.

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:

.

Now we know that if 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, .**1 input present:**we should have no more than one input present and or should be present, .**2 inputs present:**we can check that by simultaneously ensuring that either zero or two inputs are present and that and are present, .

Putting all together and adding the symmetrical cases:

.

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