Truth Tables

In this chapter, we’ll discuss the method of Truth Tables, which gives us a “negative test” for validity. Derivations show us when an argument form is good—when the particular instances of that form are guaranteed to be formally valid. Truth tables show us when an argument form is not good: when the particular instances of that argument form are not guaranteed to be formally valid.

Our ability to use truth tables depends on two things: Compositionality, and the Principle of Truth Functionality.

Compositionality

Compositionality is the following feature of languages: the meaning of a whole expression, like a sentence, is determined by the meanings of its parts.

Compositionality is often thought to explain how it is even possible for human beings (finite creatures that we are) are capable of understanding a potentially infinite collection of sentences. We do not need to know the meaning of every sentence in advance. We just need to know the meanings of words that sentences comprise, and the rules for computing the meaning of a whole from the meanings of the parts.

The principle of truth functionality is a certain rule that we have enforced in the construction of our artificial language.

The Principle of Truth Functionality

The only contribution that the parts of our sentences shall make to the meanings of the whole is their truth value.

Compositionality tells us that whether a sentence is true or not (this is the only aspect of its meaning that we will be concerned with) depends only on what its parts mean. The Principle of Truth Functionality ensures that the only relevant aspect of the meaning of the parts of a sentence in our language is whether they are true or false. Between these two principles, we know that whether a sentence of our language is true or not depends only on whether its parts are true or false. But there are only a finite number of possible combinations of truth and falsity that the basic parts of the sentence might have. This is how we manage to find, among a potentially infinite collection of cases where an argument might be applied, the cases in which it is possible for the premises to be true and the conclusion false.

And, Or, Not

Let us see how these ideas play out in some particular cases. First, we will observe how sentences whose main connective is get their truth values. These sentences—which look like (ϕ ∧ ψ) are true only when both halves (the ϕ and the ψ) are true. This makes sense—the symbol means “and”, and what does it mean to say “ϕ and ψ”, other than to say that ϕ is true and ψ is also true?

Ex. 1

  1. If P is true, and Q is true, then (P ∧ Q) must be true.
  2. If P is true, and Q is false, then (P ∧ Q) must be false.
  3. If P is false and Q is true, then (P ∧ Q) must be false.
  4. If both P and Q are false, then (P ∧ Q) must be false.
  5. If P is true and Q is true, and R is also true, then (P ∧ Q) must be true, so ((P ∧ Q)∧R) must also be true.

What about when the main connective is ? These sentences—which look like (ϕ ∧ ψ) are true only when one of the halves (the ϕ and the ψ) are true. This makes sense—the symbol means “or”, and what does it mean to say “ϕ or ψ”, other than to say that at least one of ϕ or ψ is true? This explanation is a little quick, so I include a footnote here to address one possible concern. The way that we are thinking about “or” above, an or-statement can be true if both of its parts are true. This is how things sometimes work in English. For example, when I say “there’s going to be beer or sangria at the party”, this is naturally read as meaning that there might be one or the other, or there might be both.
But, sometimes in natural language we use “ϕ or ψ” to mean not just that at least one of ϕ or ψ is true, but to mean that exactly one of ϕ or ψ is true. When I say “Each of you will be assigned to either the blue team or the red team”, that is naturally understood as meaning that each person will be assigned to one team, but nobody will be assigned to both.
The first reading of “or”, on which “ϕ or ψ” can be true when both sides are true is called the “inclusive” or. The second reading, on which “ϕ or ψ” is true when exactly one of ϕ or ψ is true is called the “exclusive” or. This difference is important in contexts where we need to know exactly what we mean (for example, logic, law, and computer programming). But it might have slipped by without notice, if we had not thought carefully about how the meaning of an or-sentence depends on the meanings of its parts.

Ex. 2

  1. If P is true, and Q is true, then (P ∨ Q) must be true.
  2. If P is true, and Q is false, then (P ∨ Q) must be true.
  3. If P is false and Q is true, then (P ∨ Q) must be true.
  4. If both P and Q are false, then (P ∧ Q) must be false.
  5. If P is true and Q is true, and R is false, then (P ∧ Q) must be true, so ((P ∧ Q)∨R) must also be true.

What about when the main connective is ¬? These sentences—which look like ¬ϕ are true only when the main part (the ϕ) is false. This makes sense—the symbol ¬ means “it is not the case that”, and what does it mean to say “it is not the case that ϕ”, other than to say that it is not the case that ϕ is true?

  1. If P is false, ¬P must be true.
  2. If P is true, ¬P must be false.
  3. If P is false and Q is true, then ¬P must be true, so P ∧ Q) must be true.
  4. If both P and Q are false, then ¬P is true and ¬Q is also true, so P ∧ ¬Q) must be true.
  5. If P is true and Q is false, and R is false, then (P ∧ Q) must be false, but ¬R must be true, so ((P ∧ Q)∨¬R) must be true.

We can summarize the rules for ∧, ∨ and ¬ as follows:

Truth-Value Rules for , , ¬
  1. if a sentence has as its main connective, it is true when both halves are true. Otherwise it is false.
  2. If a sentence has as its main connective, it is true when at least one half is true. Otherwise, it is false.
  3. If a sentence as ¬ as its main connective, it is true when its main part is true. Otherwise, it is false.

Truth Values, Truth Tables, Tautologies

As the examples of the previous section show, we can use the three simple rules associated with ∧, ∨ and ¬ to find out what truth values the sentences built up using these truth connectives have. Here is a systematic procedure for finding the truth value of a sentence, once you know the truth values of the sentence letters that occur in the sentence.

The Method of Composing Truth-Values
  1. Parse the sentence, writing out the parsing tree associated with the sentence (do this by repeatedly breaking at the main connective, and placing the parts that a sentence was built out of beneath the sentence).
  2. Write the truth values that you know next to the appropriate letters, at the bottom of the tree.
  3. Use the truth value rules associated with the connectives to figure out the truth values of sentences higher up in the tree, writing these down next to the higher sentences as you figure them out.
  4. Repeat step 3 until you know the truth value of the whole sentence.

Ex. 3

Suppose we know that P and Q are true and that R is false, and we wish to know whether (((P ∨ ¬Q)∧(P ∨ ¬R)) ∨ ((P ∧ R)∧(P ∨ ¬R))) is true.

First, we find the main connective, splitting the sentence into:

We repeat this procedure, finding main connectives and subdividing, finally getting:

We’ve now completed step 1. Step 2 tells us to write out appropriate truth values at the bottom of the tree. Since we know that P and Q are true, and R is false (we assumed this at the outset), we write these next to the appropriate sentence letters:

We’re now done with step 2. We now repeat step 3 (applying the rules for ∧, ∨ and ¬ until we are done. Since we now know the truth values of all of the parts of several of the sentences on our tree, we can compute the truth values of those sentences using the rules for ∧, ∨ and ¬. We compute those values and write them in:

Since we now know the truth values of the parts of the sentences in the second row from the top, we can write those in too:

And that means that (((P ∨ ¬Q)∧(P ∨ ¬R)) ∨ ((P ∧ R)∧(P ∨ ¬R))) was built using out of one true and one false sentence. So, the whole sentence is true:

This is interesting, but there is one problem in using this method to determine whether a sentence is true (we will eventually extend the same technique to also test arguments for validity). How do we know what the truth values of the basic components of a sentence are?

The answer is that sometimes, we will not know. But in some of the cases where we don’t know, we can still figure out the truth value of the whole sentence. The trick is this. When we do not know what the truth values of the basic parts of a sentence are, we can still know what the might be. And that is sometimes enough. Because, when we know all of the possible truth values of the sentence letters—all the truth values the sentence letters might have—we can check each possibility. If the sentence is true on every possibility, then the sentence (and indeed, any similar sentence) must be true, no matter which of the ways the truth values actually turn out to be assigned.

If a sentence is true no matter what the truth values of its sentence letters turn out to be, we say that the sentence is a tautology.

Tautology

A sentence in official or unofficial notation is a tautology if it is true no matter what truth values are assigned to its sentence letters.

To find out whether a sentence is a tautology, we just need to list all of the ways that truth values might be assigned to its sentence letters, and then use the method of Example 3 to determine what truth values the sentence have on those assignments. This is not too hard to do, in principle, but it can be a little bit hard to check whether you have listed all of the possible ways that truth values can be assigned to the sentence letters. So, here is a simple method of bookkeeping, called “the method of truth tables”, which is helpful when trying to see whether a sentence is a tautology.

Conditionals

We now are equipped with the method of composing truth values, and the rules for ∧, ∨ and ¬. These tools make it possible for us to tell, of any sentence in our language built out of ∧, ∨ and ¬, what its truth value is (so long as we know the truth values of its parts). And they will soon give us the power to tell, of any argument formulated in our language, whether it is formally valid.

But we are still missing some pieces. In particular, we do not know what the rules for , and are. These two connectives are related; the first means “If, then”, while the second means “if and only if”. Since the makes sentences that say that something will happen on some condition, it is sometimes called a conditional. Since makes sentences saying that one thing will happen if another does, and only if that other does (incorporating two conditions), it is sometimes called a biconditional.

When is a sentence which looks like (ϕ ↔ ψ), built using true? We say that such a sentence is true only when both halves (the ϕ and the ψ) have the same truth value. This has some intuitive appeal. means “if and only if”. If someone says “I will come to the party if, and only if, there is some beer”, then they’ve lied (said something false) if there’s beer and they don’t come to the party. After all, they said they’d come if there’s some beer. They’ve also lied if they come to the party even though there’s no beer. After all, they said they’d come only if there was beer. On the other hand, if there’s no beer and they don’t come, or if there’s beer and they do, they’re behaving as they said they would.

So,

  1. If P is true, and Q is true, then (P ↔ Q) must be true.
  2. If P is true, and Q is false, then (P ↔ Q) must be false.
  3. If P is false and Q is true, then (P ↔ Q) must be false.
  4. If both P and Q are false, then (P ↔ Q) must be true.
  5. If P is true and Q is true, and R is also true, then (P ↔ Q) must be true, so ((P ↔ Q)↔R) must also be true.

What about a sentence which looks like (ϕ → ψ)? Here, some cases are clear. (ϕ → ψ) means “if ϕ then ψ”. If someone says “if there’s beer, I will come to the party”, then they’ve lied (said something false) if there’s beer and they don’t come to the party (after all, they said they’d come if there’s some beer), and they’ve been honest if there’s beer at the party, so they come to the party. Some cases are not terribly clear. Were they saying something true if it turns out that there’s no beer at the party? We have no cause for complaint, at least—we can’t accuse them of lying. So it is plausible to simply stipulate that we will understand (ϕ → ψ) to be true whenever ϕ is false.

There are a number of reasons for this stipulation. One reason is that it is the simplest solution—all other ways of treating conditionals are much more complicated. Moreover, those other accounts of conditionals inevitably build on the type of simple logic we are doing here. So we need to start with this simplification if we are to understand these more complicated accounts. A third reason is that this set of rules for the conditional are the only possible way of introducing into our language without either violating the principle of truth functionality, or making mean the same thing as some other connective that we already have. The last reason for accepting this stipulation is that, by and large, it works. In fact, we are committed to it in various ways by our deductive system Consider, for example, the material conditional rules, which we can derive: P∴ Q → P and ¬Q → Q → P. These show that the conditional is true whenever its antecedent is false or consequent is true. And the NC rule, P ∧ ¬Q∴ ¬(P → Q) tells us that the conditional is false whenever the antecedent is true and the conclusion false.

  1. If P is true, and Q is true, then (P → Q) must be true.
  2. If P is true, and Q is false, then (P → Q) must be false.
  3. If P is false and Q is true, then (P → Q) must be true.
  4. If both P and Q are false, then (P ↔ Q) must be true.
  5. If P is true and Q is true, and R is also true, then (P ↔ Q) must be true, so ((P ↔ Q)↔R) must also be true.

We can summarize the rules for and as follows:

Truth-Value Rules for ,
  1. if a sentence has as its main connective, it is true when the left half is false, or the right half is true. Otherwise it is false.
  2. If a sentence has as its main connective, it is true when the left half and the right half have the same truth value. Otherwise, it is false.

We now have the rules for all of the connectives. Using these rules, together with the method of truth tables, and the method composing truth-values, it is possible to determine of any sentence in our language, whether that sentence is a tautology.

The Method of Truth Tables

We now officially introduce the method of truth tables

The Method of Truth-Tables
  1. Make a “table” by drawing two lines that cross one another—one separating the top row of the table from the rest, one separating the left half of the table from the right.
  2. Find all of the sentence letters of the sentence you are testing. List those letters on the top row, in the left half of the table, and write the sentence that you are testing in the right half of the table.
  3. Determine the number of sentence letters, and compute 2n, where n is the number of sentence letters (that is, multiply 2 by itself once for each sentence letter after the first—if there is one sentence letter, you will get 2 as a result. If there are 2, you will get 4, if there are 3, you will get 8, and so on.) write in that many rows in the lower half of the table.
  4. Underneath the first sentence letter, fill the first half of the rows with the letter T, and the second half with the letter F. Under the second sentence letter, fill the first half of the first half of the rows with the letter T, the second half of the first half with the letter F, the first half of the second half with the letter T, and the second half of the second half with the letter F. Continue this pattern.
  5. Underneath each sentence letter on the right, fill in its truth values, as listed on the left.
  6. Underneath each connective which is connecting a formula or formulas that are either
    1. Sentence letters,
    2. Complex sentences with truth values filled in under their main connectives, use the Truth-Value rules to fill in truth values, on the basis of what is under the complex formulas or sentence letters that that connective are connecting. Repeat this step until every connective has truth values filled in underneath.
  7. If you end up with only Ts underneath the main connective of the sentence you are testing, then you have found a tautology. If you end up with one or more F underneath the sentence, then you have found a non-tautology.

Ex. 4

Here’s an example of how to use the method of truth tables. Suppose we want to know whether (((P → Q)→P)→P) is a tautology.

Step 1: we make a table:

  
  

Step 2: We find the sentence letters in our sentence (they are P and Q) and we list them on the top left. We write the sentence we are testing on the right:

PQ(((PQ)P)P)
  

We have two sentence letters, so step 3 tells us to write in 22 = 4 rows:

PQ(((PQ)P)P)
  
  
  
  

For step 4, underneath the first sentence letter (i.e. P), we fill the first half of the rows (i.e. the first two rows) with the letter T, and the second two rows with F. We then fill in the first half of the first half (i.e. the first row) under the second letter with T, the second half of the first half with with F, the first half of the second half with T, and so on:

PQ(((PQ)P)P)
TT
TF
FT
FF

So far, this hasn’t involved using our knowledge of connectives. But now, we need to start filling in truth values “within the table”, rather than using the method of composing truth values. The first step is to fill in the truth values under all the sentence letters:

PQ(((PQ)P)P)
TTTTTT
TFTFTT
FTFTFF
FFFFFF

Having done this, we now have exactly one connective which combines formulas that we know the truth value of. This one connective is the leftmost . So, we can fill in truth values for that.

PQ(((PQ)P)P)
TTTTTTT
TFTFFTT
FTFTTFF
FFFTFFF

Now, though, we have filled in truth values for both P and for (P → Q), the two things that the second-from-rightmost is connecting. So, we can fill in truth values for that, on the basis of what we have filled in for these (remember, we put what we fill in for (P → Q) under the main connective of this formula):

PQ(((PQ)P)P)
TTTTTTTT
TFTFFTTT
FTFTTFFF
FFFTFFFF

There’s just one connective remaining, the rightmost . This one, we can fill in by looking at what we have put under the main connective of ((P → Q)→P) and of P:

PQ(((PQ)P)P)
TTTTTTTTT
TFTFFTTTT
FTFTTFFTF
FFFTFFFTF

We now know what the truth values underneath the main connective of (((P → Q)→P)→P) are: they are all T. That means, according to step 7, that (((P → Q)→P)→P) is a tautology.

Problem Set 13

Please fill in the following truth tables:

exercise 13.1
13.1 P/\Q
exercise 13.2
13.2 P->Q
exercise 13.3
13.3 P/\-P
exercise 13.4
13.4 P\/-P
exercise 13.5
13.5 P->(Q->P)
exercise 13.6
13.6 P/\Q->P\/Q
exercise 13.7
13.7 ((P->Q)->P)->P
exercise 13.8
13.8 -(P/\Q)<->-P\/-Q

Please also complete the following two derivations of tautologies: The first of these was originally noted and proved by G.W. Leibniz, who called it the Praeclarum Theorema (in English: “splendid theorem”).

exercise 13.9
13.9 :|-: (P->R)/\(Q->S)->(P/\Q->R/\S)
exercise 13.10
13.10 :|-: (P->(Q<->R))<->(P/\Q<->P/\R)

Problem Set 14

Please determine whether the following arguments are valid, either by providing a counterexample, or filling in the associated truth tables.

exercise 14.1
14.1 P/\Q :|-: P\/Q
exercise 14.2
14.2 P\/Q :|-: P/\Q
exercise 14.3
14.3 (P->Q)/\(Q->P) :|-: P<->Q
exercise 14.4
14.4 P->Q, Q->R :|-: P->R
exercise 14.5
14.5 S/\R, -S, -R :|-: Q
exercise 14.6
14.6 (P->(Q<->R)) :|-: (P/\Q<->Q/\R)
exercise 14.7
14.7 P<->Q :|-: -Q<->-P
exercise 14.8
14.8 P->Q, R->Q :|-: P->R

Please also complete the following two derivations:

exercise 14.9
14.9 :|-: ((P->Q)\/R)<->(P->Q\/R)
exercise 14.10
14.10 P<->Q, P<->R :|-: P<->Q\/R