1
$\begingroup$

How can we compute the degree of boolean function? I encountered with this,while solving a problem given in my assignment module which is,

How many different boolean functions of degree 1 and 2 are there?

The suggest answer in my module is $4$ and $16$,but I don't understand how and what exactly meant by the degree of boolean functions,could somebody explain?

EDIT: I encountered this link today,but I don't understand is it $2^{2^p}$ or $2^{2p}$ ?

$\endgroup$
4
  • $\begingroup$ In your book how is the degree of a function defined? Even better give some more info about the context. $\endgroup$
    – jimjim
    May 1, 2011 at 12:38
  • $\begingroup$ @Arjang:The degree is not defined,that is the problem. $\endgroup$
    – Quixotic
    May 1, 2011 at 16:10
  • $\begingroup$ StackOverflow link. $\endgroup$
    – Quixotic
    May 1, 2011 at 16:17
  • $\begingroup$ I think it is 2^(2^p). On the page you linked to, they found the truth table for the $2^{2^2}$ possible boolean functions of two variables. $\endgroup$
    – Eivind
    May 4, 2011 at 11:20

1 Answer 1

4
+50
$\begingroup$

It would seem that degree refers to the arity of the function, the number of input variables. (But you should check the definition, and the question is not really mathematically sensible without a precise definition.) Since the number of rows of a truth table with $p$ Boolean variables is $2^p$, and each row can get one of two values (true or false), the number of such truth tables is $2^{2^p}$. This is $2$ to the number of rows, since there are two possibilities for each of the $2^p$ rows.

Every such truth table determines a Boolean function in $p$ variables, and every Boolean function in $p$ variables is determined by its corresponding truth table. Thus, the total number of Boolean functions in $p$-variables is $2^{2^p}$. (And this is not the same as $2^{2p}$.)

Thus, when $p$ is $1$, we have $2^{2^1}=4$ Boolean unary functions, and when $p$ is $2$, we have $2^{2^2}=16$ Boolean binary functions.

$\endgroup$
3
  • $\begingroup$ To me, and this is standard terminology in theoretical CS, the degree of a boolean function would mean the degree of its polynomial (Fourier) representation. But it seems unlikely that the term is used in this sense here; also I do not see a nice way to count these. $\endgroup$
    – Srivatsan
    Jul 24, 2011 at 23:14
  • $\begingroup$ Ah, that would be yet another meaning for degree, and I think we are all agreed that the question is only sensible when the intended meaning of this term has been made clear. $\endgroup$
    – JDH
    Jul 24, 2011 at 23:53
  • $\begingroup$ @Srivatsan could you please elaborate a bit further on the polynomial Fourier representation of a Boolean function? $\endgroup$
    – McSinyx
    Dec 31, 2019 at 7:47

You must log in to answer this question.

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