I have tried looking it up on the Internet; however, most of the results did not make sense to me.
I know that the statement is true, but how do you mathematically prove it?
For reference the proof is "If $f:B^n \to B$ then the number of possible functions is $2^{2^n}$."
An answer should list out all of the steps of the proof explicitly.
In my Boolean Algebra textbook and another popular textbook, they only gave an unsatisfactory explanation for the theorem:
For 0 variables there is one True function and one False function so $2^{2^0} = 2$; for 1 variable there are True, False, Negation, and Identity functions so $2^{2^1} = 4$; for 2, $2^{2^2} = 2^4 = 256 $. They are attempting to show a pattern; I am not satisfied with this.
Best Answer
If there are $n$ variables $\{x_1,\cdots,x_n\}$, there are $2^n$ ways to assign values to these variables, with each one taking value $0$ or $1$.
Now for each of the $2^n$ assignments of values to these variables, you could have the output of the function be $0$ or $1$. You have to choose $0$ or $1$ for each of the $2^n$ assignments of values. There are $2^{2^n}$ ways to do this. In other words, there are $2^{2^n}$ to assign a value of $0$ or $1$ to each of the $2^n$ assignments of values for all $n$ variables. In other words, there are $2^{2^n}$ functions from $\{0,1\}^n$ to $\{0,1\}$.