I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested in the random algorithmic aspects of the notes and have never studied Boolean functions before.
Claim 5.4: Almost all $n$-input Boolean functions require circuits of size at least $2^{n}/n$
The proof goes as follows:
Proof: (sketch) Let $N(S)$ be the number of circuits of size $S$. To bound $N(S)$, note that each gate has two possible inputs and $16$ functions, so there are $16\times S^{2}$ choices for a single gate, so the number of circuits is $N(S) \leq (16 ∗ S^{2})^{S}$. There are $2^{2^{n}}$ different functions with $n$ inputs. A calculation shows that if $S < 2 ^{n}/n$, then $N(S)/2^{2^{n}} \rightarrow 0$ as $n \rightarrow \infty$.
Questions:
1) (NOT REGARDING PROOF) Firstly they mention briefly what a gate is but can every boolean function be represented using a series of gates? On page 6 they seem to mention a boolean function has $n$ inputs ($x_{1},...,x_{n}$) and $1$ output, and then just jump to a notion of a gate without really linking them together.
2) (REGARDING PROOF) I understand since each gate has two inputs for example $x_{2},x_{5}$ and $|\{0,1\}^{2}|=4$ each of these pairs can be assigned two values $0$ or $1$ and so there are 16 possible functions. How did they get $16 \times S^{2}$ possible choices for each gate and more importantly what do they mean here by choice?
3) (REGARDING PROOF) How does the deduction that if $S<2^{n}/n$ then then $N(S)/2^{2^{n}} \rightarrow 0$ as $n \rightarrow \infty$ complete the proof?
I really appreciate any help.
This is a partial answer (I don't really know how to answer question 2)
Question 1) Yes. Every boolean function can be expressed by a series of gates. Actually even few gates are needed for the completeness. For example the most common restriction is that the pair of gates $not$ and $and$ gives completeness. An other example is that any function can be represented by a series of $nand$ gates only.
Question 2) I am not sure for this one. But I think what the mean by choices is the choice of the function for the gate and the way to plug the gate. As you said there are 16 function possible. Moreover, there are S possible choices for each inputs thus $S^2$. What's bugs me is that for me there are $S+n$ possible choices for the input since you have to plug the inputs of the circuit as well but even with $(S+n)^2$ I doubt it would change the outcome of the theorem.
Question 3) Notice that (adding an identity gate), for all circuit of size $S$ there is a circuit of size $S+1$ achieving the same function. Hence the number of function that can be represented by circuit of size smaller or equals to $S$ is lower or equal to the number of circuit of size $S$. Thus $N(S)/2^{2^n} \to 0$ gives you that for $n$ large enough there are much more functions of arrity $n$ than circuit of size $S$ hence the conclusion of the theorem.