Why is the amount of boolean functions $2^{2^n}$ if the number of functions between two discrete sets is $m^n$?

Question

Recently I've learned that the amount of boolean functions $B_n$ which take $n$ inputs is $2^{2^n}$ . However I don't understand why that's the case and try to deduct that.

It seems counterintuitive to me because the number of functions between two discrete sets where $|A|=n$ is $n$ and $|B|=m$ is $m^n$. Then why is the amount of boolean functions $2^{2^n}$, and not $2^n$ for example?

Answer 1

Each of the input variables has two possible values, $0$ or $1$. So $n$ input variables allows for $2^n$ possible combinations of input values. The single output variable has $2$ possible output values of course.

So such boolean function maps from a set of $2^n$ elements to a set of $2$ elements. This means $|A|=2^n$ and $|B|=2$, giving $|B|^{|A|}=2^{2^n}$ boolean functions on $n$ inputs.

For example for $n=2$ we have $A=\{(0,0),(0,1),(1,0),(1,1)\}$, a set with $4$ elements, and $B=\{0,1\}$ has $2$ elements. For each of those four input combinations there is a choice of two outputs, leading to $2^4$ possible mappings.

Answer 2

$n$ Boolean inputs give $2^n$ possible combinations of inputs

Each combination can lead to $2$ possible Boolean outputs

So by your argument, the number of Boolean functions is $2^{\left(2^n\right)}$

With $n=1$ with inputs $0$ or $1$, this suggests $2^{2^1} = 4$ possibilities, such as:

• $f_1(0)=0, f_1(1)=0$
• $f_2(0)=0, f_2(1)=1$
• $f_3(0)=1, f_3(1)=0$
• $f_4(0)=1, f_4(1)=1$