$f: \{0,1\}^n -> \{0,1\}$

The function "depends on i" if there exists two $o/1$ strings (A and B) where A and B differ only at position i and $f(A) \not= f(B)$.

How many n-bit Boolean functions do not depend on i?

I have no clue how to start this one. If someone could explain me through the logic of it, I would be extremely grateful, and maybe I could figure out a similar problem. Thank you.

  • $\begingroup$ Can you start by determining how many $n$-bit Boolean functions there are? $\endgroup$ – MartianInvader Apr 2 '14 at 23:32
  • $\begingroup$ @MartianInvader How would I do that? $\endgroup$ – Jessica Apr 3 '14 at 0:16
  • $\begingroup$ Well, what are the choices you make when defining an $n$-bit Boolean function? $\endgroup$ – MartianInvader Apr 3 '14 at 0:45
  • $\begingroup$ Would the total number of functions be $2^{2^n}$? $\endgroup$ – Jessica Apr 3 '14 at 1:08

The answer is $2^{2^{n - 1}}$ n-bit Boolean functions that do not depend on i.

When determining the number of possible string combinations, you don't need to consider the i-th bit so there are $2^{n - 1}$ possibilities. And there are still 2 outputs to think about so the number of n-bit Boolean functions is $2^{2^{n - 1}}$.

Thanks MartianInvader :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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