Boolean Function Counts: Formulas, Worked Examples and Exam Traps

The usual confusion starts with one remembered formula: 2^n. That is the number of input rows, but learners often reuse it as the number of Boolean functions. The count follows from a truth table, with separate cases for complete three-variable, balanced, partially specified, symmetric and self-dual functions. The GATE CS Exam Preparation collection places this idea within Digital Electronics.

1. Count functions by output columns, not expressions

An n-variable Boolean function is a mapping f: {0,1}^n -> {0,1}. Its domain contains 2^n distinct input vectors, so its complete truth table has 2^n rows. Every row has an independently chosen output, either 0 or 1.

Therefore, the number of output columns is

2 x 2 x ... x 2, with one factor for each of the 2^n rows.

So the master count is 2^(2^n) distinct Boolean functions.

This is a count of behaviours, not written expressions. For example, x + xy, x, and x(x + y) simplify to the same mapping. Infinitely many expressions can be created by inserting identities, but they do not create new truth-table columns. Boolean Algebra Basics: From Truth Table to Gate Circuit follows one function through canonical forms, simplification and a circuit. Counting instead treats each output column as one function, then asks how a restriction reduces the set.

Check the smallest cases. For n=1, the two input rows can have output vectors 00, 01, 10, or 11, giving 2^2=4 functions. For n=2, four input rows allow 2^4=16 output columns. The inner exponent counts rows. The outer base counts the two choices in each output cell.

2. Worked example: all Boolean functions of three variables

For variables (x,y,z), use the row order 000, 001, 010, 011, 100, 101, 110, 111. There are 2^3=8 input combinations. Every row receives either 0 or 1, independently of the others, so

2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 2^8 = 256.

Take the output vector (1,0,1,1,0,0,1,0) in that row order. Its ones occur at rows 0, 2, 3, and 6, so it represents f = Sigma m(0,2,3,6). This eight-bit column is one of the 256 functions. Changing even one bit creates a different mapping. Its complement, (0,1,0,0,1,1,0,1), is another function.

The full chain is:

n=3 inputs -> 2^3=8 input combinations -> 2 choices per output cell -> 2^(2^3)=2^8=256 functions.

Minterms, expressions and possible circuits are not being counted as separate functions.

3. Constants, exactly k ones and balanced functions

Among the 256 three-variable functions, exactly two are constant: 00000000 and 11111111. The nonconstant count is therefore 256-2=254. In general, for n >= 1, there are 2^(2^n)-2 nonconstant functions.

If a function must contain exactly k ones, choose which k of the 2^n rows get output 1. That gives C(2^n,k). For n=3 and exactly three ones,

C(8,3) = (8 x 7 x 6)/(3 x 2 x 1) = 56.

No extra factor is needed. Once those three one-valued rows are selected, the other five outputs must be zero.

A balanced function has equal numbers of zero and one outputs. With three variables, choose four of the eight rows to receive 1:

C(8,4) = (8 x 7 x 6 x 5)/(4 x 3 x 2 x 1) = 70.

Our vector 10110010 has four ones and four zeros, so it is one of these 70 balanced functions. Generally, the count is C(2^n,2^(n-1)) for n >= 1.

4. Fixed rows and essential variables change what is free

Suppose a three-variable table fixes f(000)=1 and f(111)=0. The remaining six rows are free, so there are 2^6=64 completions. If the final table must contain exactly four ones, one is already fixed. Choose the other three one-valued rows from the six free positions, giving C(6,3)=20 completions.

Now consider functions of x and y that must depend essentially on both variables. There are 16 functions in total. Four ignore x and behave only as functions of y; another four ignore y. The two constant functions are in both groups. Inclusion-exclusion says that 4+4-2=6 functions ignore at least one variable, leaving 16-6=10 that depend on both.

The reusable method is simple: mark the independently selectable output positions first, then apply the restriction. Do not use 2^(2^n) unchanged when rows are fixed, the number of ones is prescribed, or every named variable must affect the answer.

5. Symmetric and self-dual functions use different pairings

A symmetric Boolean function depends only on Hamming weight, the number of input bits equal to 1. For three variables, possible weights are 0,1,2,3. Choosing one output for each weight gives 2^4=16 symmetric functions. Majority is one example: its weight-output vector is (0,0,1,1), corresponding to Sigma m(3,5,6,7).

A self-dual function satisfies f(x)=not f(not x) for n >= 1, where not x complements every input bit. For three variables, the input pairs are (000,111), (001,110), (010,101), and (011,100). Choose the output for one member of a pair, and the other output is forced to be its complement. Four free choices give 2^4=16 self-dual functions. In general, the count is 2^(2^(n-1)).

Both counts happen to be 16 for n=3, but the reasons differ. Symmetry groups inputs by Hamming weight. Self-duality pairs each input with its complement. A function required to satisfy both conditions needs a separate intersection argument.

6. Traps that produce the wrong count

• Answering 2^n. This counts input assignments. Write rows=2^n, then give two output choices to every row.

• Confusing 2^(2n) with 2^(2^n). At n=3, the wrong form is 2^6=64; the correct exponent is 2^3=8, giving 2^8=256.

• Counting expressions or circuits. Equivalent forms are counted repeatedly. Compare complete output columns instead.

• Subtracting constants from an exactly-k count. Use C(2^n,k) directly. The cases k=0 and k=2^n already represent the constants.

• Assuming every variable is essential or every blank is free. Circle the genuinely free output choices and account for every dependency first.

A 15-second check is enough: find the domain size, count free output positions, read the restriction, choose multiplication, combinations or inclusion-exclusion, and test the logic on n=1 or n=2.

7. How assessments reshape the same idea

Practice questions commonly ask for an unrestricted count, exactly k one outputs, completions of a partial truth table, or a count under essential, symmetric or self-dual behaviour. These are variations of one question: which output choices remain independent?

Try this timed drill before reading the answers:

1. All functions for n=2.

2. Nonconstant functions for n=2.

3. Three-variable functions with exactly two ones.

4. Three-variable functions after three distinct output rows are fixed.

The answers are 2^4=16, 16-2=14, C(8,2)=28, and 2^(8-3)=2^5=32. For each answer, say why a power, a subtraction, or a combination is appropriate. For adjacent expression practice, use Boolean Algebra and K-Map MCQs. For broader timed practice, the GATE Test Series is the relevant route.

8. The short version and next step

Remember four lines:

• 2^n is the number of input rows.

• 2^(2^n) is the number of unrestricted output columns.

• C(2^n,k) fixes exactly k one outputs.

• Other restrictions reduce or couple the free output choices.

Redraw the eight rows for (x,y,z) and reproduce 10110010. Then calculate 256 total functions, 254 nonconstant functions, 56 functions with exactly three ones, and 70 balanced functions without looking back. Explain why 56 and 70 come from combinations rather than unrestricted powers of two.

If you want a structured subject-wise preparation path after this retrieval exercise, use GATE Guidance by Sanchit Sir.