I'm posting here because this strikes me as being fundamentally a math problem compared to a digital design problem.

Given N 2-input NAND gates, what fraction of the possible functions of k-inputs can be realized?

For instance, given four inputs (A, B, C, and D), there are sixteen possible input combinations, each of which can produce one of two possible outputs. Thus there are 65,536 distinct Boolean functions of four variables.

With zero NAND gates, we can use wires to implement four functions:

Y=A

Y=B

Y=C

Y=D

Thus we can implement 1/16,384, or 0.0061% of the possible functions with zero gates.

With one gate, we can implement fourteen of them (if I'm doing things right), or 0.021% of them.

Note that there is some fine print here -- I'm not allowing explicit HI/LO signals to be used (i.e., we can't tie an output statically HI or LO). Similarly, inputs of gates have to be tied to either one of the input signals, or to an output of one of the gates. They can't be tied to HI or LO (or left unconnected).

With two gates, things start getting more interesting because we can't just count how many ways we can connect things, since now we have redundancies (distinct ways of connecting gates that produce the same logic function).

However, we can certainly construct an upper bound on how many functions by assuming that each possible way of connecting them produces a unique function. It then would be interesting to see how quickly and strongly the actual number of functions with N gates falls away from that.

A different, but not completely unrelated, question is how big does N need to be in order to be able to implement all 65536 functions? Once again, we can come up with an upper bound pretty easily, but how much can we chip away at the upper bound.

As we add more NAND gates, we

Yet another interesting avenue would be to ask what the impact of using a different 2-input gate would be. If we use NOR gates, we also know that we can eventually have enough gates to implement all possible functions. But are the two curves already described identical? I believe that they are and that the logic duality proves this, but I haven't given it an rigorous thought to make sure I'm not overlooking something. But we also know that using other gates, such as AND, OR, or XOR, will never provide full coverage. So what is the maximum coverage they can provide and what is the minimum number of gates required to achieve it? There are sixteen possible 2-input gates (though some of them are degenerate). What would a graph showing the coverage for all sixteen options look like.

I'm sure I'm not the first person to ponder these questions, so I wonder if someone has actually published anything on this and also whether this has any value. Almost certainly no practical value of any significance, but it might have some theoretical value, perhaps as being a building block in some other, more useful, theorem.