Subsection 3.2.6 Theorem upon Theorem
Suppose that we want to prove something even a little bit less trivial than the examples that we’ve done so far. For example, what if we need 10 variables. Then we know that the truth table that we’d have to build would have 2 10 or 1024 rows. Ouch. And things get much worse very quickly. If we needed 50 variables, we’d need 2 50 or 1,125,899,906,842,624 rows. Clearly we need some new techniques.
Here are two ideas. We’re going to see that both of them are powerful and, in fact, we’ll want to combine them:
Prove smaller theorems using smaller collections of variables. Then treat those theorems like premises. (This is okay because we know that they must be true.) Build on them until we prove the final theorem that we care about.
Come up with a new technique that lets us focus on the specific ways in which the premises connect to each other. In most cases, this effectively lets us ignore many (most) of the possible truth value combinations for the variables.
We’ll consider the first of these techniques here. Then, in the next section, we’ll take the second approach and develop a whole new way to construct proofs.
Let’s return to the Who Drives Me example.
We’ll use these propositional variable names for 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.
G: Mary must buy gas. (new)
D: Mary must have money. (new)
Assume these premises:
[1] J M John or Mary must drive me to the store.
[2] J L If John drives me to the store, he will be late for work.
[3] L John cannot be late for work.
[4] M G If Mary must drive me to the store, she must buy gas. (new)
[5] G D If Mary must buy gas, she must have money. (new)
And we’ve already proven:
[6] M Mary must drive me to the store.
Suppose that we want to prove:
[7] D Mary must have money.
We could start from scratch and prove:
[8] \(((J M) (J L) (L) (M G) (G D)) D \)
Notice that there are now five premises [1] – [5] anded together on the left of the top level implies. More importantly, there are now five propositional variables. So, if we build a truth table, from scratch, to prove our claim, we’ll need 32 rows. We can do it, but it’s extremely tedious.
But suppose that, instead of premises [1] – [3], we just use [6], which we’ve already derived from them. Then we can ignore the variables J and L too. We can build a truth table proof that corresponds to the everyday reasoning chain:
Mary must drive me to the store. So she must buy gas. So she must have money.
So now the truth table that we have to build is the one that shows that this claim is a tautology:
[9] \((M \wedge (M G) (G D)) D \)
Since only three variables are involved, we’ll just need to build an eight-row truth table.
Big Idea
Divide and conquer: Break complex proofs into smaller, more manageable pieces.