# Logic and Proof

### Topics

## Introduction to :

As your English teacher would say, good writers vary their sentence structure. The same is true of conditional statements: after a while, the If-Then formula becomes a real snoozefest. Some ways to mix it up are: "All things satisfying *hypothesis* are *conclusion*" and "*Conclusion* whenever *hypothesis*."

However, mathematicians can be drier than the Sahara desert: they tend to write conditional statements as a formula *p* → *q*, where *p* is the hypothesis and *q* the conclusion. In fact, the old saying, "Mind your *p*'s and *q*'s," has its origins in this sort of mathematical logic.

### Sample Problem

Identify *p* and *q* in the following statements, translating them into *p* → *q* form.

(A) If it rains outside, then flowers will grow tomorrow.

(B) I cut off a finger whenever I peel rutabagas.

(C) All dogs go to heaven.

For (A), *p* = "it rains outside" and *q* = "flowers will grow tomorrow."

In (B), we may rewrite the statement as "If I peel rutabagas, then I cut off a finger," telling us that *p* = "I peel rutabagas" and *q* = "I cut off a finger."

Finally, we may rewrite (C) as "If it is a dog, then it will go to heaven," yielding *p* = "it is a dog" and *q* = "it will go to heaven."

The hypothesis and conclusion play very different roles in conditional statements. Duh. In other words, *p* → *q* and *q* → *p* mean very different things. It's kind of like subtraction: 5 – 3 gives a different answer than 3 – 5. To highlight this distinction, mathematicians have given a special name to the statement *q* → *p*: it is called the **converse** of *p* → *q*.

No, not *those* Converse.

### Sample Problem

Write the converse of the statement, "If something is a watermelon, then it has seeds."

We want to switch the hypothesis and the conclusion, which will give us: "If something has seeds, then it is a watermelon." Of course, this converse is obviously false, since apples, cucumbers, and sunflowers all have seeds and are not watermelons. At least not during their day jobs.

There are some other special ways of modifying implications. For example, if you negate (that means stick a "not" in front of) both the hypothesis and conclusion, you get the **inverse**: in symbols, not *p* → not *q* is the inverse of *p* → *q*. Finally, if you negate everything and flip *p* and *q* (taking the inverse of the converse, if you're fond of wordplay) then you get the **contrapositive**. Again in symbols, the contrapositive of *p* → *q* is the statement not *q* → not *p*. Fancy.

### Sample Problem

What is the inverse of the statement "All mirrors are shiny?" What is its contrapositive?

If we abbreviate the first statement as mirror → shiny, then the inverse would be not mirror → not shiny and the contrapositive would be not shiny → not mirror. Written in English, the inverse is, "If it is not a mirror, then it is not shiny," while the contrapositive is, "If it is not shiny, then it is not a mirror."

While we've seen that it's possible for a statement to be true while its converse is false, it turns out that the contrapositive is better behaved. Whenever a conditional statement is true, its contrapositive is also true and vice versa. Similarly, a statement's converse and its inverse are always either both true or both false. (Note that the inverse is the contrapositive of the converse. Can you show that?)