Ludwig Wittgenstein: tautology and truth tables

by Paul Curzon, Queen Mary University of London

Ludwig Wittgenstein is one of the most important philosophers of the 20th century. His interest was in logic and truth, language, meaning and ethics. As an aside he made contributions to logical thinking that are a foundation of computing. He popularised truth tables, a way to evaluate logical expressions, and invented the modern idea of tautology. His life shows that you do not have to set out with your life planned out to ultimately do great things.

Wittgenstein was born in Austria, of three-quarters Jewish descent, and actually went to the same school as Hitler at the same time, as they were the same age to within a week. Had he still been in Austria at the time of World War II he would undoubtedly have been sent to a concentration camp. Hitler presumably would not have thought much of him had he known more about him at school. Not only did he have a Jewish background, he was bisexual: it is thought he fell in love four times, once with a woman and three times with men.

Interested, originally, in flying and so aeronautic engineering he studied how kites fly in the upper atmosphere for his PhD in Manchester: flying the kites in the Peak District. He moved on to the study of propellors and designed a very advanced propellor that included mini jet engines on the propellor blades themselves. Studying propellors led him to an interest in advanced mathematics and then ultimately to the foundations of mathematics – a course about which, years later, he taught at Cambridge University that Alan Turing attended. Turing was teaching a course with the same title but from a completely different point of view at the time. His interest in the foundations of maths led to him thinking about what facts are, how they relate to thoughts, language and logic and what truth really was. However, World War I then broke out. During the war he fought for the Austro-Hungarian army, originally safe behind the lines but at his own request he was sent to the Russian Front. He was ultimately awarded medals for bravery. While on military leave towards the end of the war he completed the philosophical work that made him famous, the Tractatus Logico-Philosophicus. After the war though he went to rural Austria and worked as a monastery gardener and then as a primary school teacher. His sister suggested this was “like using a precision instrument to open crates”, though as he got into trouble for being violent in his punishments of the children the metaphor probably isn’t very good as he doesn’t sound like a great teacher and as a teacher he was more like a very blunt instrument.

In his absence, his fame in academia grew, however, and so eventually he returned to Cambridge, finally gained a PhD and ultimately became a fellow and then a Professor of Philosophy. By the time World War II broke out he was teaching philosophy in Cambridge but felt this was the wrong thing to be doing during a war, so despite now being a world famous philosopher went to work as a porter in Guy’s hospital, London.

His philosophical work was ground breaking mainly because of his arguments about language and meaning with respect to truth. However, a small part of has work has a very concrete relevance to computing. His thinking about truth and logic had led him to introduce the really important idea of a tautology as a redundant statement in logic. The ancient Greeks used the word but in a completely different sense of something made “true” just because it was said more than once, so argued to be true in a rhetorical sense. In computational terms Wittgenstein’s idea of a tautology is a logical statement about propositions that can be simplified to true. Propositions are just basic statements that may or may not be true, such as “The moon is made of cheese”. An example of a tautology is (a OR NOT(a)) where (a) is a variable that stands for a proposition so something that is either true or false. Putting in the concrete propositions “The moon is made of cheese” we get:

“(The moon is made of cheese) OR NOT (The moon is made of cheese)”

or in other words the statement

“The moon is made of cheese OR The moon is NOT made of cheese”

Logically, this is always true, whatever the moon is made of. “The moon is made of cheese” can be either true or false. Either it is made of cheese or not but either way the whole statement is true whatever the truth of the moon as one side or other of the OR is bound to be true. The statement is equivalent to just saying

“TRUE”

In other words, the original statement always simplifies to truth. More than that, whatever proposition you substitute in place of the statement “The moon is made of cheese” it still simplifies to true eg if we use the statement instead “Snoopy fought the Red Baron” then we get

“Snoopy fought the Red Baron OR NOT (Snoopy fought the Red Baron)”

Again, whatever the truth about Snoopy, this is a true statement. It is true whatever statement we substitute for (a) and whether it is true or false: (a OR NOT(a)) is a tautology guaranteed to be true by its logical structure, not by the meaning of the words of the propositions substituted in for a.

As part of this work Wittgenstein used truth tables, and is often claimed to have invented them. He certainly popularised them as a result of his work becoming so famous. However, Charles Sanders Peirce used truth tables first, 30 years earlier. The latter was a philosopher too, know as the “Father of Pragmatism” (so hopefully that means he wouldn’t have minded Wittgenstein getting all the credit!)

A truth table is just a table that includes as rows all the combinations of true and false values of the variables in logical expressions together with an answer for those values. For example a truth table for the operator NOT, so telling us in all situations what (NOT a) means, is:

a		NOT a
TRUE		FALSE
FALSE		TRUE

The first thing that is important about truth tables is that they give very clear and simple meaning (or “semantics”) to logical operators (like AND, OR and NOT) and so of statements asserting facts logically. Computationally, they make precise what the logical operators do, as the above table for NOT does. This of course matters a lot in programs where logical operators control what the program does. It also matters in hardware which is built up from circuits representing the logical operations. They provide the basis for understanding what both programs and hardware do.

The following is the truth table for the logical OR operator: again the last column gives the meaning of the operator so the answer of computing the logical or operation. This time there are two variables (a) and (b) so four rows to cover the combinations.

a	b		a OR b
TRUE	TRUE		TRUE
TRUE	FALSE		TRUE
FALSE	TRUE		TRUE
FALSE	FALSE		FALSE

Truth tables can be used to give more than just meaning to operators, they can be used for doing logical reasoning; to compute new truth tables for more complex logical expressions, including checking if they are tautologies. This is the basis of program verification (mathematically proving a program does the right thing) and similarly hardware verification. Let us look at (a OR (NOT a)). We make a column for (a) and then a second column gives the answer for (NOT a) from the NOT truth table. Adding a third column we then look up in the OR truth table the answers given the values for (a) and (NOT a) on each row. For example, if a is TRUE then NOT a is FALSE. Looking up the row for TRUE/FALSE in the OR table we see the answer is TRUE so that goes in the answer column for (a OR (NOT a)). The full table is then:

a		NOT a		a OR (NOT a)
TRUE		FALSE		TRUE
FALSE		TRUE		TRUE

Truth tables therefore give us an easy way to see if a logical expression is a tautology. If the answer column has TRUE as the answer for every row, as here, then the expression is a tautology. Whatever the truth of the starting fact a, the expression is always true. It has the same truth table as the expression TRUE (a) where TRUE is an operator which gives answer true whatever its operand.

a		TRUE
TRUE		TRUE
FALSE		TRUE

We can do a similar thing for (a AND (NOT a)). We need the truth table for AND to do this.

a	b		a AND b
TRUE	TRUE		TRUE
TRUE	FALSE		FALSE
FALSE	TRUE		FALSE
FALSE	FALSE		FALSE

We fill in the answer column based on the values from the (a) column and the (NOT a) column looking up the answer in the truth table for AND.

a		NOT a		a AND (NOT a)
TRUE		FALSE		FALSE
FALSE		TRUE		FALSE

This shows that it is not a tautology as not all rows have answer TRUE. In fact, we can see from the table that this actually simplifies to FALSE. It can never be true whatever the facts involved as both (a) and (NOT a) are never true about any proposition (a) at the same time.

Here is a slightly more complicated logical expression to consider: ((a AND b) IMPLIES a). Is this a tautology? We need the truth table for IMPLIES to work this out:

a	b		a IMPLIES b
TRUE	TRUE		TRUE
TRUE	FALSE		FALSE
FALSE	TRUE		TRUE
FALSE	FALSE		TRUE

When we look up the values from the (a AND b) column and the (a) column in the IMPLIES truth table, we get the answers for the full expression ((a AND b) IMPLIES a) and find that it is a tautology as the answer is always true:

a	b		a AND b	a		(a AND b) IMPLIES a
TRUE	TRUE		TRUE	TRUE		TRUE
TRUE	FALSE		FALSE	TRUE		TRUE
FALSE	TRUE		FALSE	FALSE		TRUE
FALSE	FALSE		FALSE	FALSE		TRUE

Using the same kind of approach we can use truth tables to check if two expressions are equivalent. If they give the same final column of answers for the same inputs then they are interchangeable. Let’s look at (b OR (NOT a)).

a	b		NOT a		(b OR (NOT a))
TRUE	TRUE		FALSE		TRUE
TRUE	FALSE		FALSE		FALSE
FALSE	TRUE		TRUE		TRUE
FALSE	FALSE		TRUE		TRUE

This gives exactly the same answers in the final column as the truth table for IMPLIES above, so we have just shown that:

(a IMPLIES b) IS EQUIVALENT TO (b OR (NOT a))

We have proved a theorem about logical implication. (a IMPLIES b) has the same meaning as, so is interchangeable with, (b OR (NOT a)). All tautologies are interchangeable of course as they are all equivalent in their answers to TRUE. If we give a truth table for IS EQUIVALENT TO we could even show equivalences like the above are tautologies!

Tautologies, and equivalences, once proved, can also be the basis of further reasoning. Any time we have in a logical expression (a IMPLES b), for example, we can swap it for (b OR (NOT a)) knowing they are equivalent.

Truth tables helped Wittgenstein think about arguments and deduction of facts using rules. In particular, he decided special rules that other philosophers suggested should be used in deduction, were not necessary, as such. Deduction instead works simply from the structure of logic that means logical statements follow from other logical statements. Truth tables gave a clear way to see the equivalences resulting from the logic. Deduction is not about meanings in language but about logic. Truth tables meant you could decide if something was true by looking at equivalences so ultimately tautologies. They showed that some statements were universally true just by inspection of the truth table. For computer scientists they gave a way to define what logical operations mean and then reason about digital circuits and programs they designed, both to help understand, so write them, and get them right.

Wittgenstein started off as an engineer interested in building flying machines, moved to become a mathematician, a soldier, a gardener and a teacher, as well as a hospital porter, but ultimately he is remembered as a great philosopher. Abstract though his philosophy was, along the way he provided computer scientists and electrical engineers useful tools that helped them build thinking machines.

---

More on …

• Lego Computer Science: truth tables
• LGBTQ+ Computer Science Greats

Related Magazines …

• Issue 14 – Alan Turing – The genius who gave us the future

---

EPSRC supports this blog through research grant EP/W033615/1, and through EP/K040251/2 held by Professor Ursula Martin.