# Where did mathematicians learn how to do truth tables?

I'm trying to find out who invented truth-tables. Here is what I have so far.

Leibniz 'invented' binary arithmetic, or at least is the first one recognized to have codified and explained a base 2 system for arithmetic (there's no doubt that there are vague priors from China; Leibniz himself mentions 'Fohy' and goves a figure that looks like 'I Ching').

Boole, in his Laws of Thought, essentially created boolean algebra (notice that the name of the thing is not the same as the thing).

Peirce and Frege separately introduced symbolism that treated boolean things functionally (that's a roundabout way of saying they were the first to use the notation of functions on booleans, i.e. boolean functions).

Schroeder and later Post also are mentioned in connection with truth tables, but I'm having a hard time substantiating that more than just by repeating that other people collocate those names with 'truth table'.

Wittgenstein, in Tractatus Logicus-Phiosophicus, chapter 5, discusses boolean functions using that terminology and -graphically- expresses these functions in tabular format, calling them 'truth tables' (in German).

Shannon is famous for introducing boolean logic in his master's thesis (1936) for use in design of computers. (his primary references being Couturat, The Logic of Algebra (1905), and Whitehead, Universal Algebra (1898).

It is taken by philosophers that Wittgenstein is the inventor of truth tables: (Stanford Encyclopedia of Philosophy entry on Wittgenstein). But with a background more in cs and math, I find that it doesn't fit with my preconceived notions of intellectual culture - I just wouldn't expect scientific/mathematical types to trace the usage history of something so technical back to someone (Wittgenstein) so humanities-oriented (to be frank, I can't believe that people who built the first digital computers learned truth tables directly or indirectly from TLP).

It is the introduction of a tabular format called 'truth table' that I am looking for the provenance. Since boolean functions were well known before then, it is simply the distinctive visual device of laying out the function in a table with all the possibilities for the arguments next to the value of the function for those arguments. To me this seems like who invented 'FOIL' for teaching how to multiply binomials, in that a name was given to something that people had been doing anyway already (or not even bothering to do).

So, really, where did the use of truth tables really come from, and is there any indication in the history that follows, where the mathematicians and engineers got it from? So maybe Wittgenstein 'popularized' it among the philosophers (I don't have any doubt there), but maybe he was (or maybe wasn't) the source for later use by the engineers.

So, whoever was the first to have invented truth tables (Peirce is definitively the first one there is evidence for), who popularized the use of truth tables in elementary mathematical logic? Wittgenstein certainly popularized it among philosophers, but he (and the Wiener Kreis by extension) doesn't have much influence on mathematicians, so I find it unlikely that mathematicians learned it there.

-
It is hardly appropriate to frame Wittgenstein as "humanities oriented"! –  amWhy Jun 3 '11 at 15:55
@amWhy: any particular reason? in terms of humanities and sciences as broad categories, philosophy is usually located in the humanities. –  Mitch Jun 3 '11 at 16:02
@Mitch: Wittgenstein is sui generis. –  TonyK Jun 3 '11 at 19:39
Wittgenstein worked with Russell on the mathematical foundations of logic. That's pretty "hard" science. –  Raskolnikov Jun 3 '11 at 19:39
Even in his later work, where he broke away from logical positivism, Wittgenstein continued his exploration in Mathematical Foundations (Remarks on the Foundations of Mathematics, etc). The most recent publication of the journal *Philosophia Mathematica" (Series III, Volume 19, no. 1, 2011), the very first article is entitled "Motivating Wittgenstein's Perspective on Mathematical Sentences as Norms" by Simon Friederich, 1-19. –  amWhy Jun 3 '11 at 23:12

Well, Aristotle qualifies as quite "humanities oriented" according to the modern way of classifying subject areas, but up until recently plenty of usage history can get traced back to him. Actually, there still exists some usage history traceable back to him.

That said, you might want to see this page, which indicates that perhaps no real inventor existed. Shosky tried to argue that Russell did so. Anellis, though, if his evidence is correct clearly enough indicates that C. S. Peirce had them before that. So, unless historians have missed something in Frege, Peirce gets the prize here:

... the discovery by Zellweger of Peirce’s manuscript of 1902 does permit us to unequivocally declare with certitude that the earliest, the first recorded, verifiable, cogent, attributable and complete truth-table device in modern logic attaches to Peirce, rather than to Wittgenstein’s 1912 jottings and Eliot’s notes on Russell’s 1914 Harvard lectures

One might also ask here, "who first used numbers for truth-values in the context of truth tables?" I'm not so sure here, but I would think Łukasiewicz did that first, though when he wrote a truth table he wrote them horizontally instead of vertically. ${}$

-
nice links (how did you find them? google didn't help me). So those links nicely address the nominal question 'Who was first?'. I am also looking for the pathway of popularization. I think it is undoubted that Wittgenstein popularized it (whether he invented it or not) among philosophy. But How did it become popular among the engineers? What was the pathway from WIttgenstein (or Post or Peirce) to those later? (I added to the end of my question to reflect this). –  Mitch Jun 3 '11 at 17:33
@Mitch Wittgenstein certainly could well have publicized it's use. He was part of what is known as the "Vienna Circle"...worked closely with Russell, Carnap, and others. Most of his work was in mathematics and logic...It is well known in philosophy/logic, that Wittgenstein conceived of truthtables while working as a teacher of mathematics and logic, and later in his work and correspondences with colleagues, who may then have also adopted its use. –  amWhy Jun 3 '11 at 21:57
Excellent links...they go directly to the 'inventor' question. –  Mitch Jun 4 '11 at 21:18

In addition to the Stanford encyclopedia of Philosophy's attribution to Wittgenstein, Wikipedia's discussion of Wittgenstein's masterpiece Tractatus Logico-Philosophicus also credits Wittgenstein as the inventor of truth tables.

"Wittgenstein is to be credited with the invention of truth tables (4.31) and truth conditions (4.431) which now constitute the standard semantic analysis of first-order sentential logic.[7] The philosophical significance of such a method for Wittgenstein was that it alleviated a confusion, namely the idea that logical inferences are justified by rules. If an argument form is valid, the conjunction of the premises will be logically equivalent to the conclusion and this can be clearly seen in a truth table; it is displayed. The concept of tautology is thus central to Wittgenstein's Tractarian account of logical consequence, which is strictly deductive.

5.13 When the truth of one proposition follows from the truth of others, we can see this from the structure of the propositions.

5.131 If the truth of one proposition follows from the truth of others, this finds expression in relations in which the forms of the propositions stand to one another: nor is it necessary for us to set up these relations between them, by combining them with one another in a single proposition; on the contrary, the relations are internal, and their existence is an immediate result of the existence of the propositions.

5.132 If p follows from q, I can make an inference from q to p, deduce p from q. The nature of the inference can be gathered only from the two propositions. They themselves are the only possible justification of the inference. "Laws of inference", which are supposed to justify inferences, as in the works of Frege and Russell, have no sense, and would be superfluous."

The book (Tractatus) itself is worth the read!

Update: In The Development of Logic (1962), Kneale and Kneale argue that Boole, Frege, Peirce, Jevons, and Venn all contributed to the essentials popularized by Post and Wittgenstein in 1920 (420 and 531).

In making their argument, Kneale and Kneale cite Peirce's paper "On the Algebra of Logic: A Contribution to the Philosophy of Notations" (American Journal of Mathematics 7 [1885], 180-202):

[T]o find whether a formula is necessarily true substitute f and v for the letters and see whether it can be supposed false by any such assignment of values (CP 3.387).

-
My question is getting at the problem with claims you present in your answer that Wittgenstein 'invented' truth-tables, because there is evidence that others had done the same thing before him and that he was only reproducing such things without attribution in TLP (read his introduction where he himself expressly disavows that anything is particularly original in TLP). –  Mitch Jun 4 '11 at 20:46

If you do a little research, Peirce WAS a scientist. Wittgenstein's work was primarily in the philosophy of mathematics and in the philosophy of language after having studied mechanical engineering and Russell and Frege were logician/mathematician's. They had large followings from academics in all departments. They were the originators, the popularizer's and the teachers, not the other way around.

-
Interesting. 1) it is unclear who you are saying did what (who is 'they'?). Is it Russell/Frege? Truth Tables are not done in BR or GF sources, but they are in Wittgenstein, therefore my question. 2) Can you cite any references which support this? I'm curious about the train of provenance. –  Mitch Nov 30 '12 at 18:30

@ Doug Spoonwood: I am unable to date exactly the first use of the truth-tables among (professional) mathematicians, although Charles S. Peirce and Gottlob Frege could make up good approximations (implicit refs. to a famous paper published by Peirce in 1885 and to Frege's "Begriffsschrift" 1879). In particular, Peirce was aware [cca 1900-1902] of the truth-functional behaviour of ALL [two-valued] propositional connectives (including NAND and NOR, usually attributed to Henry M. Sheffer 1913), although he did not publish details, during his lifetime: his findings remained in MSS. On this, the SEP-reference given previously is rather misleading: Ludwig Wittgenstein comes later into the picture (some time during the early twenties or slightly before).

We know, however, for sure that truth-tables were popular already about 21 centuries before Frege and Peirce, among philosophers, more precisely they were found by Chrysippus of Sol[o]i, circa 279-206 BC, the founder of Stoic logic. Even Chrysippus was based on previous findings due to a 5th century BC philosopher, Euclides of Megara, a former pupil of Socrates, and the founder of the Megarian school (or, more likely, of one of his "Megarian" followers). For details, see e.g. the SEP-entry on the "Dialectical school", due to Susanne Bobzien, her SEP-entry on "Ancient logic", and, possibly, the Wikipedia entries on the Megarian school and the like.

As an aside, on should note that, unlike Aristotle and other members of Plato's Academy, Chrysippus and his followers were not particularly fond of mathematics (in the sense of the time).

I will hopefully publish, one of these days, a longer note on the (most plausible) "mathematical" method of construction behind the so-called "Stoic logic" (the "logic of Chrysippus"), including the truth-table stuff (as they could have figured it out, 22 centuries ago) [follow up academia.edu for would-be pre-prints].

@ Mitch, as of today, 20150323 [the answer is too long to fit the comment space] :

> [ Mitch: ] Are you saying there is evidence that some Greek philosophers had the concept of truth functions (functions whose inputs and outputs are something like true and false) and graphical representation of truth tables (a tabular representation)? I don't doubt the first, but I do the latter. Also, the question I have is about the intellectual provenance of the truth-table display in modern mathematics, not the multiple possibly non-influencing reinventions across the world. <

The first half of your question can be answered in the affirmative: Chrysippus and some later Stoics “had the concept of truth functions”, for all practical purposes, so to speak. In his / their terms, of course: they knew how to manipulate truth-functions in order to explain “semantically” complex propositions (the Stoic axiomata) in terms of simples, i.e. atomic propositions. (You don’t expect a second century BC philosopher to be conversant with our modern — set theoretical — concept, not even with the “old-fashioned” pre-Cantorian way of thinking of functions in traditional mathematics — functions as rules, say. Besides, as I said already, the Stoics were less interested in the mathematics of their times.) So, as regards the “intellectual provenance” (of the concept), the honors should go to Chrysippus, no doubt.

However, the second half of the question (concerning the actual representation of the truth-value assignments) cannot be answered properly, mainly because we have insufficient (textual or other kind of historical) evidence at hand, in order to say something definite about. Even the young Russell was a bit confused much later, around the turn of the xix-th century, about the concept of a “propositional function”, and Wittgenstein was not significantly more brilliant in this mater either…

Now, putting things in modern terms, it is likely the Stoics used something equivalent to our truth-tables (an ad hoc concrete representation, after all) only in order to justify semantically, so to speak, their proof-theoretic ruminations. Although nice to play with — a piece of kindergaten mathematics, after all —, the truth-functional explanation of the logical connectives was not central to their logical doctrines: the Stoics used to think about the binary connectives (connector = syndesmos in Greek) in terms of “polar oppositions” (or conflict = “maché”, in Greek; more or less: contradictions).

Examples: the pair of complex propositions reading (A AND B, A NAND B) in our jargon— both attested, btw, in the remnant Stoic fragments — makes up a “polar pair” (of opposites), and similarly for the “polar pairs” including IF (the material conditional) and its converse, reading approximatively SINCE. Actually the polar opposites of IF [IF A THEN B] and SINCE [A SINCE B] resp., are also attested in surviving Stoic fragments: the former would read “A mallon he B” [“A more than B”], in Chrysippus’ Greek — semantically = A AND (NOT B) —, while the polar opposite of SINCE [A SINCE B = IF B THEN A] would read “A etton he B” [“A less than B”], semantically = (NOT A) AND B. (The truth-functional interpretation of “mallon…” / “etton…” has been also confirmed, recently, by Prof. Bobzien, a major expert in Stoics doctrines, btw.) Lastly, the polar pair (A NOR B, A OR B) is also historically attested in late Stoic texts. So, we have “expressive completeness”, in fact (the biconditional IFF and the exclusive disjunction, XOR, can be explained in terms of the above. This can be also found in Stoic texts!) Whence, we know what is *(C) — the polar opposite of C — for any C. Moreover, “double negation” is granted for each form of (complex) C.

To anticipate the longer (technical) note promised earlier: Once the polar trick is well understood, it is relatively clear how to construct inconsistent sequences of propositions (elenchoi, or refutations in Greek) of the form A_1, …, A_n ||- Falsum, in the spirit of the Stoics, such that a valid entailment (syllogismos), A_1, …, A_n ||- C, can be accounted for in terms of … ||- Falsum by:

A_1, …, A_n ||- C iff A_1, …, A_n, *(C) ||- Falsum,

where Falsum is an arbitrary false proposition and *(C) is the polar opposite of C.

On this plan — granted the fact that we can analyse systematically complex *(C)’s into their “polar” components —, it is relatively easy to obtain something very similar to a Gentzen “natural deduction” system resp. a resolution / tableaux-like system (à la Hintikka, Beth, Smullyan and so on) for classical (i.e. Chrysippean) logic!

Well, I won’t go so far to claim that Chrysippus proved the completeness of his logic ( = classical logic ), relative to a would-be account of the classical connectives in terms of truth-tables, 22 centuries ago, but he was pretty close to it, anyway!

-
Are you saying there is evidence that some Greek philosophers had the concept of truth functions (functions whose inputs and outputs are something like true and false)_and_ graphical representation of truth tables (a tabular representation)? I don't doubt the first, but I do the latter. Also, the question I have is about the intellectual provenance of the truth-table display in modern mathematics, not the multiple possibly non-influencing reinventions across the world. –  Mitch Mar 23 at 12:41

The popularization question I find hard to answer sufficiently. What culture are we talking about? English people didn't necessarily read American textbooks, and Americans didn't read German textbooks did they? At least, not usually, I would believe. That said, I will say this. A famous textbook is Lukasiewicz's "Elements of Mathematical Logic" Elementy logiki matematycznej He has 3 logical matrices in it for verifying the independence of axioms, and a 4th logical matrix to indicate how truth values might work in a 3-valued logic at variance with the standpoint of classical propositional logic he adopted in the rest of the book. In my opinion, the textbook is particularly excellent in that I think it has strong advantages for students both new to the study of classical logic and those experienced in it.

-
Yes, the specific strand of culture is difficult to specify, because there are language/nation separations (in addition to the faculty differentiation), but academic borrowing, too. Also, the 20th century has seen a lot of changes in communication, which complicates the matter. If forced, I'd have to limit it to English speaking culture (where things might be likely to have been borrowed from German or French, and doubtfully from Russian or Polish (but that would be very interesting!)) –  Mitch Jun 19 '13 at 15:51

My deleted comment was a very precise rebutall of the author's remark:

"It is taken by philosophers that Wittgenstein is the inventor of truth tables: (Stanford Encyclopedia of Philosophy entry on Wittgenstein). But with a background more in cs and math, I find that it doesn't fit with my preconceived notions of intellectual culture - I just wouldn't expect scientific/mathematical types to trace the usage history of something so technical back to someone (Wittgenstein) so humanities-oriented (to be frank, I can't believe that people who built the first digital computers learned truth tables directly or indirectly from TLP)."

My comment historically supported/proved the possibility of W. being the inventor of the truth tables and historically proved that he has inderictly contributed to the invention of the digital computer (via Turing).

-
Can you give the details of your comment? –  Mitch Feb 9 at 1:55
sorry, someone called jeremy rickard or some other blog manager keeps deleting my responses to you (twice already) for no apperent reason. he/she doesn't allow me to elucidate the connection wittgenstein-turing -- not sure why. if you investigate that, you should be able to find out how truth tables and theoretical computer science historically met one another. –  lost in cyberspace Feb 9 at 15:34