# Degree of boolean functions

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

-
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

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.