|
I got in my lecture the formula that describe the number of nondegenerate Boolean functions of $n$ variables (or how many boolean functions have no fictitious variables), but we don't have proof for it and I don't understand where did it get from. Here is it $$ \sum_{0\le k\le n} (-1)^k \binom{n}{k} 2^{2^{n-k}}.\qquad $$ I would be greatly appreciated if someone explained it. Thanks. |
|||||||||||
|
|
It can be shown by the Inclusion-Exclusion principle. First, count all possible boolean functions. You need to assign values for $2^n$ possibilities and each value can be $0$ or $1$. So there are a total of $2^{2^n}$ boolean functions. Now let us try to subtract number of functions with a degenerate variable. The degenerate variable can be picked in $\binom{n}{1}$ ways and the we now need to assign values for $2^{n-1}$ variable combinations. So this gives $\binom{n}{1}2^{2^{n-1}}$ ways. But consider the cases where there are two degenerate variables. They are being counted twice in the above list. So we add the corresponding number to compensate for that. But there is multiple counting of functions with $3$ degenerate variables and we should subtract that and so on. Repeating this process, and noting that for $k$ degenerate variables, the corresponding count is $\binom{n}{k} 2^{2^{n-k}}$, you get the required result. |
|||
|
|
