# Create NOT gate from other gates

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.
• It’s also a standard technique. If I remember correctly, $\log n$ inversion gates are sufficient and necessary to recover general circuits. – Yuval Filmus Jul 20 '19 at 14:02