If we are given only one NOT gate and any number of OR and AND gates, then, can we simulate more NOT gates?


Consider a circuit having a single NOT gate, computing some function $f(x)$. We can write $f(x) = g(x,\lnot h(x))$, where $g,h$ are monotone functions.

Consider now a sequence of inputs $x_0 < x_1 < \cdots < x_n$ (i.e., $x_0$ is the zero input, and $x_i$ is obtained from $x_{i-1}$ by changing one bit from 0 to 1). Since $h$ is monotone, it is either constant on $x_0,\ldots,x_n$, or $h(x_0) = \cdots = h(x_i) = 0$ and $h(x_{i+1}) = \cdots = h(x_n) = 1$ for some $i$. In the former case, $f(x_0) \leq \cdots \leq f(x_n)$. In the latter case, $f(x_0) \leq \cdots \leq f(x_i)$ and $f(x_{i+1}) \leq \cdots \leq f(x_n)$. This means that the sequence $f(x_0),\ldots,f(x_n)$ flips from 1 to 0 at most once.

It follows that the complement of the parity function on three bits cannot be computed using a single NOT gate. Indeed, if it could, then consider $x_0=000$, $x_1=001$, $x_2=011$, $x_3=111$. Then $f(x_0),f(x_1),f(x_2),f(x_3)=1,0,1,0$ flips twice from 1 to 0.

This shows that you cannot simulate an arbitrary number of NOT gates using a single NOT gate.

  • $\begingroup$ This is an ingenious answer. It can be generalized easily to show that even together with unbounded supply of OR and AND gates, a bounded number of NOT gates cannot simulate an arbitrary number of NOT gates. $\endgroup$ – John L. Jul 20 '19 at 7:50
  • 1
    $\begingroup$ It’s also a standard technique. If I remember correctly, $\log n$ inversion gates are sufficient and necessary to recover general circuits. $\endgroup$ – Yuval Filmus Jul 20 '19 at 14:02
  • $\begingroup$ This is probably one of the reasons that in early IC development, the NAND and NOR gates were far more plentiful and popular than the AND and OR versions. The "built in" NOT function made them more versatile. $\endgroup$ – Peter Camilleri Jul 21 '19 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.