Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$ ?

share|improve this question
    
In your book how is the degree of a function defined? Even better give some more info about the context. –  Arjang May 1 '11 at 12:38
    
@Arjang:The degree is not defined,that is the problem. –  Quixotic May 1 '11 at 16:10
    
StackOverflow link. –  Quixotic May 1 '11 at 16:17
    
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. –  please delete me May 4 '11 at 11:20

1 Answer 1

up vote 4 down vote accepted
+50

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.

share|improve this answer
    
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. –  Srivatsan Jul 24 '11 at 23:14
    
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. –  JDH Jul 24 '11 at 23:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.