4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ can you define what is a non-degenerate boolean funtion? $\endgroup$
    – Mohan
    Jan 19, 2013 at 7:59
  • $\begingroup$ Boolean function that have no fictitious(dummy) variables - for example if we have f=(0011) and we have 2 variables X and Y, the second variable is dummy because it values, doesn't change the function....sorry for my English $\endgroup$ Jan 19, 2013 at 8:04
  • $\begingroup$ Have someone any ideas? $\endgroup$ Jan 19, 2013 at 8:26
  • $\begingroup$ Same question as this one $\endgroup$ Jan 19, 2013 at 8:38
  • $\begingroup$ ops...I didn't see it...Thanks $\endgroup$ Jan 19, 2013 at 8:42

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I get it, thank you :) $\endgroup$ Jan 19, 2013 at 8:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .