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