how many semantically different boolean functions are there for n boolean variables?

Solution 1:

This question, in a sense, is a question of combinations.

We can start with a single-valued function of Boolean variables. I claim that there are $2^n$ combinations of a single-valued function. For instance, if we start with one variable, there are two combinations; namely, $a$ and $\neg a$. If we have two variables, there are four combinations. This is because we can have, for $a$, either $a$ or $\neg a$. Then, for $b$, we can have either $b$ or $\neg b$. So there are four combinations between these two variables. Similarly, for three variables, there are $2 \times 2 \times 2=2^3$ combinations between these variables.

Now, to consider the set of ALL Boolean functions, we have to consider again each of these combinations. We can say that there are $2^\text{combinations}$ different combinations between Boolean variables. This is because, for each combination, it can be true or false. So in the paragraph above, we have stated that there are $2^n$ combinations between the variables. Each of these combinations can be true or false for a particular variable assignment. So, again, we get $2^\text{combinations} = 2^{(2^n)}$ combinations between them all.

Solution 2:

Let's reverse-engineer this: In the case of $n=2$ there are $2^{(2^n)}=2^4=16$ distinct functions: $F0...F15$. Below you can find the resulting truth table. Each column represents the outcome for function $F0...F15$

$F0(0,0) = 0$

$F0(0,1) = 0$ ....

$F15(1,1)=1$

A   B|  F0  F1  F2  F3  F4  F5  F6  F7
0   0|  0   0   0   0   0   0   0   0
0   1|  0   0   0   0   1   1   1   1
1   0|  0   0   1   1   0   0   1   1
1   1|  0   1   0   1   0   1   0   1

A   B|  F8  F9  F10 F11 F12 F13 F14 F15
0   0|  1   1   1   1   1   1   1   1
0   1|  0   0   0   0   1   1   1   1
1   0|  0   0   1   1   0   0   1   1
1   1|  0   1   0   1   0   1   0   1

To verify why there are 16 distinct functions, we start with our first function $F0$ which maps any given pair $(A,B)$ to $FALSE$. For the next function $F1$ it is sufficient to differ at only one position in order to be become distinct from $F0$ $=>F1(A=1,B=1)=1$. The same is true for $F2$ with regard to $F1$ and so forth. Finally we arrive at $F15$ which becomes distinct from $F14$ by simply mapping all inputs to TRUE.

Let's also do the math:

How many different ways can you pick k items from n items set with repetition ( $k=2$ $n=2$ )? $n^k$ = $2^2=4$. There are 4 ways to form a pair $(A,B)$ hence $F(A,B)$ yields also 4 outcomes $k1,k2,k3,k4$. How many different ways can you pick k items from n items set with repetition ( $k=4$ $n=2$ )? $n^k$ = $2^4=(2^{(2^2)})=16$. Thus 16 semantically different boolean functions.

See the respective function names and symbols below. (Source: http://mathworld.wolfram.com/BooleanFunction.html)

function            symbol          name
F0                  0               FALSE
F1                  A ^ B           AND
F2                  A ^ !B          A AND NOT B
F3                  A               A
F4                  !A ^ B          NOT A AND B
F5                  B               B
F6                  A xor B         XOR
F7                  A v B           OR
F8                  A nor B         NOR
F9                  A XNOR B        XNOR
F10                 !B              NOT B
F11                 A v !B          A OR NOT B
F12                 !A              NOT A
F13                 !A v B          NOT A OR B
F14                 A nand B        NAND
F15                 1               TRUE

Solution 3:

Think about the truth table, say for a concrete $n$ like $n=3$. There are $2^3$ sequences of length $3$ made up of $0$'s and/or $1$'s. More generally, there are $2^n$ sequences of $0$'s and/or $1$'s of length $n$.

To make a Boolean function, for each of these sequences, we can independently choose the value of our function at the sequence.

Thus there are $2^{(2^n)}$ Boolean functions of $n$ variables.

Solution 4:

Here let me add my part. Consider we are having two logic variables a and b. These two variables may be 0 or 1. So the total possibilities are

    a  |  b
    -------
    0  |  0    =  a'b'
    0  |  1    =  a'b
    1  |  0    =  a b'
    1  |  1    =  a b
    -------

___2__ X __2__ = 4 possibilities
0 or 1   0 or 1

Now its time to find total number of functions for 2 variables!...We found 4 terms for 2 variables in above example, isn't it? So for A Equation or Function may contain any number of 4 terms that we have found above. Like this

    a'b' + a'b             - contain two terms
    a b'                   - contain single term
    a'b' + a'b + a b       - contain three terms
    a'b' + a'b + ab' + a b - contain four terms (maximum possibilities)

So the total combination(count) of functions for 2 variables are

_______2_______ X _______2_______ X _______2_______ X _______2_______ = 16 possibilities
term or no term   term or no term   term or no term   term or no term

       -                -                  -                 -        = 0(false)

       ab               -                  -                 -        = ab

       -               a'b                 -                 -        = a'b

       -                -                  ab'               -        = ab'

       -                -                  -                 a'b'     = a'b'

       ab              a'b                 -                 -        = ab + a'b

       -               a'b                ab'                -        = a'b + ab'

       -                -                 ab'               a'b'      = ab' + a'b'

       ab               -                 ab'                -        = ab + ab'

       ab               -                  -                a'b'      = ab + a'b'

    ..... //some more possible combinations like this, ( to lazy to type it;) )
    and finally it would be like 

       ab              a'b                ab'             a'b'        =  1 (True)

So The combination(count) of functions that can be formed by n variables is 2^2n

n = 2

2 ^ 2*2 = 16