Possible Boolean functions in n-dimensional space

1.4k Views Asked by At

Each unique assignment of 0-1 values to the $2^n$ possible inputs in $n$ dimensions represents a Boolean function. Therefore, in $n$ dimensions, there are $2^{2^n}$ such unique assignments that can be made, and this $2^{2^n}$ possible functions.

Why are there $2^{2^n}$ such unique assignments not $2\cdot2^{n}$?

2

There are 2 best solutions below

7
On BEST ANSWER
  • You have $2^n$ distinct possible "inputs" to the function: indeed, $\lvert \{0,1\}^n\rvert = 2^n$.

  • For each input $x\in\{0,1\}^n$, the value of a Boolean function $f$ is either $0$ or $1$, i.e. there are two choices for $f(x)$.

Overall, you therefore have $$(\text{number of choices})^{(\text{number of inputs})} = 2^{2^n}$$ different Boolean functions on $\{0,1\}^n$.

One way to see it is that the choice for each "input" is independent from the choice of the others. You chose the value for the first input: 2 choices. Then you choose for the second one: 2 choices as well, no matter what you had chosen for the first input. That means you have $2^2=4$ possibilities for the value on the first two choices: $(0,0)$, $(0,1)$, $(1,0)$, and $(1,1)$. And so on: the number of choices for the $k$ first inputs is $2^k$, and overall for $k=2^n$ you get the result.


Note that this is not specific to Boolean functions: if $A,B$ are two sets (let's say finite for simplicity), then the number of functions from $A$ to $B$ is $\lvert B\rvert^{\lvert A\rvert}$.

0
On

Oh, It's from Neural Networks- A classroom Approach By Satish Kumar. Chapter 4. Geometry of Binary Threshold Neurons 4.3 Space of a Boolean Function.
Here in Range Set you have only 2 Answers i.e. either 0 or 1, And for n=2, you have 4 different choices [0,1] x [0,1] (i.e. Cartesian product of two closed intervals.) {00,01,10,11}.
So Your answer is always in 0 or 1 Because it's a Boolean Function so....
Always f: 2^n -> 2.
NOT LIKE f:2^n -> 2^m.
Just as earlier mentioned by Clement it's
(No of Choices)^ 2^n.