An Informaticist Looks at Math Proofs, Part I: Learning the Rules

My interest in learning discrete math was triggered by a desire to understand Petri nets.   I never really intended to learn how to do math proofs because they always seemed too obscure to be grasped by mere mortals.   Like most people, by the time I picked up a discrete math book, I had already been treated (or better, mistreated) to proofs in books, especially calculus.

Typically, the author would present a theorem by somebody long-since dead in the form of a few English words that don’t mean what you think they mean followed by a collection of symbols.  Then, striving to be helpful and enlightening, he would proceed with something like: “Here is the proof for this theorem.  Let’s assume that x is a set and m is…”  Next would follow a series of Greek letters with signs or symbols (backwards Es and upside-down As) interspersed between them.     At this point, no matter how earnestly I had set out to read the proof, my mind would drift—symbol, x, +, blah, blah, symbol, puppies, blah, blah, girlfriend, blah, blah, hungry…

When I decided to learn discrete math, I ran into proofs big-time because learning to do proofs is a major component of discrete math.   Every discrete math book starts with logic and sets, then moves on to proofs, relations, and other basic topics.    In most books, the section on learning to do proofs is fairly brief–often consisting of a few sections that follow the predicate logic discussion.   Since my main interest was in graph theory (for Petri nets), I wanted to get to that topic as quickly as possible.    However, knowing that it was best to start at the beginning, I followed the author’s suggestions concerning chapter prerequisites.  This meant doing logic and sets before anything else.

Before finding my go-to text by Susanna Epp, I tried two other books (not Rosen).   In each, the sections on logic were understandable, but as soon as I got to the section on proofs, I hit a wall.  There was simply too great a leap from: “Here is an implication,” and “Here are some logic rules,” to “prove that the sum of any two odd numbers is even.”  Wait…what?

For a while, I had decided PhD math candidates learned proof writing in a manner akin to how apprentice sorcerers learn their trade–in dark, hidden rooms with flickering candles accessed by secret code words.     As it turns out, I simply needed a better book.

Discrete Mathematics with Applications, by Susanna Epp, dedicates four chapters to logic and proofs, letting the reader take baby steps in developing this skill.    More importantly, she takes the time to teach the “tricks of the trade” with especially good sections on valid argument forms and rules of inference.  These two topics, along with predicate logic, are essential for proof-writing. Once learned, writing proofs becomes much easier.

A brief review of implications
Implications are common in everyday life and in writing proofs.   Conditional statements consist of two statements – a hypothesis and a conclusion.  They use the form If-Then, as in “If it is raining, Then I wear a raincoat.”  Here, “It is raining” is the hypothesis, and “I wear my raincoat” is the conclusion.

Here is the truth table for a conditional statement.  The symbol “–>” is read as “implies” or “then” as in, If p, then p or p implies q.    p=It is raining; q= I wear a raincoat.

 p q p–> q 1 T T T 2 T F F 3 F T T 4 F F T

Table 1. Implication

Row 1 should be obvious.  It fits what we think is logical.    It says what we expect, “If it is raining, Then I wear a raincoat.  The third column has T, to signify the implication is true. Thus, if a friend said, “ If it rains, Then  I wear a raincoat,”  on every rainy day ever,  you would expect to see them wearing a raincoat.

Row 2 could be read as, “It is raining, and I am NOT wearing a raincoat.”   Row 2 is the negation of this implication. There is an F in the third column because in Row 2 raining does NOT lead to wearing a raincoat.   In this situation, you find that even though it is pouring, your friend is not wearing a raincoat.

Row 2 is important for writing proofs because the negation of any implication is a compound AND statement, written symbolically as p ^ ~q (p AND NOT q).  The negation of an implication is NEVER another implication; rather, it is always a compound statement connected by AND.  I make a point of this because many would be inclined to say that the negation of “IF it is raining, Then I wear a raincoat” is “If it is NOT raining, Then I DO NOT wear a raincoat.”  Nope.

Explaining why the implication is considered true even though the hypothesis is false in Rows 3 and 4 would take more trouble than it’s worth.  Let’s just leave it at that.

Implication forms and logical equivalence
Implications may be rearranged in specific ways.   In addition to the form discussed above, there are the contrapositive, inverse and converse versions as shown in Table 2.

 Original implication If it is raining, Then I wear a Raincoat p –> q Contrapositive If I am NOT wearing a raincoat, Then it is NOT raining ~q –> ~p Converse If I wear a raincoat, Then it is raining q –> p Inverse If it is NOT Raining, Then I am NOT wearing a raincoat ~p  –> ~q Negation It is raining AND I am NOT wearing  a raincoat p  ^ ~q

Table 2. Implication forms

The contrapositive form is very important for writing proofs because the contrapositive is logically equivalent to the original implication.   This allows one to substitute the contrapositive for the original implication when writing a proof, which is a handy trick since the contrapositive is sometimes easier to prove than the original implication.

Logical equivalence is proven with truth tables. If two statements are logically equivalent, they have identical truth tables. Table 3 shows the truth table for the contrapositive of an implication.  Compare the final column in Table 3 to the final column of Table 1, and you will see they have the same pattern of T/F values—proving they are logically equivalent.

 p q ~q ~p ~q–> ~p 1 T T F F T 2 T F T F F 3 F T F T T 4 F F T T T

Table 3. Contrapositive

Converse and inverse forms are not logically equivalent to the original implication and cannot be used in place of the original implication when writing proofs.

What is a valid argument?
An argument is a series of statements ending with a conclusion.  The statements leading to the conclusion are called premises.   Validity is essential for sound conclusions.   A valid argument is one in which the conclusion necessarily flows from the premises.  Put another way, if an argument is valid, then its conclusion must be true if its premises are true.   Fortunately, using truth tables, it is easy to determine if an argument form is valid.

A syllogism is an argument consisting of two premises and a conclusion.   A common type of syllogism that uses an implication as a premise is modus ponens.

A modus ponens argument has the form:

p –> q
p
Therefore, q.

Using our rain example, this argument goes as follows:

If it is raining, I wear a raincoat.
It is raining.
Therefore, I wear a raincoat
.

Now let’s look at this argument in a truth table and see why it is valid.

 Premise1 Premise2 Conclusion P Q P –> Q P Q T T T T T T F F T F F T T F T F F T F F

Table 4. Modus ponens argument form

When consulting a truth table, an argument is considered valid if, and only if, for every row in the table where the premises are true, the conclusion is true.  Looking at Table 4, one sees that only one row has T for Premise1, Premise2, and the Conclusion.   Further, there are no rows where the premises are true and the conclusion is false.

Writing proofs requires using valid argument forms and, as it turns out, there is a small set of valid argument forms that are referred to as rules of inference (for examples of invalid forms with truth tables see  What Are You Trying to Infer? – Part 2).   Table 5 lists common rules of inference with their names from the two most widely-used discrete math textbooks.

 Epp name Rosen name Symbolically Modus Ponens Modus Ponens p–>q p, Therefore, q Modus Tollens Modus Tollens p–>q ~q, Therefore,  ~p Generalization Addition p Therefore, p OR q q Therefore p OR q Specialization Simplification p AND q  Therefore, p p AND q Therefore, q Conjunction Conjunction p q Therefore,  p AND q Elimination Disjunctive syllogism p OR  q  ~q  Therefore, p  p OR  q ~p Therefore, q Transivity Hypothetical  syllogism p–>q  q–>r, Therefore, p–>r

Table 5. Valid argument forms

Once I understood validity and learned the rules of inference, proofs seemed much less mysterious.  Of course, I still had to learn what all of the symbols meant, which required learning predicate logic.  In the next post, I will discuss the trials and tribulations encountered in learning how to turn English into math symbols.  Until then…
___________________________

Epp, Susanna S. Discrete Mathematics with Applications. Belmont, CA: Thomson-Brooks/Cole, 2011.

Rosen, Kenneth H. Discrete Mathematics & Its Applications: With Combinatorics and Graph Theory. New Delhi: McGraw-Hill, 2012