Section 2: 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.

Here are the truth tables for the connectives of SL, written in terms of 1s and 0s.

\(\mathcal{A}\)	¬\(\mathcal{A}\)
1 0	0 1

\(\mathcal{A}\)	\(\mathcal{B}\)	\(\mathcal{A}\) & \(\mathcal{B}\)	\(\mathcal{A}\)∨\(\mathcal{B}\)	\(\mathcal{A}\)→\(\mathcal{B}\)	\(\mathcal{A}\)↔\(\mathcal{B}\)
1 1 0 0	1 0 1 0	1 0 0 0	1 1 1 0	1 0 1 1	1 0 0 1

Table 3.1: The characteristic truth tables for the connectives of SL.

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

\(H\)	\(I\)	(\(H\) & \(I\))→\(H\)
1 1 0 0	1 0 1 0	1 1 1 1 0 1 0 1 0 0 0 0

Now consider the subsentence \(H\)&\(I\). This is a conjunction \(\mathcal{A}\)&\(\mathcal{B}\) with \(H\) as \(\mathcal{A}\) and with \(I\) as \(\mathcal{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:

\(H\)	\(I\)	(\(H\) & \(I\))→\(H\)
1 1 0 0	1 0 1 0	\(\mathcal{A}\) & \(\mathcal{B}\) 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 0

The entire sentence is a conditional \(\mathcal{A}\)→\(\mathcal{B}\) with (\(H\)&\(I\)) as \(\mathcal{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:

\(H\)	\(I\)	(\(H\) & \(I\))→\(H\)
1 1 0 0	1 0 1 0	\(\mathcal{A}\) → \(\mathcal{B}\) 1 1 1 0 1 1 0 1 0 0 1 0

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

\(H\)	\(I\)	(\(H\) & \(I\))→\(H\)
1 1 0 0	1 0 1 0	\(\mathcal{A}\) → \(\mathcal{B}\) 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0

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:

\(C\)	[(\(C\)↔\(C\) )→\(C\) ] & ¬(\(C\)→\(C\) )
1 0	1 1 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0

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:

\(M\)	\(N\)	\(P\)	\(M\) & (\(N\) ∨\(P\))
1 1 1 1 0 0 0 0	1 1 0 0 1 1 0 0	1 0 1 0 1 0 1 0	1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0

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 \(\mathcal{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 rightmost 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.