# Logic and Proof

### Topics

## Introduction to :

You have been cordially invited to attend the Formal Proof. Please dress in the appropriate attire. Form two columns and show this invitation at the door for admittance. Complimentary cheesecake will be provided.

Only one part of that is true and unfortunately, it's not the part about the cheesecake. We do have to form two columns. The left column is a (usually numbered) list of statements that logically follow each other. The right column is a list of reasons (or justifications) for these statements, just in case we need a little help going from one statement to the next.

Usually you are asked to prove an implication, a conditional statement with a hypothesis (sometimes several) and a conclusion. To prove such a thing, the first step is detaching the hypothesis from the conclusion, and assume the hypothesis as given. Then, write a bunch of statements and reasons until you end up with the conclusion.

Naturally, the tricky part is figuring out which statements will take you to the conclusionâ€”it's a bit of a guessing game. Sometimes it will take several tries before you reach the desired conclusion. Don't worry, when you finally get there it will be that much more satisfying.

### Sample Problem

Write a formal proof of the big train in the last section. That is, if *A* = *B* and *B* = *C* and *C* = *D*, then *A* = *D*.

Here, our given facts are the hypothesis of the conditional statement, namely *A* = *B*, *B* = *C*, and *C* = *D*. The fact we want to prove is *A* = *D*, so that should be our last statement in the list. Here's a good formal proof:

Statements | Reasons |

1. A = B | Given |

2. B = C | Given |

3. C = D | Given |

4. A = C | Transitive Property (1 and 2) |

5. A = D | Transitive Property (4 and 3) |

We can list the given statements first, since they don't require any reason beyond "given." ("Given" simply means that you're assuming them as a hypothesis, so the problem "gives" them to you. Happy birthday!) Statement 4, *A* = *C*, follows from applying the transitive property to *A* = *B* and *B* = *C*.

Technically, we are also using the law of detachment here, but the laws of detachment and syllogism are used so often that we don't write down when we use them. In fact, almost every single non-given line of every proof uses one or the other; if we wrote them down, we'd spend hours on each proof just writing "detachment" twenty times. Instead, we'll say they're implied and save a couple (thousand) trees.

Finally, statement 5, *A* = *D*, follows from using the transitive property on statements 4 and 3. Since statement 5 is what we wanted to prove, we're done. Hooray!

Some **formal** or **two-column proofs** don't use the parentheses in the justification statements (telling exactly which of the statements you use), and sometimes it's even okay to lump together several steps at once. For example, some might consider this an acceptable proof:

Statements | Reasons |

1. A = B, B = C, C = D | Given |

2. A = C | Transitive Property |

3. A = D | Transitive Property |

The idea is that we give enough information for the reader to be able to decipher our proofs. We think it's a good idea to write proofs more like the first one, since it's always a good habit to be as precise as possible, but how you write your proofs is up to you.