# 5 Truth Tables

This chapter introduces a way of evaluating sentences and arguments of SL. Although it can be laborious, the truth table method is a purely mechanical procedure that requires no intuition or special insight.

# I. Truth-functional connectives

Any non-atomic sentence of SL is composed of atomic sentences with sentential connectives. The truth-value of the compound sentence depends only on the truth-value of the atomic sentences that comprise it. In order to know the truth-value of (D ↔ E), for instance, you only need to know the truth-value of D and the truth-value of E. Connectives that work in this way are called TRUTH-FUNCTIONAL.

In this chapter, we will make use of the fact that all of the logical operators in SL are truth-functional— it makes it possible to construct truth tables to determine the logical features of sentences. You should realize, however, that this is not possible for all languages. In English, it is possible to form a new sentence from any simpler sentence X by saying ‘It is possible that X .’ The truth-value of this new sentence does not depend directly on the truth-value of X . Even if X is false, perhaps in some sense X could have been true— then the new sentence would be true. Some formal languages, called modal logics, have an operator for possibility. In a modal logic, we could translate ‘It is possible that X ’ as ◊X . However, the ability to translate sentences like these come at a cost: The ◊ operator is not truth-functional, and so modal logics are not amenable to truth tables.

# II. Complete truth tables

The truth-value of sentences which contain only one connective are given by the characteristic truth table for that connective. In the previous chapter, we wrote the characteristic truth tables with ‘T’ for true and ‘F’ for false. It is important to note, however, that this is not about truth in any deep or cosmic sense. Poets and philosophers can argue at length about the nature and significance truth, but the truth functions in SL are just rules which transform input values into output values. To underscore this, in this chapter we will 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 5.1.

The characteristic truth table for conjunction, for example, gives the truth conditions for any sentence of the form (A & B). Even if the conjuncts A and B are long, complicated sentences, the conjunction is true if and only if both A and B are true. 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.

Now consider the subsentence H & I. This is a conjunction A & B with H as A and with I as B. 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. We continue for the other three rows and get this:

The entire sentence is a conditional A → B with (H & I) as A and with H as B. 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)   →  I 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. 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.

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.

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

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. Five letters, 32 lines. Six letters, 64 lines. And so on. To be perfectly general: If a complete truth table has n different sentence letters, then it must have 2n 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.

# III. Using truth tables

## Tautologies, contradictions, and contingent sentences

Recall 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 IN SL if the column under its main connective is 1 on every row of a complete truth table.

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

A sentence is CONTINGENT IN SL 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.

## Logical equivalence

Two sentences are logically equivalent in English if they have the same truth value as a matter logic. Once again, truth tables allow us to define an analogous concept for SL: Two sentences are LOGICALLY EQUIVALENT IN SL 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.

## 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 IN SL if there  is at least one line of a complete truth table on which all of the sentences are true. It is INCONSISTENT otherwise.

## 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:

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

Yes, the argument is valid. The only row on which both the premises are 1 is the second row, and on that row the conclusion is also 1.

# IV. Partial truth tables

In order to show that a sentence is a tautology, we need to show that it is 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.

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 contradiction requires a complete truth table. Showing that something is not a contradiction requires only a one-line partial truth table, where the sentence is true on that one line.

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:

Note that there are many combinations of truth values that would have made the sentence true, so there are many ways we could have written 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 5.2 summarizes when a complete truth table is required and when a partial truth table will do.

V. 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 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 B Determine whether each pair of sentences is logically equivalent. Justify your answer with a complete or partial truth table where appropriate.

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

Part D Determine whether each argument is valid or invalid. Justify your answer with a complete or partial truth table where appropriate.

Part F 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 (→).

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.

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 only the Sheffer stroke, write sentences that are equivalent to each of the following.