1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about truth tables.

  1. Mar 21, 2012 #1
    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 [itex] 2^n [/itex] n is the number of variables.
    Does this work for infinite truth tables?
     
  2. jcsd
  3. Mar 22, 2012 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    It looks like you have something equivalent to all numbers between 0 and 1 in binary.
     
  4. Mar 22, 2012 #3
    are you saying that the rows in the truth table are uncountable?
    That seems weird.
     
  5. Mar 23, 2012 #4

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Weird or not - it happens to be true.
     
  6. Mar 23, 2012 #5
    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.
     
  7. Mar 23, 2012 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Why does it seem that way?
     
  8. Mar 23, 2012 #7
    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 [itex] 2^n [/itex] hold for infinite tables.
     
  9. Mar 23, 2012 #8

    chiro

    User Avatar
    Science Advisor

    Think of your truth table as a mapping of [itex]G1 x G2 -> {0,1}[/itex], 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?
     
  10. Mar 24, 2012 #9

    mathman

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  11. Mar 24, 2012 #10
    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.
     
  12. Mar 25, 2012 #11

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Sorry - you lost me. could you illustrate what you are trying to describe?
     
  13. Mar 25, 2012 #12
    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.
     
  14. Mar 25, 2012 #13

    chiro

    User Avatar
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question about truth tables.
  1. Truth tabes (Replies: 4)

  2. Vacuous truths (Replies: 43)

Loading...