How many rows are there in a truth table having n variables?

Concept: When independent choices are combined, the multiplication principle says that the total number of outcomes is the product of the numbers of choices. If each of k independent positions can take b states, the number of distinct assignments is bk.

Application — apply the principle to this item:

1. Each truth-table variable has two states, 0 and 1. For n independent variables, multiply 2 by itself n times.

2. The product 2 × 2 × … × 2 (n factors) is 2n, so it gives the number of distinct input assignments.

3. For n = 3, the eight assignments are 000, 001, 010, 011, 100, 101, 110, and 111.

Cross-check: Adding one variable splits every existing assignment into two branches, one with the new variable equal to 0 and one equal to 1. Thus T(n + 1) = 2T(n), with T(0) = 1; repeated doubling gives T(n) = 2n.

Contrast with the other expressions:

• 2n grows linearly and adds 2 when n increases by 1, so it does not follow the doubling recurrence.

• n2 grows quadratically; its ratio between successive values is not always 2.

• log2 n increases slowly and can be non-integer, whereas a row count is a whole number and follows the doubling recurrence.

Result: A truth table with n variables has 2n rows.