1
$\begingroup$

How many bits we can negate using two/three NOT gates ?

I am newbie at this subject so I ask for help. It is about circuits.

Edit
After reading link given in comments by @D.W I think that I can negate bits without NOT gates. I know that it is impossible, however I don't know where I am wrong.

Simply, I can sort bits, then I can find $i-$th bit that it is first bit $1$ in sorted sequence.
so, $b_{1,...,i-1}=0$ and $b_{i,...,n}=1$. Now, I now where I should return $0$ and where $1$. So I write in circuits something like:

b_0 -> 1 = c_0
b_1 -> 1 = c_1
...
b_{i-1} -> 1 = c_{i-1}
b_i -> 0 = c_i
...
b_n -> 0 = c_n

Then, I sort bits $c_1,...,c_n$. I didn't use NOT gates, the trick was to using constants $0$ and $1$.
Where am I wrong ?

$\endgroup$
8
  • $\begingroup$ Which gates are we allowed to use? (presumably NAND is not allowed, for instance) Are there fan-in/fan-out limits? What have you tried? Have you tried seeing if you can negate 2 bits using 1 NOT gate? negate 3 bits using 2 NOT gates? negate 4 bits using 3 NOT gates? There are only so many circuits to consider.... $\endgroup$ – D.W. Apr 19 '17 at 22:02
  • $\begingroup$ @D.W can you show me at begin 2 bits using 1 NOT ? I tried to solve it but no result $\endgroup$ – user54001 Apr 20 '17 at 18:37
  • 1
    $\begingroup$ I haven't tried to solve it myself, but you should be able to quite easily determine whether it is possible. Any approach that uses one NOT gate has the form $t = f(x_1,x_2)$, $u = \neg t$, output $y = g(x_1,x_2,u)$ where $f,g$ are monotone functions. There are only 6 monotone functions with two inputs, and only 29 monotone functions with three inputs. So, write a program to examine all $6 \times 29$ cases and see what you find. Work your way up from there (3 bits with 1 NOT? 3 bits with 2 NOTs? etc.), see how far you can get and where you get stuck, and update the question accordingly $\endgroup$ – D.W. Apr 20 '17 at 19:49
  • $\begingroup$ I don't undestand your hint. On input we have two bits: $x_1, x_2$. We would like to get on output $\neg x_1, \neg x_2$. What does mean here $f,g, monotonous$ I have no idea. Could you try to explain it in more clear way, please ? $\endgroup$ – user54001 Apr 20 '17 at 21:08
  • $\begingroup$ You're right. I should have written $t=f(x_1,x_2)$, $u= \neg t$, $y_1 = g(x_1,x_2,u)$, $y_2 = h(x_1,x_2,u)$. The question is whether there exist monotone boolean functions $f,g,h$ such that $y_1 = \neg x_1$ and $y_2 = \neg x_2$ always holds. You can check whether this is the case by writing a program to examine all $6 \times 29 \times 29$ possible combinations of monotone functions $f,g,h$. (Any monotone boolean function can be implemented with a circuit that uses only AND and OR gates, no NOT gates; and vice versa.) $\endgroup$ – D.W. Apr 21 '17 at 5:04

Your Answer

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