Prove that with n variables there are 2^2^n possible boolean functions

Question

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.

Answer 1

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\}$.

Answer 2

There's quite a few ways to see it: here's two of them. There are $2^n$ possible inputs for a Boolean function on $n$ variables, and for each input, there's two choices of the output. That gives $2\cdot 2\cdot\ldots\cdot 2=2^{2^n}$ possible choices, and each of these gives a distinct function.

If you want an inductive proof, you can easily show it for $n=1$ (write out all of them if you need more convincing). Now suppose it is true for some $n\geq 1$. For the $n+1$ case, if we fix the last bit $x_{n+1}$ to $0$, then the the Boolean function restricts to a Boolean function of the first $n$ variables, of which we know there are $2^{2^n}$ choices by hypothesis. The same is true when we fix the last bit to $1$. We can choose these independently, so in total there are $$ 2^{2^n}\cdot 2^{2^n}=2^{2^n+2^n}=2^{2^{n+1}} $$ such functions, completing the induction.

Answer 3

If you are familiar with truth-tables, it's pretty straightforward to see:

You know that for a boolean function with $n$ variables, the truth-table will have $2^n$ rows. And, since in each row the function can take on the value of True or False, you immediately obtain that there are $2^{2^n}$ different possible truth-functions.

Answer 4

The number of functions for a given number of variables (inputs) is determined by the number of ways you can choose outputs of 0’s and 1’s (results) for that number of inputs.

Consider only the final column of a truth table…the “results column”.

(Think of that column as a row vector instead of a column…since that’s how we write numbers in binary…it’s easier that way when we’re talking about a relation between the number of digits in our rows (the number of variables) and the number of possible ways to choose your “results” in that column)

How many different ways can we arrange the digits in our output column for a given number of input rows in our table? That’s the number of possible functions.

If your table has two rows, then you will only have two digits in your output column…and with two digits we can get four different arrangements of 0’s and 1’s in that column (for the two given rows).

If your table has four rows (there will always be a power of 2 number of rows), then its output column will have 4 digits to work with giving 16 possible arrangements of 0’s and 1’s in that column for the four given rows.

8 rows -> 2^8 ways to arrange 0’s and 1’s in the output column…and so on.

So your answer is found in the number of ways you can arrange the 0’s and 1’s in the output column for a given number of rows.

Again, to think of the output column itself as a binary number, just “read it sideways”.