Wittgenstein introduced them in the Tractatus Logico-Philosophicus (1921); in proposition 4.31 to be exact.
4.26    If all true elementary propositions are given, the result is a complete description of the world. The world is completely described by giving all elementary propositions, and adding which of them are true and which false.

4.27    For n states of affairs, there are Kn = Σ(from ν = 0 to n) (n above ν) possibilities of existence and non-existence.

Of these states of affairs any combination can exist and the remainder not exist.

4.28    There correspond to these combinations the same number of possibilities of truth -- and falsity -- for n elementary propositions.

4.3    Truth-possibilities of elementary propositions mean possibilities of existence and non-existence of states of affairs.

4.31    We can represent truth-possibilities by schemata of the following kind ('T' means 'true', 'F' means 'false'; the rows of 'T's' and 'F's' under the row of elementary propositions symbolize their truth-possibilities in a way that can easily be understood):

    p  q  r
    -  -  -
    T  T  T       p  q
    F  T  T       -  -       p
    T  F  T       T  T       -
    T  T  F ,     F  T ,     T
    F  F  T       T  F       F
    F  T  F       F  F
    T  F  F
    F  F  F

And thereafter with a number of remarks in a similar vein. Clearly he is working this out as a new idea. In his later work (foremost in Philosophical Investigations) he repudiated this atomistic picture of the world being composed of all the things that were true about it, but his legacy of the truth table remains useful.