# Question about truth tables.

1. Mar 21, 2012

### cragar

If I had a truth table with a countably infinite number of variables. How many rows would my truth table have. For finite truth tables it is $2^n$ n is the number of variables.
Does this work for infinite truth tables?

2. Mar 22, 2012

### mathman

It looks like you have something equivalent to all numbers between 0 and 1 in binary.

3. Mar 22, 2012

### cragar

are you saying that the rows in the truth table are uncountable?
That seems weird.

4. Mar 23, 2012

### mathman

Weird or not - it happens to be true.

5. Mar 23, 2012

### cragar

that means that we can't construct the rows of the truth table. We wouldn't be able to write them down. But how could I have a countable number of variables and and uncountable number of rows. It seems that all the possible number of combinations in my truth table should be countable.

6. Mar 23, 2012

### HallsofIvy

Staff Emeritus
Why does it seem that way?

7. Mar 23, 2012

### cragar

Would I be able to write down the rows of the truth table? Or at least start to.
Even though I have a countable infinite number of variables. It seems I should be able to compare all these variables by constructing them one line at a time. and why
should $2^n$ hold for infinite tables.

8. Mar 23, 2012

### chiro

Think of your truth table as a mapping of $G1 x G2 -> {0,1}$, where G is some input corresponding to a binary vector.

Now lets say that G1 and G2 refer to the same set. If G1 has infinitely many combinations, why should G2 not either?

9. Mar 24, 2012

### mathman

The proof is essentially the same as the Cantor proof that the reals are uncountable. Short version: Assume that all the rows are in a (countable) list. Then (following Cantor) I can create a row that is not on the list - contradicting the assumption you have all the rows.

The first entry is the opposite of the first entry of the first row, the second entry is the opposite of the second entry of the second row, ..., the nth entry is the opposite of the nth entry of the nth row, etc. You now have a row which differs from all the rows on list, so the list in incomplete, contradicting the assumption it was complete.

10. Mar 24, 2012

### cragar

ok, how do we know that combination needed to be on the table.
Is it because we need an infinite amount of combinations.
What If I constructed my table in such a way that if it had an infinite amount of variables , but I picked the connectives in such a way that we didn't necessarily need all the possible combinations. for example for an if then statement if the first value is false
then it will be true no matter what the second one is. Maybe im way off. What do you think.

11. Mar 25, 2012

### mathman

Sorry - you lost me. could you illustrate what you are trying to describe?

12. Mar 25, 2012

### cragar

Lets say we use a bunch of if-then statements on our truth table.
so if the first truth value is false then it doesn't matter what the second value is,
So maybe cantors diagonal argument doesn't necessarily apply to this table, because we could generate all the possible truth combinations with out having every line be a unique line.

13. Mar 25, 2012

### chiro

The thing is though that if you are doing some computation on two inputs and the number of inputs is infinite, then under the Turing model you won't be able to do the computation in a finite amount of time.

For an infinite input space, you will need infinite numbers of bits for every element. For a general truth table, it is not computationally possible under a model like a Turing machine to even calculate the value from an algorithm or look up the entry from some memory location if it is in a table of some sort.