Consider 3 boolean variables $x, y$ and $z$. Then you can form a total of 8 expressions using each variable or its complements exactly once in each expression i.e. $xyz$, $xyz′$, $xy′z$, $xy′z′$, $x′yz$, $x′yz′$, $x′y′z$, $x′y′z′$ where $x′$ represent complement of $x$. Each of these terms is called a minterm. So if we have $n$ variables, we can have a total of $2^n$ minterms.

Now any boolean function which involves these n variables can be expressed as a sum of one or more of these minterms.

For a better explanation, look into this wiki link here.

So what is the possible number of functions using $n$ boolean varibles? Below is my attempt:

Since we have $n$ boolean variable, that means we have $2^n$ possible minterms and any function using given $n$ boolean variables is essentially a sum of one or more of these. So this essentially reduces our problem to the number of ways that we can pick these minterms.

For each minterms, we have two options, either to select it or to not. Repeating this for every minterm, We have that total number of possible functions is:

$2*2*2*....... (2^n times)$

$= 2^{2^n}$ possible functions. But the solution states that the total number of possible functions is $2^{2n}$.

Where am I going wrong?

  • 1
    $\begingroup$ There seems to be a counterexample for $2^{2n}$. For $n=0$, you get $2^0=1$, and $2^{2^n}=2$. There are two possible functions, $0$ and $1$. $\endgroup$ – GoodDeeds Sep 21 '16 at 5:30
  • $\begingroup$ Yep, it seems to me that your logic is correct. There should be $2^{2^n}$ possible functions from $n$ boolean variables to a boolean value. $\endgroup$ – Bolton Bailey Sep 21 '16 at 5:31

There are $2^n$ possible input vectors to the boolean function, and $2$ possible outputs, so you have $2^{2^n}$ possible boolean functions (as in this question).

The person who wrote the answer probably reversed the inputs and the outputs -- if you have a function which takes a boolean, and outputs a length n boolean vector, there are $2^{2n}$ such functions.


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.