by Laurie L. Lacey, Schenectady County Community College

In a Discrete Structures, or Discrete Mathematics, course, it is common to devote a significant portion of the course to techniques of proof.  This is the case at Schenectady County Community College where I have taught Discrete Structures (previously known as Discrete Math) since 1999.  Many of my students are non-mathematics majors; often, they are computer science, computer information systems, or networking students.  Some of them are even liberal arts students! The concept of ‘proof ’ is often rather alien to these students.  The computer science program requires calculus while the other programs do not require it.  So there are very disparate mathematical backgrounds in any particular section in any particular semester.  It was a mystery to me, as a mathematician who has published programs of sorts (maplets with mapleapps.com), why the computer science, computer information systems, or networking majors did not see the connection between the techniques of mathematical proof and computer programming.  After all, they did relate truth tables, Euler circuits, minimal spanning trees, and even the Pigeonhole principle to their other classes.  After a few semesters, I realized that the students were concentrating on the words and not on the structures.  Once I understood the problem it was an easy extension to flowchart the basic structures for proofs.   Some students then saw why they were learning proofs, even though proofs remained difficult.  The techniques are still in development, but it may prove useful to other instructors faced with a similar dilemma.  However, I offer this caveat: the flowcharts are not meant to replace more traditional methods of teaching proofs.  I do not, and would not, use them exclusively, but only as a supplement to enhance the learning of techniques of proof.
The flowcharts really livened up the class.  The various computer majors began to discuss their programming classes in which they had previously seen flowcharts.   They then start to recognize the connection between mathematical proof and flowcharting.  Students tell me that the flowcharts allow them “to see the natural steps within the proofs” and some students referred to the flowcharts throughout the semester.  Flowcharts helped students “think like a mathematician” instead of just trying to memorize a series of steps.

The first type of proof that the students see is direct proof.  Usually, we begin with some very basic number theoretical proofs.   For example, the student may be asked to prove that the sum of two odd numbers is even.  [1]

While this seems basic to me, it “proves” to be the antithesis of basic to the beginning student who may not have had any course more advanced than Algebra II with Trigonometry.  After showing a few examples, I then display the following flowchart:

Now we can consider flowcharting an actual theorem such as

Theorem:  The sum of two odd numbers is an even number.

We can then turn this flowchart into a more standard proof:

Theorem:  The sum of two odd numbers is an even number.
Proof:  First we rewrite the statement as a conditional:  If x and y are two odd integers, then x + y is an even integer.  Let x = 2k + 1 for some integer k.  Let y = 2j + 1 for some integer j.  We need the sum x + y to be an integral multiple of two.  Observing that x + y = 2k + 1 + 2j +1, rearranging the terms, and simplifying gives x + y = 2k + 2j +2 = 2(k + j +1).  Since k + j + 1 is an integer, it follows that x + y is an even integer.

An example of a basic theorem that the students might prove by contradiction is the following. [1]

Theorem:  Prove that if x is a rational number and y is an irrational number, then x + y is an irrational number.

We could flowchart the proof of this theorem as illustrated here.

This is admittedly somewhat of an oversimplification of the complicated (for the students) concept of proof by contradiction.  It does, however, give the students a visual aid to help guide them through the proof.  I will leave it to the reader to synthesis the elements of the flowchart into an actual proof.

My Discrete Structures course usually has about 20 - 25 students and I find that I cannot always give each individual as much time as I would like. Difficult topics such as techniques of proof can present considerable challenges. The aim of the flowcharting is to make the connection between the mathematical proofs and the programs that the computer science and computer information systems students might be writing.  They might also pick up on the connection to the symbolic logic they are learning in Discrete Structures and their computer classes.  Some semesters, however, I find I have a number of liberal arts students signed up for the course. Those liberal arts students are not as familiar with the idea of flowcharting.  I would expect that for them, this method might not be as clarifying.   For those future semesters when my class is populated by computer science majors, I hope to elaborate further on the technique and to include flowcharts for proofs by mathematical induction.  I hope also to include flowcharts for existence proofs, which I cover some semesters.

Acknowledgment
I wish to thank Dr. Richard Goldstein of the State University of New York at Albany for reading this article prior to submission and for his encouragement.  I would also like to thank my students William Stedman and Claire Stawski for insightful comments.

[1]  Kolman, Busby, and Ross (2004).  Discrete Mathematical Structures. Upper Saddle River, NJ:  Pearson, Prentice Hall.

The Innovative Teaching Exchange is edited by Bonnie Gold.