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

Question

In short, this is an assignment question for a course I am taking - the exact wording is this:

"Given n Boolean variables, how many 'semantically' different Boolean functions can you construct?"

Now, I had a crack at this myself - and got pretty stuck. The question doesnt state how many boolean operators there are (and, or, xor, nand, nor, iff, implies, not) nor does it state whether brackets should be used, i.e. a ^ (b v c) is different from (a ^ b) v c.

So, my question for you is - is this question possible given the limited information available?

Is it going to be something like ${n^x}$ where x is the number of boolean operators.

Any direction here would be greatly appreciated.

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

Answer 2

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.

Answer 3

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