One of the better books that introduces rigorous proof is
*How to Prove It* by Daniel J. Velleman. Here I'm going to
discuss one of the key skills from that book, which is recognizing
what form of proof is appropriate for the kind of thing you want to
prove. This skill is the easy part of doing proofs, but I find that
many students are too slow in this regard. Analogous to a computer
game, one needs to become fast with the button combinations. You shouldn't
have to think consciously about them. The same is true for the basics
of proof. There's a bunch of stuff that should be automatic, at the tips
of your fingers. Once this is accomplished, your mind is then free to
think about the truly hard aspects of more difficult proofs.

For today, what we're going to prove is formulas in propositional logic.
These formulas form a little language, defined by the grammar below.
We'll use lowercase letters to represent propositional variables.
These variables represent statements such as "socrates is mortal".
We'll use uppercase letters as placeholders for formulas.
The kinds of formulas, working left to right, are
variables,
the trivial formulas
and ,
negation (),
logical and (),
logical or (), and
implication ().
We refer to the symbols ,
, etc. as *logical connectives*.
The following is an example of a formula:

### Identify the Main Connective

The first skill needed to recognize what form of proof is needed
to prove a formula, such as the one above, is the ability to
identify the *main connective* of a formula. The main connective
is at the root of the parse tree for the formula.
One can construct a parse tree by starting at the leaves and
working your way towards the root. The leaves are the formulas that don't
have any sub-parts. Constructing a parse tree is equivalent
to adding parentheses to every sub-part of a formula, which
is what we'll do here.
In the above formula, the leaves are:
. Working
from the first and
we have
. (We just used
the grammar rule .)
Working our
way from the last
we have .
For the second occurrence of
we have two choices, we can either go to the left to form
or we can go to the
right and form .
Here we need to use the precedence of the connectives to decide
what to do. The grammar above lists the formulas in the order of
their precedence. So
is higher precedence than ,
so we go to the left and form .
So far, we have parses for
Next, we need to decide whether to combine
and
with the connective ,
or whether to combine
and with the
connective .
Again, we consider the precedences, and here
has higher precedence
than . So we
have the parses:
The last step is to parse the last connective, ,
and complete the tree:
The root of the tree is the last connective that we added to complete
the parse, in this case, the right-most .
So we have found the main connective. It's also important to
know the two sub-trees of the main connective. In this case,

### Prove It!

Now that we've found the main connective, we just do a simple table look-up to figure out what form of proof we should use. Here's the table, which we call the prove-it table.- : assume and prove .
- : prove and also prove .
- : prove one of or .
- : assume and then prove .

Assume .The represents the part of the proof that we haven't finished yet. The table told use to assume , meaning that we should assume the first sub-tree under the implication, which in this case was . We need to prove , the second sub-tree, which in this case is .

Therefore .

Therefore .

At this point we need to prove , so we repeat the above process. The main connective is , so rule 1 of the prove-it table tells us to assume and prove .

Assume .At this point we're a bit stuck, there are no more main connectives to find in the simple formula . But that's ok, we have lots of assumptions to use!

Assume .Therefore .Therefore .

Therefore .

Aside: the fancy name for a prove-it rule is
an *introduction rule*.

### Use It!

Using assumptions and previously-proven facts is a lot like proving formulas: find the main connective and then do a table look-up. The only difference is that we use a different table, shown below, which we call the use-it table.

- From and : have . (You get to choose any formula!)
- From : have .
- From : have .
- From , , and : have .
- From and : have .

We have the assumption , whose main connective is , so we apply the use-it rules 2 and 3.

Assume .Next we apply use-it rule 5 with and to deduce . (The fancy name for use-it rule 5 is

Have .Therefore .

Have .

Assume .Therefore .

Therefore .

*modus ponens*.)

Assume .We now have and , so we can conclude anything at all. (We've reached a contradiction.) We want to prove , so that's what we'll choose. Thus, we don't need any more steps in the proof, so we remove the vertical dots and our proof is complete.

Have .Therefore .

Have .

Assume .Have .Therefore .

Therefore .

Assume .Also, the name for the formula we just proved is

Have .Therefore .

Have .

Assume .Have .Therefore .

Therefore .

*modus tolens*.

In general, the fancy name for a use-it rule is an *elimination rule*.

### More Practice

In the above proof, we didn't get a chance to apply the use-it rule 4 or prove-it rule 3, so let's look at another proof. Let's prove Skipping a couple steps that we already know how to do, we arrive at the following partial proof.

Assume .We have two formulas whose main connective is a logical or, so we need to apply use-it rule 4. This rule is also know as reasoning by cases. We have to choose between using fact or the fact . Sometimes choices like this matter, and you might end up wasting time by making the wrong choice, but that's water under the bridge and you can always backtrack and try the other option. Also, as you gain in skill you'll be able to look a bit into the future, like a good chess player, and figure out which choice is better. Sometimes a choice like this doesn't matter because you're going to end up using both assumptions and it doesn't matter what order to use them in.Have .Therefore .

Have .

Therefore .

Here we're going to use the first fact first, . Now, to apply use-it rule 4 to this assumption, we need two more things that we don't have. We need and . We get to choose what stands for. Once we've applied rule 4, we'll know this is true, so let's choose what we're trying to prove, . Our partial proof expands to the following.

Assume .The second case, in which we assume is easy. We just apply prove-it rule 3. So we've connected those dots.Have .Therefore .

Have .

Assume .Therefore .

Therefore .

Assume .Therefore .

Therefore .

Therefore .

Assume .To deal with the other set of vertical dots, the way forward is not so obvious. But we do have one more fact to use: . To apply use-it rule 4, we'll need to prove a pair of implications. Again, let's choose as the .Have .Therefore .

Have .

Assume .Therefore .

Therefore .

Assume .Therefore .Therefore .

Therefore .

Assume .The first set of dots can be eliminated by use-it rule 1 and the second set of dots can be eliminated by prove it rule 3. So our completed proof is as follows.Have .Therefore .

Have .

Assume .Assume .Therefore .Therefore .

Therefore .

Assume .Therefore .

Therefore .

Therefore .

Assume .Therefore .Therefore .

Therefore .

Assume .Aside: The formula we have just proved is known as theHave .Therefore .

Have .

Assume .Assume .Therefore .Therefore .Therefore .

Assume .Therefore .Therefore .

Therefore .

Assume .Therefore .Therefore .

Therefore .

*resolution rule*.

### But this doesn't look like a real proof!

If you've read one or more proofs in textbooks, you might be thinking at this point that what you've seen above doesn't look like the proofs you've seen in the past. That's because seasoned mathematicians expect that you can do proofs such as the ones above in your head, and don't write down those parts of the proofs. That is, they skip lots of steps and only write down the really important stuff. So why is it a good idea to start by writing down proofs such as the ones above? It's great practice! It's the only way I know that you'll gain enough experience that you'll be able do these simple proofs in your head with confidence.

### Conclusion

The basics of proof is simple. Look at what you need to prove, find the main connective, and find what to do in the prove-it table. Repeat until you run into a dead end. Then look at what you know (assumptions and facts you've already proved), find the main connectives in those formulas, and apply the use-it rules. Hopefully that let's you connect all the dots! Happy propositional proving.

## No comments:

## Post a Comment