Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
