Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
can you define what is a non-degenerate boolean funtion? –  Mohan Jan 19 '13 at 7:59
    
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 –  Nicole Grefder Jan 19 '13 at 8:04
    
Have someone any ideas? –  Nicole Grefder Jan 19 '13 at 8:26
    
Same question as this one –  David Moews Jan 19 '13 at 8:38
    
ops...I didn't see it...Thanks –  Nicole Grefder Jan 19 '13 at 8:42

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
I get it, thank you :) –  Nicole Grefder Jan 19 '13 at 8:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.