snippetMinor
Create NOT gate from other gates
Viewed 0 times
createothergatesgatefromnot
Problem
If we are given only one NOT gate and any number of OR and AND gates, then, can we simulate more NOT gates?
Solution
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.
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.
Context
StackExchange Computer Science Q#111968, answer score: 5
Revisions (0)
No revisions yet.