Truth tables

This chapter introduces a way of evaluating sentences and arguments of SL. The truth table method is a purely mechanical procedure that requires no intuition or special insight. Given the (albeit imprecise) translatability between SL and natural languages, this also amounts to a formal way of evaluating some natural language arguments.

3.1 Truth-functional connectives

Any non-atomic sentence of SL is composed of atomic sentences with sentential connectives. In Ch. 2, we offered characteristic truth tables for each connective. Although we didn't emphasize it at the time, the fact that it is possible to give truth tables like this is very significant. It means that our connectives are truth-functional. That is to say, the only thing that matters for determining the truth value of a given sentence of SL is the truth values of its constituent parts. To determine the truth value of a sentence ¬Φ, the only thing that matters is the truth value of Φ. You don't have to know what Φ means, or where it came from, or what evidence there is for it and what that evidence might depend on. The truth-value of ¬Φ is a function of the truth-value of Φ. And so likewise for the other connectives.

We are using the same notion of a function that you have probably encountered in mathematics. A function from one set to another associates each member of the first set with exactly one member of the second set. Once the first element is fixed, the function uniquely selects an element of the second set. Any given numerical value of x will unambiguously determine the value of x², for instance, so f(x) = x² is a function. In the same way, any given truth value of Φ will unambiguously determine the value of ¬Φ, which is why negation, too, is a function.

This is a very interesting feature of SL. It is not inevitable. The syntax of English, for example, permits one to make a new, more complex English declarative sentence by prefixing the phrase 'Donald Trump cares whether' in front of any declarative English sentence. In this respect this phrase is syntactically similar to '¬' in SL. But it is impossible to give a truth-functional characterization of the 'Donald Trump cares whether' operator in English. If you want to know whether Donald Trump cares whether the Canadian dollar is getting stronger, it's not enough to know whether the Canadian dollar is getting stronger. If it is, he might or might not care; if it isn't, he might or might not care. 'Donald Trump cares whether' is not truth-functional. But all the connectives of SL are.

For this reason, we can construct truth tables to determine the logical features of SL sentences.

3.2 Complete truth tables

The truth-value of sentences which contain only one connective are given by the characteristic truth table for that connective. Truth tables list out all the possible combinations of truth values for the atomic wffs at play; each row corresponds to a possible way of assigning truth values to atomic sentences. ({P = 1, Q = 1} is one way truth values could be assigned; {P = 1, Q = 0} is another.)

In the previous chapter, we wrote the characteristic truth tables with '1' for true and '0' for false. It is important to note, however, that this is not about truth in any deep or cosmic sense. Philosophical investigation into the nature of truth is a worthy project in its own right, but the truth functions in SL are just rules which transform input values into output values. (This is part of the reason why, in this book, we usually write '1' and '0' instead of 'T' and 'F'.) Even though we interpret '1' as meaning 'true' and '0' as meaning 'false', computers can be programmed to fill out truth tables in a purely mechanical way. In a machine, '1' might mean that a register is switched on and '0' that the register is switched off. Mathematically, they are just the two possible values that a sentence of SL can have. The truth tables for the connectives of SL, written in terms of 1s and 0s, are given in table 3.1.

The characteristic truth table for conjunction, for example, gives the truth conditions for any sentence of the form (Φ&Ψ). Even if the conjuncts are long, complicated sentences, the conjunction is true if and only if both Φ and Ψ are true.

Let's construct a truth table for a more complicated sentence. Consider the sentence (H&I) ⊃ H. We consider all the possible combinations of true and false for H and I, which gives us four rows. We then copy the truth-values for the sentence letters and write them underneath the letters in the sentence.

So far all we've done is duplicate the first two columns. We've written the 'H' column twice --- once under each 'H', and the 'I' column once, under the 'I'.

Now consider the subsentence H&I. This is a conjunction with H as Φ and with I as Ψ. H and I are both true on the first row. Since a conjunction is true when both conjuncts are true, we write a 1 underneath the conjunction symbol. In the other three rows, at least one of the conjuncts is false, so the conjunction (H&I) is false. So we write 0s under the conjunction symbol on those rows:

The entire sentence is a conditional Φ ⊃ Ψ with (H&I) as Φ and with H as Ψ. On the second row, for example, (H&I) is false and H is true. Since a conditional is true when the antecedent is false, we write a 1 in the second row underneath the conditional symbol. We continue for the other three rows and get this:

The column of 1s underneath the conditional tells us that the sentence (H&I) ⊃ H is true regardless of the truth-values of H and I. They can be true or false in any combination, and the compound sentence still comes out true. It is crucial that we have considered all of the possible combinations. If we only had a two-line truth table, we could not be sure that the sentence was not false for some other combination of truth-values.

In this example, we have not repeated all of the entries in every successive table, so that it's easier for you to see which parts are new. When actually writing truth tables on paper, however, it is impractical to erase whole columns or rewrite the whole table for every step. Although it is more crowded, the truth table can be written in this way:

Most of the columns underneath the sentence are only there for bookkeeping purposes. When you become more adept with truth tables, you will probably no longer need to copy over the columns for each of the sentence letters. In any case, the truth-value of the sentence on each row is just the column underneath the main logical operator of the sentence; in this case, the column underneath the conditional. We've marked it in bold.

A complete truth table has a row for all the possible combinations of 1 and 0 for all of the sentence letters. The size of the complete truth table depends on the number of different sentence letters in the table. A sentence that contains only one sentence letter requires only two rows, as in the characteristic truth table for negation. This is true even if the same letter is repeated many times, as in the sentence [(C≡C)⊃C]&¬(C⊃C). The complete truth table requires only two lines because there are only two possibilities: C can be true or it can be false. A single sentence letter can never be marked both 1 and 0 on the same row. The truth table for this sentence looks like this:

Looking at the column underneath the main connective, we see that the sentence is false on both rows of the table; i.e., it is false regardless of whether C is true or false. So it is a contradiction. (See §1.6.1.)

A sentence that contains two sentence letters requires four lines for a complete truth table, as in the other characteristic truth tables and the table for (H&I) ⊃ I above.

A sentence that contains three sentence letters requires eight lines. For example:

From this table, we know that the sentence M&(N∨P) might be true or false, depending on the truth-values of M, N, and P.

A complete truth table for a sentence that contains four different sentence letters requires 16 lines. In general, if a complete truth table has n different sentence letters, then it must have 2ⁿ rows.

In order to fill in the columns of a complete truth table, begin with the right-most sentence letter and alternate 1s and 0s. In the next column to the left, write two 1s, write two 0s, and repeat. For the third sentence letter, write four 1s followed by four 0s. This yields an eight line truth table like the one above. For a 16 line truth table, the next column of sentence letters should have eight 1s followed by eight 0s. For a 32 line table, the next column would have 16 1s followed by 16 0s. And so on.

3.3 Using truth tables

3.3.1 Tautologies, contradictions, and contingent sentences

Recall from §1.6.1 that an English sentence is a tautology if it must be true as a matter of logic. With a complete truth table, we consider all of the ways that the world might be. If the sentence is true on every line of a complete truth table, then it is true as a matter of logic, regardless of what the world is like.

So a sentence is a tautology if the column under its main connective is 1 on every row of a complete truth table.

Conversely, a sentence is a contradiction if the column under its main connective is 0 on every row of a complete truth table.

A sentence is contingent if it is neither a tautology nor a contradiction; i.e. if it is 1 on at least one row and 0 on at least one row.

From the truth tables in the previous section, we know that (H&I) ⊃ H is a tautology, that [(C≡C)⊃C]&¬(C⊃C) is a contradiction, and that M&(N∨P) is contingent.

3.3.2 Logical equivalence

Two sentences are logically equivalent in English if they have the same truth value as a matter of logic. Once again, truth tables allow us to define an analogous concept for SL: Two sentences are logically equivalent if they have the same truth-value on every row of a complete truth table.

Consider the sentences ¬(A∨B) and ¬A&¬B. Are they logically equivalent? To find out, we construct a truth table.

Look at the columns for the main connectives; negation for the first sentence, conjunction for the second. On the first three rows, both are 0. On the final row, both are 1. Since they match on every row, the two sentences are logically equivalent.

3.3.3 Consistency

A set of sentences in English is consistent if it is logically possible for them all to be true at once. A set of sentences is logically consistent if there is at least one line of a complete truth table on which all of the sentences are true. It is inconsistent otherwise.

Look again at the truth table above. We can see that ¬(A∨B) and ¬A&¬B are consistent, because there is at least one row, namely the last one, where both are assigned true.

Are A, B, and ¬A&¬B logically consistent? No. If they were, there would have to be a row where all three sentences are assigned true. But examination of the truth table reveals that there is no such row.

3.3.4 Validity

An argument in English is valid if it is logically impossible for the premises to be true and for the conclusion to be false at the same time. An argument is valid in SL if there is no row of a complete truth table on which the premises are all 1 and the conclusion is 0; an argument is invalid in SL if there is such a row.

Consider this argument:

¬L ⊃ (J∨L)
¬L
J

Is it valid? To find out, we construct a truth table.

To determine whether the argument is valid, check to see whether there are any rows on which both premises are assigned 1, but where the conclusion is assigned 0. There are no such rows. The only row on which both the premises are 1 is the second row, and on that row the conclusion is also 1. So the argument form is valid in SL.

Here is another example. Is this argument valid?

P ⊃ Q
¬P
¬Q

To evaluate it, construct a truth table and see whether there is a row that assigns 1 to the premises and 0 to the conclusion:

There is. On the third row, the premises are true and the conclusion is false. So the argument is invalid.

3.4 Partial truth tables

In order to show that a sentence is a tautology, we need to show that it is assigned 1 on every row. So we need a complete truth table. To show that a sentence is not a tautology, however, we only need one line: a line on which the sentence is 0. Therefore, in order to show that something is not a tautology, it is enough to provide a one-line partial truth table --- regardless of how many sentence letters the sentence might have in it.

Consider, for example, the sentence (U&T) ⊃ (S&W). We want to show that it is not a tautology by providing a partial truth table. We fill in 0 for the entire sentence. The main connective of the sentence is a conditional. In order for the conditional to be false, the antecedent must be true (1) and the consequent must be false (0). So we fill these in on the table:

In order for the (U&T) to be true, both U and T must be true. So we put a 1 under those letters:

Remember that each instance of a given sentence letter must be assigned the same truth value in a given row of a truth table. You can't assign 1 to one instance of U and 0 to another instance of U in the same row. So here we put a 1 under each instance of U and T.

Now we just need to make (S&W) false. To do this, we need to make at least one of S and W false. We can make both S and W false if we want. All that matters is that the whole sentence turns out false on this line. Making an arbitrary decision, we finish the table in this way:

Showing that something is a tautology requires a complete truth table. Showing that something is not a tautology requires only a one-line partial truth table, where the sentence is false on that one line. That's what we've just done. In the same way, to show that something is a contradiction, you must show that it is false on every row; to show that it is not a contradiction, you need only find one row where it is true.

A sentence is contingent if it is neither a tautology nor a contradiction. So showing that a sentence is contingent requires a two-line partial truth table: The sentence must be true on one line and false on the other. For example, we can show that the sentence above is contingent with this truth table (it would have been fine to just show the two relevant rows):

Note that there are many combinations of truth values that would have made the sentence true, so had multiple choices for the second line.

Showing that a sentence is not contingent requires providing a complete truth table, because it requires showing that the sentence is a tautology or that it is a contradiction. If you do not know whether a particular sentence is contingent, then you do not know whether you will need a complete or partial truth table. You can always start working on a complete truth table. If you complete rows that show the sentence is contingent, then you can stop. If not, then complete the truth table. Even though two carefully selected rows will show that a contingent sentence is contingent, there is nothing wrong with filling in more rows.

Showing that two sentences are logically equivalent requires providing a complete truth table. Showing that two sentences are not logically equivalent requires only a one-line partial truth table: Make the table so that one sentence is true and the other false.

Showing that a set of sentences is consistent requires providing one row of a truth table on which all of the sentences are true. The rest of the table is irrelevant, so a one-line partial truth table will do. Showing that a set of sentences is inconsistent, on the other hand, requires a complete truth table: You must show that on every row of the table at least one of the sentences is false.

Showing that an argument is valid requires a complete truth table. Showing that an argument is invalid only requires providing a one-line truth table: If you can produce a line on which the premises are all true and the conclusion is false, then the argument is invalid.

Table 3.2 summarizes when a complete truth table is required and when a partial truth table will do. If you are trying to remember whether you need a complete truth table or not, the general rule is, if you're looking to establish a claim about every interpretation, you need a complete table.

3.5 Evaluating English arguments via SL

Recall from §1.4 that a natural language argument is valid if and only if it is impossible for the premises to be true while the conclusion is false. This notion is rather closely related to validity in SL, which obtains if and only if there is no assignment of truth values to atomic sentences on which the premises are assigned '1' and the conclusion is assigned '0'. This is of course by design. Validity of an SL argument form guarantees that an English argument that is well-translated into that form is valid. Consider for example this English argument:

1. Either the butler is the murderer or the gardener isn't who he says he is.
2. The gardener is who he says he is.
The butler is the murderer.

This argument is valid. There's no way for the conclusion to be false if both premises are true. Let's translate this argument into SL, and evaluate the resulting formal argument for validity with a truth table. We begin with a symbolization key:

B: The butler is the murderer.
G: The gardener is who he says he is.

With this key, the argument, rendered in SL, looks like this:

1. (B∨¬G)
2. G
B

We can evaluate this formal argument for validity using a truth table. We'll set up a table with two atomic sentences, and check to see whether there is a row that assigns '1' to both premises and assigns '0' to the conclusion. The completed truth table looks like this:

If the argument form were invalid, there'd be a line on which the first two bold values are '1' but the third is '0'. There is no such line, so the argument form is valid. This helps explain why the English version of the argument is also valid: it is an argument that has a valid form in SL.

There are at least two advantages to evaluating natural language argument for validity by translating it into SL. For one thing, using truth tables to evaluate arguments is a formal method that does not require any particular rational insight or intuition. It is often relatively easy to tell whether the informal definition of validity is met --- most of us have a good sense of what is and isn't possible. But it is an advantage to have an operationalized set of rules that a simple computer could apply. A second advantage, alluded to in Chapter 2, is that talking about valid SL forms provides a nice way to explain what various valid English arguments have in common with one another. The validity of the argument form

1. (B∨¬G)
2. G
B

helps explain why the butler argument is valid, but the explanation does not depend on any of the specifics of what the individual letters stand for. It would be a perfectly good explanation for why any argument of this form would have to be valid. For example, consider this argument:

1. Either Barney is a purple dinosaur or I don't have a really weird-looking cat.
2. I do have a really weird-looking cat.
Barney is a purple dinosaur.

That argument can be translated into the same SL argument just evaluated, using this symbolization key:

B: Barney is a purple dinosaur.
G: I have a really weird-looking cat.

Since it too has a valid form in SL, it too must be a valid argument. Any argument with this form will be a valid argument.

If you have an argument form that is valid in SL, then any English argument that is properly translatable into that argument form will be valid.

Note that this is even true for arguments that have a more complex internal structure, like this strange argument:

1. Either Canada is a democracy if and only if Poland is neither part of the European Union nor majority Catholic, or my dog is not not lazy.
2. My dog is not lazy.
Canada is a democracy if and only if Poland is neither part of the European Union nor majority Catholic.

One could translate this argument in to a relatively complex argument in SL. (If you did, the first premise would probably be a disjunction with a complex biconditional as one disjunct, and a negated negation as the other; the conclusion would probably be a biconditional with an atom on one side, and a negated disjunction on the other.) In this instance, however, that extra structure isn't needed to explain the validity of the argument. For this argument too has the same valid form as the previous ones, as can be seen via this symbolization key:

B: Canada is a democracy if and only if Poland is neither part of the European Union nor majority Catholic.
G: My dog is not lazy.

For many purposes, this would be a poor choice of symbolization keys. It ignores the internal structure of two central sentences. But if, as here, that structure is irrelevant, you can save yourself some work by engaging at a higher level of abstraction.

Note also that it's an implication of what we've just illustrated that there's not just one SL argument form that is the argument form for a given argument in English. One can formalize arguments in various ways. If an argument has a valid argument form in SL, that's a guarantee that the argument is valid. But it is important not to invert this relationship --- it does not follow from the fact that an argument has an invalid form, that the argument is invalid. One reason this is so is that it is possible for arguments to have valid forms and invalid forms.

3.6 Common student mistakes

Here are a couple of issues that often come up when I teach this material to students.

3.6.1 Validity is not relative to particular valuations of atoms

A sentence in SL is true on some interpretations, and false on others. (For current purposes, you can think of an interpretation as something that fixes a row of the truth table; it determines the truth values of the atomic sentences in use.) For example, P ≡ Q is true on an interpretation where {P = 1, Q = 1}, and false when {P = 1, Q = 0}. So truth in SL is relative to an interpretation.

But validity, unlike truth, is a claim about all interpretations.

Let's use a truth table to evaluate whether P ∨ Q, ¬P∴ P ≡ Q is a valid argument form. To do this, we can draw the complete truth table for those three wffs:

We then check to see whether there is any row where the disjunction and the negation are true and the biconditional is false. Row three, {P = 0, Q = 1}, is such a row, so the argument is invalid.

Here is a common mistake. Students sometimes draw the truth table accurately, and correctly note that line three is inconsistent with the argument's validity, but misdescribe the situation, saying something like this: 'The argument is invalid when P = 0, Q = 1.' This is a mistake because the argument isn't only invalid in that row --- the argument is invalid, period. That interpretation explains why the argument is invalid, but validity and invalidity are claims about all interpretations. So we shouldn't say the argument is invalid 'when' P = 0, Q = 1; it's invalid always, because of the interpretation where P = 0, Q = 1.

This sounds like a small and fussy point about speaking precisely about logic. It is. But careful language here can help lead to careful thought. It is important, to thinking clearly about validity, to remember that validity, unlike truth, is a feature that SL argument forms have or lack intrinsically. Validty is not something an argument form has in some interpretations and lacks in others.

The same goes for tautologies, contradictions, and contingent sentences. A sentence isn't a tautology on some interpretations and not on others; it either simply is, or it simply is not, a tautology.

3.6.2 Valid arguments with invalid forms

Here is a question students sometimes get wrong: Provide (in English) a valid argument of the form P∴ P&Q, or explain why it is impossible to do so. Students often think this is impossible, because P  P&Q is an invalid argument form.

Well, P∴ P&Q certainly is an invalid argument form. The premise is true, and the conclusion false, on an interpretation where P = 1, Q = 0. But that doesn't mean there can be no valid argument with this form.

A valid argument form is a form that guarantees that any argument of that form is valid. Since this form is invalid, it is going to be possible to find invalid arguments of that form. For example, we could interpret P and Q thus:

P: Captain Hook is angry.
Q: Captain Hook has at least two daughters.

And of course the English argument, Captain Hook is angry, therefore Captain Hook is angry and he has at least two daughters is obviously invalid. But that doesn't mean there couldn't be other arguments of this form that are valid. The form doesn't guarantee that they'll be valid, but they may be valid nevertheless. Consider this symbolization key:

P: Captain Hook has three daughters.
Q: Captain Hook has at least two daughters.

The resulting argument is valid: Captain Hook has three daughters. Therefore, Captain Hook has three daughters and he has at least two daughters. It is impossible for the premise to be true without the conclusion also being true, so it satisfies the definition of validity given in Chapter 1. This argument is valid, even though it has an SL argument form that is invalid. We will be particularly interested in arguments whose validity can be explained by their forms, but the definition of validity in English is more general.

Practice Exercises

If you want additional practice, you can construct truth tables for any of the sentences and arguments in the exercises for the previous chapter.

Part A Provide the truth table for the complex formula: ((P⊃((P⊃Q)≡(P&¬R)))∨R) Indicate whether the formula is tautological, contradictory, or contingent. If it is contingent, provide a model that satisfies it and one that falsifies it.

Part B Provide the complete truth table for this SL sentence: ((P∨Q)&(¬P∨¬Q)) ≡ R Indicate whether it is tautological, contradictory, or contingent. If it is contingent, provide an assignment of truth values that satisfies it and one that falsifies it.

Part C Determine whether each sentence is a tautology, a contradiction, or a contingent sentence. Justify your answer with a complete or partial truth table where appropriate.

Part D Determine whether each pair of sentences is logically equivalent. Justify your answer with a complete or partial truth table where appropriate.

Part E Determine whether each set of sentences is consistent or inconsistent. Justify your answer with a complete or partial truth table where appropriate.

Part F

Use a complete truth table to evaluate this argument form for validity:

1. (P⊃Q) ∨ (Q⊃P)
2. P
P ≡ Q

Indicate whether it valid or invalid. If it is invalid, provide an interpretation that satisfies the premises and falsifies the conclusion.

Part G Determine whether each argument form is valid or invalid. Justify your answer with a complete or partial truth table where appropriate. (In each case, the last column is the conclusion of the argument and the preceding ones are the premises.)

Part H Answer each of the questions below and justify your answer.

Suppose that Φ and Ψ are logically equivalent. What can you say about Φ ≡ Ψ?

Suppose that (Φ&Ψ) ⊃ Ω is contingent. What can you say about the argument:

1. Φ
2. Ψ
Ω

Suppose that {Φ, Ψ, Ω} is inconsistent. What can you say about (Φ&Ψ&Ω)?

Suppose that Φ is a contradiction. What can you say about the argument

1. Φ
2. Ψ
Ω

Suppose that Ω is a tautology. What can you say about the argument

1. Φ
2. Ψ
Ω

Suppose that Φ and Ψ are logically equivalent. What can you say about (Φ∨Ψ)?

Suppose that Φ and Ψ are not logically equivalent. What can you say about (Φ∨Ψ)?

Part I We could leave the biconditional (≡) out of the language. If we did that, we could still write 'A ≡ B' so as to make sentences easier to read, but that would be shorthand for (A⊃B)&(B⊃A). The resulting language would be formally equivalent to SL, since A ≡ B and (A⊃B)&(B⊃A) are logically equivalent in SL. If we valued formal simplicity over expressive richness, we could replace more of the connectives with notational conventions and still have a language equivalent to SL.

There are a number of equivalent languages with only two connectives. It would be enough to have only negation and the material conditional. Show this by writing sentences that are logically equivalent to each of the following using only parentheses, sentence letters, negation (¬), and the material conditional (⊃).

1. A ∨ B
2. A&B
3. A ≡ B

We could have a language that is equivalent to SL with only negation and disjunction as connectives. Show this: Using only parentheses, sentence letters, negation (¬), and disjunction (∨), write sentences that are logically equivalent to each of the following.

4. A&B
5. A ⊃ B
6. A ≡ B

The Sheffer stroke is a logical connective with the following characteristic truthtable:

7. Write a sentence using the connectives of SL that is logically equivalent to (A|B).

Every sentence written using a connective of SL can be rewritten as a logically equivalent sentence using one or more Sheffer strokes. Using no connectives other than the Sheffer stroke, write sentences that are equivalent to each of the following.

8. ¬A
9. (A&B)
10. (A∨B)
11. (A⊃B)
12. (A≡B)

Part J

The connective '∨' indicates inclusive disjunction; it is true if either or both of the disjuncts is true. One might be interested in exclusive disjunction, which requires that exactly one of the disjuncts be true. Let us temporarily extend SL to include a connective for exclusive disjunction, allowing sentences of the form (Φ⊕Ψ), where Φ and Ψ are sentences, meaning that exactly one of Φ and Ψ are true.

Provide the truth table for (Φ⊕Ψ).

⊕ is definable in terms of ∨,&, and ¬. This means that there is a formula using only these latter connectives that is equivalent to --- true in all the same models as --- (P⊕Q). Provide such a formula.

Using truth tables, prove that the formula provided in the last question is equivalent to (P⊕Q).