What is the maximum number of different Boolean functions involving n Boolean variables? A. n^2 B. 2^n C. 2^(2^n) D. 2^(n^2)
GATE 2007 · Discrete Mathematics · Functions · medium
Answer: The maximum number of different Boolean functions of n variables is 2^(2^n), so the answer is Option C.
Count the input rows: Each of the n Boolean variables is independently 0 or 1, so by the product rule there are 2 * 2 * ... * 2 (n times) = 2^n distinct input assignments, i.e. 2^n rows in the truth table.
Count output assignments over all rows: A Boolean function is a function from the 2^n input rows to {0, 1}. By the function-count rule, the number of functions from a set of size m = 2^n to a set of size 2 is 2^m = 2^(2^n). For example n = 2 gives 2^(2^2) = 2^4 = 16.