A * proof* is an argument from *
hypotheses* (assumptions) to a * conclusion*.
Each step of the argument follows the laws of logic. In mathematics,
a statement is not accepted as valid or correct unless it is
accompanied by a proof. This insistence on proof is one of the things
that sets mathematics apart from other subjects.

Writing proofs is difficult; there are no procedures which you can
follow which will guarantee success. *The patterns which proofs
follow are complicated, and there are a lot of them.* You can't
expect to do proofs by following rules, memorizing formulas, or
looking at a few examples in a book.

For this reason, I'll start by discussing * logic
proofs*. Since they are more highly patterned than most proofs,
they are a good place to start. They'll be written in * column format*, with each step justified by a * rule of inference*. Most of the rules of inference
will come from tautologies. Since a tautology is a statement which is
"always true", it makes sense to use them in drawing
conclusions.

Like most proofs, logic proofs usually begin with *
premises* --- statements that you're allowed to assume. The * conclusion* is the statement that you need to
prove. The idea is to operate on the premises using rules of
inference until you arrive at the conclusion.

* Rule of Premises.* You may write down a * premise* at any point in a proof.

The second rule of inference is one that you'll use in most logic
proofs. It is sometimes called * modus ponendo
ponens*, but I'll use a shorter name.

* Modus Ponens.* If you know P and , you may write down Q.

In the rules of inference, it's understood that symbols like
"P" and "Q" may be replaced by *any*
statements, including compound statements.

* Example.* Here's a simple example of modus
ponens. Suppose that P and are premises. Then I
can use modus ponens to derive Q:

I'll write logic proofs in 3 columns. The statements in logic proofs are numbered so that you can refer to them, and the numbers go in the first column. The actual statements go in the second column. The third column contains your justification for writing down the statement.

Thus, statements 1 (P) and 2 ( ) are
premises, so the rule of premises allows me to write them down. Modus
ponens says that if I've already written down P and --- on *any* earlier lines, in either order
--- then I may write down Q. I did that in line 3, citing the rule
("Modus ponens") and the lines (1 and 2) which contained
the statements I needed to apply modus ponens.

Here's another example.

There are several things to notice here. First, is taking the place of P in the modus
ponens rule, and is taking the place of Q. As I
remarked prior to this example, "P" and "Q" can
be *any* statements, including compound statements.

Notice also that the if-then statement is listed first and the antecedent is listed second. It doesn't matter which one has been written down first, and long as both have been written down before you apply modus ponens.

Finally, the statement didn't take part in the modus ponens step. Perhaps this is part of a bigger proof, and will be used later. The fact that it came between the two modus ponens pieces doesn't make a difference.

* Double Negation.* In any statement, you may
substitute P for or for P (and write down the new statement).

* Example.* In this example, I'm applying
double negation with P replaced by :

Double negation comes up often enough that, as a shortcut, I'll often skip a step and use it without mentioning it explicitly. I'll demonstrate this in the examples for some of the other rules of inference.

* Modus tollens.* If you know and , you may write down
.

* Example.* Here's a simple example of modus
tollens:

In the next example, I'm applying modus tollens with P replaced by C and Q replaced by :

* Disjunctive Syllogism.* If you know and , you may write down Q.

* Example.* Here's the simplest form of
disjunctive syllogism:

In the next example, I'm applying disjunctive syllogism with replacing P and D replacing Q in the rule:

In the next example, notice that P is the same as , so it's the negation of .

This is a case where I'm skipping a double negation step. Without skipping the step, the proof would look like this:

* DeMorgan's Law.* In any statement, you may
substitute:

1. for .

2. for .

3. for .

4. for .

As usual, after you've substituted, you write down the new statement.

DeMorgan's Law tells you how to distribute across or , or how to factor out of or . To distribute, you attach to each term, then change to or to . To factor, you factor out of each term, then change to or to .

* Example.*

Notice that a literal application of DeMorgan would have given . I changed this to , suppressing the double negation step.

* Constructing a Conjunction.* If you know P and
Q, you may write down .

* Example.* In this example, notice that I put
the pieces in parentheses to group them after constructing the
conjunction.

* Rule of Syllogism.* If you know and , then you may write
down .

* Example.* The Rule of Syllogism says that you
can "chain" syllogisms together. For example:

* Definition of Biconditional.* If you know
, you may write down and you may write down . If you know and , you may write down .

* Example.*

* Decomposing a Conjunction.* If you know , you may write down P and you may write down Q.

* Example.* You can decompose a conjunction to
get the individual pieces:

Note that you *can't* decompose a disjunction!

Knowing that is true, you know that
*one* of P or Q must be true. The problem is that you don't
know *which one* is true, so you can't *assume* that
either one in particular is true.

* Constructing a Disjunction.* If you know P, and
Q is *any* statement, you may write down .

* Example.* If you know a statement, you can
"or" it with {\it any other statement} to construct a
disjunction.

Notice that it doesn't matter what the other statement is!

* Commutativity of Conjunctions.* In any
statement, you may substitute for (and write down the new statement).

* Commutativity of Disjunctions.* In any
statement, you may substitute for (and write down the new statement).

* Example.* The commutativity rules are so easy
that I'll often use them without explicit mention. They say that you
can write the terms in an "or" statement or an
"and" statement in either order.

Here is commutativity for a conjunction:

Here is commutativity for a disjunction:

Before I give some examples of logic proofs, I'll explain where the
rules of inference come from. You've probably noticed that the rules
of inference correspond to tautologies. In fact, you can start with
tautologies and use a small number of * simple
inference rules* to derive all the other inference rules.

Three of the simple rules were stated above: The Rule of Premises, Modus Ponens, and Constructing a Conjunction. Here are two others:

* Equivalence* You may replace a statement by
another that is logically equivalent. (Recall that P and Q are * logically equivalent* if and only if is a tautology.)

For instance, since P and are logically equivalent, you can replace P with or with P. This is Double Negation.

* Substitution.* You may take a known tautology
and substitute for the simple statements.

* Example.* The Disjunctive Syllogism tautology
says

Suppose you have and as premises. Here's how you'd apply the simple inference rules and the Disjunctive Syllogism tautology:

Notice that I used four of the five simple inference rules: the Rule of Premises, Modus Ponens, Constructing a Conjunction, and Substitution. In line 4, I used the Disjunctive Syllogism tautology by substituting

(Some people use the word "instantiation" for this kind of substitution.)

The advantage of this approach is that you have only five simple rules of inference. The disadvantage is that the proofs tend to be longer. With the approach I'll use, Disjunctive Syllogism is a rule of inference, and the proof is:

The approach I'm using turns the tautologies into rules of inference
beforehand, and for that reason you won't need to use the Equivalence
and Substitution rules that often. But you *are* allowed to
use them, and here's where they might be useful. Suppose you're
writing a proof and you'd like to use a rule of inference --- but it
wasn't mentioned above. Write down the corresponding logical
statement, then construct the truth table to prove it's a tautology
(if it isn't on the tautology list). Then use Substitution to use
your new tautology.

If you go to the market for pizza, one approach is to buy the ingredients --- the crust, the sauce, the cheese, the toppings --- take everything home, assemble the pizza, and put it in the oven. Using tautologies together with the five simple inference rules is like making the pizza from scratch. But you could also go to the market and buy a frozen pizza, take it home, and put it in the oven. Using lots of rules of inference that come from tautologies --- the approach I'll use --- is like getting the frozen pizza.

Here are some proofs which use the rules of inference. In each case,
some * premises* --- statements that are assumed
to be true --- are given, as well as a statement to prove. A proof
consists of using the rules of inference to produce the statement to
prove from the premises.

* Example.* Premises: .

Prove: C.

It is one thing to see that the steps are correct; it's another thing
to see how you would think of making them. I used my * experience with logical forms* combined with * working backward*.

I'm trying to prove C, so I looked for statements containing C. Only the first premise contains C. I saw that C was contained in the consequent of an if-then; by modus ponens, the consequent follows if you know the antecedent.

The antecedent of the first premise is . Hence, I looked for another premise containing A or . The only other premise containing A is the second one. In this case, A appears as the antecedent of an if-then. By modus tollens, follows from the negation of the consequent B. But I noticed that I had as a premise, so all that remained was to run all those steps forward and write everything up.

In order to do this, I needed to have a hands-on familiarity with the basic rules of inference: Modus ponens, modus tollens, and so forth. You'll acquire this familiarity by writing logic proofs.

You also have to concentrate in order to remember where you are as you work backwards. You may need to scribble stuff on scratch paper to avoid getting confused. Keep practicing, and you'll find that this gets easier with time.

* Example.* Premises: .

Prove: .

* Example.* Premises: .

Prove: B.

Notice that in step 3, I would have gotten . I omitted the double negation step, as I have in other examples.

Copyright 2009 by Bruce Ikenaga