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

$\begingroup$

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.

$\endgroup$ 11

7 Answers

$\begingroup$

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.

$\endgroup$ 1 $\begingroup$

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: )

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

$\endgroup$ 1 $\begingroup$

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.

$\endgroup$ 4 $\begingroup$

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

$\endgroup$ $\begingroup$

Consider this: There are n variables which means there are 2ⁿ entries in the truth table. The number of variables determine the number of rows in the truth table

A minterm exists for every row in the truth table. This means that there are 2ⁿ minterms . The column of minterms on the far right.

Each function can be written as a sum of minterms . The minterm is either in the sum or not in the sum.

This means that such a function can be specified with a string of 1's and 0's with the following meaning:

• if at position i there is a 1 then the i-th minterm is part of the function sum.
• if there is a 0 instead then that minterm is not part of the sum.

Each function can be expressed as a sum of one or more minterms

It is clear that having 2ⁿ minterms makes this function defining string 2ⁿ positions long. At each position there can be a 1 or a 0. Hence the total number of different strings is 2²ⁿ which is the total number of different functions and also the total number of different sums that the minters can be combined into.

$\endgroup$ $\begingroup$

I do not know about semantically correct but it is pretty easy to compute even more general case: how many are there functions of $k$ arguments, each may take n values and function may produce one of m outcomes for every combination. As this blog says, your arguments provide $n^k$ combinations of values. You can interpret your function as a function of single argument, which takes one of $n^k$ values. Now, you start by placing all possible functions into one group

[all possible functions]

and apply the first value of $n^k$. The functions of the group will respond with $m$ various outcomes. This way, you have resolved one group into $m$ subgroups.

[responded with 1][responded with 2] ... [responded with m]

On the next step, you apply next value of $n^k$ to each subgroup. Again, functions in those subgroups will split into $m$ further subgroups. After two steps, you have resolved all your functions into $m^2$ subgroups. After applying all $n^k$ input values, you have resolved the initial group into $m^{n^k}$ subgrops. You have no more tests to apply. You, therefore, consider all functions in the resulting subgroups identical. You have got $m^{n^k}$ different functions. Isn't it beatiful?

In case the function arguments and values belong to the same type (type is a range of values that variable can take), you have $m=n$ and $n^{n^k}$ different functions. Particularly, in case the type is binary, we may have $2^{2^k}$ functions. I am sure that all functions are realizable (there is a notion of functional completness), and, thus are semantically correct if that is what you mean.

$\endgroup$ $\begingroup$

This is a classic problem in circuit theory. See .

One of the difficulties in getting started is deciding how you'll define "semantically equivalent"; then you'll get pretty deep into group theory before you'd be able to describe your answer accurately in a few paragraphs on e.g. StackExchange.

Golomb's 1959 paper in IRE Trans Circuit Theory is a good place to start:

"The Boolean functions of k variables, f(x1, x2, ..., xk), fall into equivalence classes (or families) when two functions differing only by permutation or complementation of their variables are considered equivalent. The number of such families is easily computed, as illustrated by Slepian [l]. The next step is to discover the invariants of the logic families, and determine to what extent they characterize the individual families. Given the class decomposition, one also wishes to select a "representative assembly", with one delegate from each family. That is, canonical forms for the logics are sought, with every family having its characteristic canonical form..."

$\endgroup$