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?
Best Answer
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.