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