🧮 Boolean Function Counting

Written and maintained by the PhDino author · Last reviewed 21 September 2026 · Checked against 2 independent reference calculations · how PhDino checks its numbers

How fast the space of possible logic functions explodes as the number of input variables grows.

A truth table for n boolean variables has exactly 2ⁿ rows, since each variable independently doubles the number of possible input combinations. That part is intuitive. What's much less intuitive is how many distinct boolean functions exist for those n variables: since each row of the truth table can independently be assigned a 0 or 1 output, the number of distinct possible functions is 2 raised to the power of the number of rows — 2^(2ⁿ).

That double exponential is genuinely explosive: 2 variables already allow 16 possible functions, 3 variables allow 256, and 4 variables allow 65,536 — despite the truth table itself only growing linearly in row count (4, 8, 16 rows respectively). This is the deeper reason simplification tools like Karnaugh maps and the Quine-McCluskey algorithm matter: the space of things a circuit could compute grows far faster than the table describing any one of them.

Key formula

Truth table rows = 2ⁿ
Possible distinct functions = 2^(2ⁿ)

Notes & limitations

• This counts every mathematically possible function of n inputs, including ones with no simpler circuit realization and ones that are constant, trivial, or practically useless — it's a statement about the size of the function space, not about how many of those functions are actually useful.
• This is why minimization matters practically: among the enormous space of possible functions, the one a real circuit needs to implement can very often be built from far fewer gates than a naive one-gate-per-truth-table-row implementation would require.