# Minimal representation of an AND with two-input NOR

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.

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.