Maths WorkshopMaths problems with full solutions
Exercise 875Combinatorics › Counting principlesL1Added 3 Nov 2026

Counting Boolean functions

#Boolean functions#counting#product rule

Statement

How many Boolean functions f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} are there?

Hint

There are 2n2^n inputs; each maps to 00 or 11.

Show solutionHide solution

Solution

Inputs. 2n2^n inputs.

Outputs. Each input has 22 choices, so 22n2^{2^n} functions total.

Conclusion. There are 22n2^{2^n} Boolean functions of nn variables.

Example. For n=2n=2, 24=162^4=16 Boolean functions.