The number of Boolean functions possible with n binary variables is equal to

Boolean Functions (Expressions):

It is useful to know how many different Boolean functions can be constructed on a set of Boolean variables.

When there are no variables: There are two expressions

False = 0 and True = 1

For one variable p: Four functions can be constructed.

Recall, a function maps each input value of a variable to one and only one output value.

1. The False(p) function maps each value of p to 0 (False).
2. The identity(p) function maps each value of p to the identical value.
3. The flip(p) function maps False to True and True to False.
4. The True(p) function maps each value of p to 1 (True).

So, For one variable p, 4 = \(2^{2^{1}}\) functions can be constructed.

This information can be collected into a table

For two variables: p and q, 16 Boolean functions can be constructed.

Boolean Functions of n Variables:

∴ There are \(2^{2^{n}}\)different Boolean functions on n Boolean variables