How to Prove It

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 $\mathit{True}$ and $\mathit{False}$, negation ($\neg$), logical and ($\land$), logical or ($\lor$), and implication ($\to$). We refer to the symbols $\land$, $\lor$, etc. as logical connectives. $$\begin{array}{lrcl} \text{Variables} & p,q \\ \text{Formulas} & P,Q,R &::= & p \mid \mathit{True} \mid \mathit{False} \mid \neg P \\ & & & \mid P \land Q \mid P \lor Q \mid P \to Q \end{array}$$ The following is an example of a formula: $$(p \to q) \land \neg q \to \neg p$$

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: $p,q,q,p$. Working from the first $p$ and $q$ we have $(p \to q)$. (We just used the grammar rule $P ::= P \to Q$.) Working our way from the last $p$ we have $(\neg p)$. For the second occurrence of $q$ we have two choices, we can either go to the left to form $(\neg q)$ or we can go to the right and form $(q \to (\neg p))$. 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 $\neg$ is higher precedence than $\to$, so we go to the left and form $(\neg q)$. So far, we have parses for $$(p \to q), (\neg q), (\neg p)$$ Next, we need to decide whether to combine $(p \to q)$ and $(\neg q)$ with the connective $\land$, or whether to combine $(\neg q)$ and $(\neg p)$ with the connective $\to$. Again, we consider the precedences, and here $\land$ has higher precedence than $\to$. So we have the parses: $$((p \to q) \land (\neg q)), (\neg p)$$ The last step is to parse the last connective, $\to$, and complete the tree: $$(((p \to q) \land (\neg q)) \to (\neg p))$$ The root of the tree is the last connective that we added to complete the parse, in this case, the right-most $\to$. So we have found the main connective. It's also important to know the two sub-trees of the main connective. In this case, $$((p \to q) \land (\neg q)) \qquad (\neg p)$$

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.

1. $\neg P$: assume $P$ and prove $\mathit{False}$.
2. $P \land Q$: prove $P$ and also prove $Q$.
3. $P \lor Q$: prove one of $P$ or $Q$.
4. $P \to Q$: assume $P$ and then prove $Q$.

Our main connective is $\to$, so we can begin our proof using prove-it rule 4:

Assume $(p \to q) \land (\neg q)$.

$\vdots$
Therefore $(\neg p)$.

Therefore $((p \to q) \land (\neg q)) \to (\neg p)$.

The $\;\vdots\;$ represents the part of the proof that we haven't finished yet. The table told use to assume $P$, meaning that we should assume the first sub-tree under the implication, which in this case was $((p \to q) \land (\neg q))$. We need to prove $Q$, the second sub-tree, which in this case is $(\neg p)$.

At this point we need to prove $(\neg p)$, so we repeat the above process. The main connective is $\neg$, so rule 1 of the prove-it table tells us to assume $p$ and prove $\mathit{False}$.

Assume $((p \to q) \land (\neg q))$.

Assume $p$.

$\vdots$
Therefore $\mathit{False}$.

Therefore $(\neg p)$.

Therefore $((p \to q) \land (\neg q)) \to (\neg p)$.

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

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.

1. From $\neg P$ and $P$: have $Q$. (You get to choose any formula!)
2. From $P \land Q$: have $P$.
3. From $P \land Q$: have $Q$.
4. From $P \lor Q$, $P \to R$, and $Q \to R$: have $R$.
5. From $P \to Q$ and $P$: have $Q$.

We have the assumption $((p \to q) \land (\neg q))$, whose main connective is $\land$, so we apply the use-it rules 2 and 3.

Assume $((p \to q) \land (\neg q))$.

Have $p \to q$.
Have $\neg q$.
Assume $p$.

$\vdots$
Therefore $\mathit{False}$.

Therefore $(\neg p)$.

Therefore $((p \to q) \land (\neg q)) \to (\neg p)$.

Next we apply use-it rule 5 with $p \to q$ and $p$ to deduce $q$. (The fancy name for use-it rule 5 is modus ponens.)

Assume $((p \to q) \land (\neg q))$.

Have $p \to q$.
Have $\neg q$.
Assume $p$.

Have $q$.
$\vdots$
Therefore $\mathit{False}$.

Therefore $(\neg p)$.

Therefore $((p \to q) \land (\neg q)) \to (\neg p)$.

We now have $q$ and $\neg q$, so we can conclude anything at all. (We've reached a contradiction.) We want to prove $\mathit{False}$, 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.

Assume $((p \to q) \land (\neg q))$.

Have $p \to q$.
Have $\neg q$.
Assume $p$.

Have $q$.
Therefore $\mathit{False}$.

Therefore $(\neg p)$.

Therefore $((p \to q) \land (\neg q)) \to (\neg p)$.

Also, the name for the formula we just proved is 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 $$(p \lor q) \land (\neg p \lor r) \to q \lor r$$ Skipping a couple steps that we already know how to do, we arrive at the following partial proof.

Assume $(p \lor q) \land (\neg p \lor r)$.

Have $p \lor q$.
Have $\neg p \lor r$.
$\vdots$
Therefore $q \lor r$.

Therefore $(p \lor q) \land (\neg p \lor r) \to q \lor r$.

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 $p \lor q$ or the fact $\neg p \lor r$. 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.

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

Assume $(p \lor q) \land (\neg p \lor r)$.

Have $p \lor q$.
Have $\neg p \lor r$.
Assume $p$.

$\vdots$
Therefore $q \lor r$.

Therefore $p \to (q \lor r)$.
Assume $q$.

$\vdots$
Therefore $q \lor r$.

Therefore $q \to (q \lor r)$.
Therefore $q \lor r$.

Therefore $(p \lor q) \land (\neg p \lor r) \to q \lor r$.

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

Assume $(p \lor q) \land (\neg p \lor r)$.

Have $p \lor q$.
Have $\neg p \lor r$.
Assume $p$.

$\vdots$
Therefore $q \lor r$.

Therefore $p \to (q \lor r)$.
Assume $q$.

Therefore $q \lor r$.

Therefore $q \to (q \lor r)$.
Therefore $q \lor r$.

Therefore $(p \lor q) \land (\neg p \lor r) \to q \lor r$.

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: $\neg p \lor r$. To apply use-it rule 4, we'll need to prove a pair of implications. Again, let's choose $q \lor r$ as the $R$.

Assume $(p \lor q) \land (\neg p \lor r)$.

Have $p \lor q$.
Have $\neg p \lor r$.
Assume $p$.

Assume $\neg p$.

$\vdots$
Therefore $q \lor r$.

Therefore $\neg p \to (q \lor r)$.
Assume $r$.

$\vdots$
Therefore $q \lor r$.

Therefore $\neg p \to (q \lor r)$.
Therefore $q \lor r$.

Therefore $p \to (q \lor r)$.
Assume $q$.

Therefore $q \lor r$.

Therefore $q \to (q \lor r)$.
Therefore $q \lor r$.

Therefore $(p \lor q) \land (\neg p \lor r) \to q \lor r$.

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.

Assume $(p \lor q) \land (\neg p \lor r)$.

Have $p \lor q$.
Have $\neg p \lor r$.
Assume $p$.

Assume $\neg p$.

Therefore $q \lor r$.

Therefore $\neg p \to (q \lor r)$.
Assume $r$.

Therefore $q \lor r$.

Therefore $\neg p \to (q \lor r)$.
Therefore $q \lor r$.

Therefore $p \to (q \lor r)$.
Assume $q$.

Therefore $q \lor r$.

Therefore $q \to (q \lor r)$.
Therefore $q \lor r$.

Therefore $(p \lor q) \land (\neg p \lor r) \to q \lor r$.

Aside: The formula we have just proved is known as the 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.