36
$\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
  • $\begingroup$ What do you know about constructing Boolean functions from the course? It seems to me that you're on the right track when you mention a function $n^x$. How about this: How many different possible functions are there if you have zero variables? Think of the possibilities. How many different possible functions are there if you have one variable? Think of the possibilities. Now how many are there when you have two variables? Think of the possibilities. Now add up all of the possibilities. Does this help? $\endgroup$
    – Matt Groff
    Sep 26, 2013 at 1:20
  • $\begingroup$ I did try that initially - however, the list got quite large. For 1 variable the answer is obviously 2 (a and ¬a) for 2 variables - its much larger, (a ^ b, a V b, etc) followed by the ¬ on each side, then on both sides. For 3 variables - its even worse, as with the example above a ^ (b v c) is semantically different from (a ^ b) v c $\endgroup$ Sep 26, 2013 at 1:45
  • $\begingroup$ I'm still wondering about what you've covered. For instance, you may have covered truth tables. The main reason I'm wondering is because of how we, together, can construct Boolean functions. You've got the concept/example already that for one variable, you have either $a$ or $\neg a$. Now, the trick seems to be to forget about "what the function is", and instead to concentrate on "what we can get". By this I mean for two variables, we can get $a$ or $\neg a$ for $a$, and $b$ or $\neg b$ for $b$. How many combinations can you get between the two? (Each can take on one of two values) $\endgroup$
    – Matt Groff
    Sep 26, 2013 at 2:20
  • $\begingroup$ We have covered truth tables, and proof by contradiction and induction. From what you are saying it sounds like "semantically different function" is a unique entry in a truth table, however the truth table for a ^ b looks the same as the truth table for a V b, however each of these is "semantically different", correct? $\endgroup$ Sep 26, 2013 at 2:27
  • 4
    $\begingroup$ Yes. For the case of Boolean variables, there are really only $2^{{\color{red}{2}}^n}$ combinations. Either a particular combination out of the $2^n$ entries in a truth table is true, or it is not. Thus the $2^{{\color{red}{2}}^n}$ total combinations. $\endgroup$
    – Matt Groff
    Sep 26, 2013 at 3:18

7 Answers 7

30
$\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$ I had read in a textbook that there are in general $k^{k^n}$ different functions you can make in a k-valued logic with n variables, but I had never seen a proof. Thank you for writing this, as it has become a reference for my ~2 year long question. $\endgroup$
    – user400188
    Sep 11, 2020 at 3:39
26
$\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: 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
$\endgroup$
1
  • $\begingroup$ So you are saying that given all n length binary sequences (whose number is $2^n$) we can get a single output of length $m=2^n$ and number of such output is then $2^m = 2^{2^n}$. $\endgroup$
    – Ankit Seth
    Sep 12, 2018 at 7:33
6
$\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$ I'm not sure I quite follow, if we choose three variables: a,b and c. How do you get 256 combinations? Also, this doesn't take into account the ways they can be combined (the number of boolean operators) $\endgroup$ Sep 26, 2013 at 1:50
  • 1
    $\begingroup$ It is Boolean functions we are counting, not combinations of operators. There are infinitely many ways to express each Boolean function. For a silly example, $p_1$, $p_1\land p_1$, $p_1\land p_1\land p_1$ and so on all give us the same Boolean function. So does $\p_1\lor p_1$, and many many others. And yes, there are $256$ different truth tables in the case $n=3$. $\endgroup$ Sep 26, 2013 at 2:01
  • $\begingroup$ Ok, so it sounds like you are saying it is the entries in the truth table we are counting, if p1 V p1 gives us the same function as p1 ^ p1 ^ p1. Does this reduce to a situation where "semantically different" only corresponds to the number of different assignments in a truth table? a ^ b ^ c and a V b V c both will create identical truth tables? I'm still not sure where 256 comes from, surely there are only 001, 010, 011, etc. $\endgroup$ Sep 26, 2013 at 2:31
  • 1
    $\begingroup$ Yes, semantically different means different truth table. Because I am lazy, take $n=2$. So we have $00$, $01$, $10$, $11$. Now on the right hand side of the truth table, the truth value of $f$ at $00$ could be $0$ or $1$. For each of these choices, the truth value of $f$ at $01$ could be $0$ or $1$. And so on. So $2^4$ choices. $\endgroup$ Sep 26, 2013 at 2:52
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$
2
$\begingroup$

Consider this: There are n variables which means there are 2n 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 2n 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 2n minterms makes this function defining string 2n positions long. At each position there can be a 1 or a 0. Hence the total number of different strings is 22n which is the total number of different functions and also the total number of different sums that the minters can be combined into.

$\endgroup$
1
$\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$
1
$\begingroup$

This is a classic problem in circuit theory. See https://scholar.google.co.nz/scholar?hl=en&as_sdt=0%2C5&q=Classification+of+Boolean+Functions&btnG=.

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .