Let $x_1,x_2,x_3,x_4$ be boolean variables (i.e $x_i \in \{0,1\}$)

Consider $f(x_1,x_2,x_3,x_4) = x_1 \wedge x_2 \wedge x_3 \wedge x_4 $

I want to write $f$ in terms of two-input NOR gates. I.e, $\mbox{NR}(x,y)= \neg ( x \vee y ) $.

What is the minimum number of NOR gates to write it?

I found that it can be done with 9. Can it be done with less.


Rather than describing the answer, I'm going to describe how you could write a program to find the answer.

Write a program to exhaustively check all functions that can be computed by circuits with 1 NOR gate, all functions that can be computed by circuits with 2 NOR gates, all functions that can be computed by circuits with 3 NOR gates, etc. This would give you the answer.

Here is more detail on how to do that. Represent a function by its truth table (i.e., a 16-bit vector). To find all function representable by $k$ NOR gates, enumerate all functions $f,g$ representable by $i,k-i$ NOR gates, respectively, and then compute the function $\neg (f \lor g)$, for all $0 \le i < k$. Representing $f,g$ as a 16-bit bitvector, you can compute $\neg (f \lor g)$ in two instructions, then you add it to the set of achievable functions. If you represent that set of achievable functions as a bitvector of length $2^{16}$, adding a new function to the set can be done in a few instructions. So, each individual step will be very fast.

Overall, this computation should be feasible. In particular, this computation requires at most $(k-1) \times 2^{16} \times 2^{16} \le 2^{35}$ simple operations, and you are going to do this 8 times, for a total of at most $2^{38}$ simple operations. That should be doable in a few minutes or a few hours on a typical computer.

I leave it to you to implement this and discover the minimal representation you are seeking.


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.