Subsection 3.2.1 Introduction
So far we have used truth tables to tell us when a logical expression is true. It turns out that we can also use them to prove theorems.
Recall that what we need to do in order to prove a theorem is to show that a statement of the following form is a tautology:
\((premise_1 \wedge premise_2 \wedge premise_3 \wedge \cdots \wedge premise_n ) \rightarrow conclusion \)
This means that we must show that the conclusion is true for all possible assignments of truth values to its variables. Put another way, it’s true in all possible worlds.
So we need to show that every cell of the final column of its truth table contains the value T . To do this, we simply build the truth table just as we’ve been doing.
Let’s return to the Who Drives Me example. We’ve given these names to the basic statements:
J: John must drive me to the store .
M: Mary must drive me to the store .
L: John will be late for work.
In terms of these names our premises are:
[1] J \(\vee \) M John or Mary must drive me to the store.
[2] J \(\rightarrow \) L If John drives me to the store, he will be late for work.
[3] \(\neg \) L John cannot be late for work.
And the conclusion we’d like to draw is:
[4] M Mary must drive me to the store.
So we must prove that this statement is a tautology:
[5] ((J \(\vee\) M) \(\wedge\) (J \(\rightarrow\) L) (L)) M
To do that, we build its truth table (we’ve omitted a couple of intermediate columns so that the table fits on a page):
Every cell of the final column contains the value T. So [5] is a tautology. We have proved that, if the premises are true, then Mary must drive me to the store.
Recall that, when we presented the truth table definition of implies , we argued that our definition was a reasonable one:
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
You can now see even more clearly why that is so:
It’s the tool we need for proving a theorem: As we just saw, all we have to do to prove that whenever some collection of premises P is true then some conclusion C must also be true is to use the truth table for implies to show that P → C is a tautology.
-
It’s the tool we need when it comes time to exploit a theorem to make a new claim: If we know that p → q cannot be false (because we have proved it to be a tautology), then we can look at the truth table for implies and see that we cannot be in the situation described in line 2. In other words:
If p is true then q must be.
If p is false then we don’t know anything about q . It could be true or false. In other words, this theorem isn’t relevant.
Exercises Exercises
1.
Let’s return to a famous Catch-22 situation. We’ll give names to the following statements:
C : I’m crazy.
M : I’ve requested a mental health discharge from the Army.
E : I’m eligible for a mental health discharge from the Army.
In Joseph Heller’s book, the Army has two rules about this. We can encode them as premises as follows:
[1] E → C ∧ M The only way to be eligible is to be crazy and request the discharge.
[2] M → ¬ C I’m not crazy if I’ve requested the discharge.
Prove that it’s not possible that I’m eligible for a discharge. (And, since we could do this same proof for anyone else, there can never be any of these discharges.)
To do this, we must show that the conjunction of the premises implies the conclusion (¬ E ). In other words, we must show that the following is a tautology:
(( E → C ∧ M ) ∧ ( M → ¬ C )) → ¬ E
Use a truth table to do this. We’ll use our Truth Table app. Click here to begin:
When you’ve finished the table, enter here values for the \(((E \rightarrow C \wedge M) \wedge (M \rightarrow \neg C))\) column.
truthtables.org