Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is about truth tables and specifically why there is $2^n$ rows for $n$ inputs in a truth table?

I understand that there's a finite amount of states a variable can be in, here it's 2 - true (1) and false (0). What I don't understand is why is it growing exponentially, is there some intuitive explanation I'm missing?

When I write it out, I understand that in every column is exactly n true(1) states and n false(0) states. So, the $2^n$ certainly works, but I'd like to understand why and how it works.

Can anyone help out? Thanks!

share|improve this question
    
I apologize if I wasn't clear enough, but I meant to say the total sum of all entries is 2n because n true(1) states + n false(0) states = 2n states. –  Curiosity Sep 2 '11 at 14:04
add comment

3 Answers 3

up vote 2 down vote accepted

It's a counting problem. It is based on the following:

Product Rule: If one even can occur in $k$ different ways, and a second event can occur in $m$ different ways, then the number of ways in which both events can occur is $km$.

That is, there are $k$ possible outcomes for the first event, and $m$ for the second, so there are $km$ total possible combinations of outcomes.

The truth table has one row for every possibility. Each variable has two possible outcomes: true or false. If there are $n$ different variables, then you have two possibilities for each, and the number of total combinations is the product of the number of possible outcomes for each. That amounts to a product of $2$ with itself, $n$ times, or $2^n$.

Inductively: one variable has $2$ possible outcomes. Assume that $k$ variables have $2^k$ possible outcomes. How many possible outcomes are there for $k+1$ variables? There are $2^k$ ways in which you can have outcomes in which the last variable is false, and another $2^k$ ways in which you can have outcomes in which the last variable is true. So there is a total of $2^k+2^k = 2(2^k) = 2^{k+1}$ different possible outcomes.

share|improve this answer
add comment

It's because each input can either be in 2 states: on (true) or off (false). Also, in each truth table, there are $n$ inputs. So, we have $2^n$ total rows for this truth table.

However, if we had a different kind of table where each input could be in 3 different states (left, right, center), then the total number of outcomes would be $3^n$.

Hence, you always want to take the number of states possible (2 for truth tables) and raise that to the power of how many inputs you have.

Hope this helps.

share|improve this answer
    
Thanks for the good will to answer, yes, that is correct... But that's just an application of the rule, I'm more interested in why and how the rule works. Mr. Arturo Magidin captured the essence of my question, if you are interested in what I meant. –  Curiosity Sep 2 '11 at 14:06
add comment

While Arturo Magidin is certainly correct in his answer, there is another simple way to illustrate this. That is through an analogy to decimal numbers via binary numbers.

Just like decimal numbers goes from $k$ digits to $k + 1$ digits (e.g. from $999$ to $1000$) when the combinations in the first $k$ digits are exhausted, so does binary (e.g. from $111$ to $1000$ in binary notation), so the construction of binary numbers is quite the same as the decimal numbers that we all feel well at home with.

The difference for binary numbers is in the number of possibilities for each digit. For decimal numbers we have $10$ such possibilities, $0$ through $9$, and thus we have that there is $10^3 = 1000$ possible combinations ($000$ through $999$) of $3$ decimal digits; in binary numbers there is only $0$ and $1$. Just as we intuitively see that with $3$ decimal digits we can create all the combinations up to $10^3 - 1 = 999$ it holds true that for a three digit binary number you can create all the combinations up to $2^3 - 1 = 7$ (or $111$ in binary notation), accounting for a total of $2^3$ combinations including $000$.

Now, for every row in a truth table you can form a binary number by representing it as a string of ones and zeroes. Therefore, according to the above reasoning, if you have $n$ columns in your truth table you must have $2^n$ rows to cover all possible combinations.

share|improve this answer
    
As an upshot of this, if you assign all 0s to all atomic variables in the first row, then all 0s except for the last atomic variable which you make a 1, and so on, you can enumerate the rows of a truth table via binary numbers. –  Doug Spoonwood Sep 2 '11 at 17:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.