Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 3.1.4 Setting Up a Proof

Suppose that we want to show that a set of premises implies a conclusion:

1. \(\displaystyle (premise_1 \wedge premise_2 \wedge premise_3 \wedge \cdots \wedge premise_n ) \rightarrow conclusion \)

In other words, we want to show that there is no circumstance in which the premises are true but the conclusion isn’t. Recall that that’s equivalent to showing that [1] is a tautology .

So, to construct a proof, we do the following:

1. Choose a set of premises whose truth we are willing to accept.

2. Construct the logical statement that is the conjunction of all of them. That gives us something like:

   \((premise_1 \wedge premise_2 \wedge premise_3 \wedge \cdots \wedge premise_n ) \rightarrow conclusion \)

3. Construct the logical statement that asserts that such a conjunction implies the desired conclusion. That gives us something like:

   [1] ( premise 1 ∧ premise 2 ∧ premise 3 ∧ … ∧ premise n ) → conclusion

4. Show that [1] is a tautology. In other words, that, for any assignment of the values T and F to the variables in [1], the truth value of [1] is T . You might, at this point, argue that we don’t actually need the whole column to be T . We really only care about the cases where the premises are themselves true. But how are we going to know which rows those are? It’s not just when the variables are T since (as a trivial example), we could have ¬ p as a premise. So we’ll insist on a proof that the whole column is T . But, in the next section, we’ll look at an alternative to truth tables as a proof technique. One of the wins of that alternative (which we’ll call, “natural deduction”), is that we won’t necessarily have to consider irrelevant combinations of truth values.

Who Drives Me

Let’s give names to some 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.

Using those statements, we can state our premises:

[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.

The conclusion that we’d like to draw is:

[4] M Mary must drive me to the store.

We want to prove that, if all the premises are true, then the conclusion follows. So we need to form the conjunction of our premises and then set up an implication with that conjunction on the left and the conclusion (i.e., M) on the right. That gives us:

[5] ((J \(\vee \) M) \(\wedge\) (J \(\rightarrow\) L) \(\wedge\) ( \(\neg \) L)) \(\rightarrow \) M

And now we must show that [5] is a tautology. If it is, our premises imply our conclusion.

How shall we prove that we’ve got a tautology? In the Wet Sidewalks example, the logical expressions were so simple that we just derived our conclusion informally. But now we have something where it’s less obvious how to reason correctly.

We’re going to describe two different approaches to constructing sound proofs. The first uses a technique we already know: truth tables.

Then we’ll introduce an alternative that we’ll call “natural deduction”. It corresponds more closely to the way we reason in everyday life. But we’ll define it formally so that we’re sure that we can’t erroneously draw conclusions that don’t follow from our premises.