# An n-bit boolean function maps 0/1 strings to 0 or 1

$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.

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