A COGNITIVE APPROACH TO TEACHING LOGIC AND PROOF
Susanna S. Epp
Department of Mathematical Sciences
DePaul University
sepp@condor.depaul.edu
In the late 1970's I started teaching a course to help
students make the transition from a computationally oriented calculus
class to more abstract, theoretical classes in mathematics and
computer science. Members of my department were concerned that
students in our more advanced classes had great difficulty answering
what we considered to be quite simple abstract questions involving
proof and disproof, and certain foundational mathematical material was
receiving short shrift because teachers in the advanced classes wanted
to move quickly to more interesting topics. The rationale for the new
course was that it would solve these problems by giving students an
adequate amount of time in which to focus exclusively on techniques of
proof and disproof and topics like sets, functions, and relations.
Unfortunately, the solution was not so simple. In teaching
the course I found that student difficulties were much more profound
than I had imagined. In fact, I discovered, most of my students lived
in a different logical and linguistic world from the one I inhabited.
Yet to be able to engage effectively in abstract mathematical
thinking, students had to learn to function in my world. (For more
details see Epp, 1987.) My aim in teaching, therefore, became to help
my students develop new habits of mind as well as new knowledge.
Over the years of evolution of the course I've experimented
quite a lot. As a general principle I've tried to remain sensitive to
the kinds of difficulties students encounter and be constantly alert
for more effective ways to help them. In the two examples which
follow I describe how I've come to present two particular topics,
validity and basic notions of proof and counterexample.
EXAMPLE: TEACHING ABOUT VALIDITY
My main purpose in teaching about validity is to lay the
groundwork for understanding the process of deductive reasoning. Thus
I want students to develop insight into the fact that validity is
conditional, namely that in a valid form of argument when all the
premises are true the conclusion is necessarily true and that it's
only when all the premises are true that we have any information about
the truth or falsity of the conclusion. I also want at least the
better students to understand that the word "necessarily" means that
in any other argument of the given form, if the premises are true then
the conclusion is also true.
When I first started teaching a course in mathematical
reasoning, I decided against having students test the validity of
forms of argument in the statement calculus by checking to see whether
the corresponding conditional statement form was a tautology. This
approach seemed too static to insure that students who used it
correctly would develop the kind of dynamic understanding I was aiming
for. In the tautology approach the conditional aspect of validity,
which I wanted students to think about explicitly, might be hidden as
a mechanical part of truth table construction.
Instead I elected to use the format where students have to
identify explicitly the columns of the truth table that represent the
premises and the conclusion, consider each case where the premises are
all true, and then check that in each such case the conclusion is also
true.
Over time I discovered that simply using this method was not
sufficient to achieve my goal. It turned out that I needed to be much
more careful in my choice of examples and exercises than I had at
first realized was necessary. A small but significant number of
students made the mistake of declaring an argument to be valid if they
found one row of the truth table in which the premises and the
conclusion were all true. Recently I've come to see that this mistake
is part of a broader cognitive tendency to ignore quantification and
confound universal conditional statements and conjunctions. (Other
manifestations of this tendency are seen if one asks students to write
what it means for a set A to be a subset of a set B. Quite a few
respond "x is in A and x is in B", or the equivalent. [See endnote 1.]
Similarly, many students define a relation R to be symmetric if "xRy
and yRx".)
To counter the mistake, I began including, at the earliest
stage of the discussion of validity, examples and exercises designed
to make as obvious as possible that each individual row having true
premises must be checked. So now the first argument form I test for
validity (with much participation by members of the class) fails the
test but its truth table has several rows in which all the premises
and the conclusion are true. Of course, in discussing this example I
make much of the fact that some (but not all!) rows have all true
premises and a true conclusion so that (be careful!) every single row
with true premises must be checked. I also make sure that the first
homework assignment includes at least two exercises of this type (with
answers in the back of the book to give students immediate feedback if
they make a mistake), and I give a follow-up quiz with a similar
problem. (Often I sharpen the focus and shorten the length of this
quiz by supplying the truth table myself so that all the students have
to do is interpret it.) Actually I give the quiz to students in pairs
so that those students who have successfully caught on to the idea
become my allies in passing it along to their less receptive
colleagues.
I've found the combination of these measures to be quite
successful in achieving good student performance. Another benefit is
that it gives students concrete practice in determining the truth or
falsity of a universal conditional statement (which many of them
clearly need) and thus helps sharpen students' sensitivity to the
meaning of quantified statements and prepare the way for our
subsequent treatment of the predicate calculus.
Despite the success of these measures, however, many of my
students were still not coming to understand validity in the
conceptual way I was hoping for. I discovered that some rather good
students were able to perform the steps to test for validity but were
doing so mechanically without being able to articulate the connection
between the steps and the definition. For instance, in connection
with a class example one day a student stated, "It is invalid because
the result in row 3 is F." "What do you mean by 'result'," I asked
(nicely). It took several minutes of discussion, which involved most
of the rest of the class, until one student finally said that "result"
actually meant truth value of the conclusion.
The first countermeasure I took was to change the way I wrote
solutions to validity problems in the book I had developed to use for
the course. In the first edition I wrote the explanations for the
answers as ordinary text underneath the truth tables. (Epp, 1990, pp.
37-8) In the second edition I made the explanation part of the truth
table display itself. (Epp, 1995, p. 30) The reason I did this was
that in a problem solution containing a display students tend to
regard the text outside the display as extra explanatory material
rather than as a formal part of the answer. Incorporating a brief
explanation into the display sends an (admittedly subtle) message that
students are to include it in their own solutions.
When I next taught the course, I went a step further in
explicitness and changed the wording of my questions. Now instead of
just asking students to "determine whether the following argument form
is valid," I routinely add (both in class and on quizzes and exams):
"Include a few words of explanation for your answer." During class,
after student discussion has produced a truth table and a correct
analysis of it, I matter-of-factly summarize the result and the reason
for it on the board as if inclusion of these words is simply part of a
standard answer. For instance, on the basis of the discussion I might
draw an arrow to one row and write "This row shows that it is possible
for an argument of this form to have true premises and a false
conclusion; hence this argument form is invalid." Or I might write:
"Thus for each possible argument of this form in which the premises
are true, the conclusion is also true; hence the argument form is
valid." Hence all students are participants in a process that leads
to an answer which reinforces conceptual understanding, and students
taking notes have the answer available as a model for future
reference. Now when I ask for explanations about validity on quizzes
and exams, a remarkably larger number of students give very well
expressed answers, and almost all the rest express their answers
reasonably well. This result encourages me in the belief that
relatively small changes in instructional technique can have a major
impact on student understanding.
EXAMPLE: TEACHING ABOUT PROOF AND COUNTEREXAMPLE
In introducing students to the concepts of proof and
counterexample, my primary goal is to help them develop the ability to
evaluate the truth and falsity of simple mathematical statements. I
want them to get a feel for the flow of deductive argument, to
appreciate the role of definitions in mathematical reasoning, and to
learn to express themselves with clarity and coherence.
When I first started trying to teach students how to write
proofs, I was almost overwhelmed by the poor quality of their
attempts. Often their efforts consisted of little more than a few
disconnected calculations and imprecisely or incorrectly used words
and phrases which did not even necessarily advance the substance of
their cases. A few of my colleagues are so put off by such student
work that they avoid asking for proof altogether, focusing on the
purely computational even in advanced courses. Some argue that the
really "good" students will develop an ability to reason
mathematically by osmosis as they watch the teacher at the board and
that the other students are simply incapable of complex mathematical
abstraction. But in all likelihood those who make this argument have
themselves had the experience of improving their performance of a
complex skill by dint of persistent effort. We do not all have the
same innate gifts; hardly any of us will become Mozarts in music or
Gausses in mathematics, not by a long shot. And the level of
achievement attained will certainly vary from one person to another.
But with sustained effort and encouragement, I believe that everyone
is capable of improvement.
It seems to me that the very existence of student difficulties
with abstract thinking is reason for us to address them. The students
I teach are majoring in mathematics and computer science at a
selective university. In fact many are computer professionals with a
decade or more of experience. If they are having problems with what
we consider the most fundamental aspects of mathematical reasoning, it
should be one of our prime responsibilities to help them better their
performance.
A rather widely held belief among cognitive psychologists is
that the human brain consists of many parts which operate more or less
independently and which often do not communicate very well with each
other. [For instance, see Gazzaniga, 1985 or Minsky, 1987.] The
implication for education is that to learn a complex process such as
proof and disproof, many component intellectual skills must be
developed and effectively integrated. It is the teacher's job to
devise ways to help different students achieve such development and
integration.
Earlier in this century the Russian psychologist L. S.
Vygotsky coined the phrase "zone of proximal development." (Vygotsky,
1935). I confess that when I first heard these words, I dismissed
them as jargon. I've since come to view them as articulating a
profound truth about the educational process, namely that at any given
point in the learning process, the insight and intuitions the learner
has previously developed provide a basis that defines and limits the
amount that can be accomplished in the next stage of instruction.
Thus the depth of my understanding of the background ideas for a given
topic area and my skill in working with them determine how much I can
absorb in the next instructional session.
When I first started teaching a course in mathematical
reasoning, I covered preliminary material on logic in the briefest and
most perfunctory way before launching into specific topic such as
sets, functions, and relations. Over the years, however, I've come to
see the benefit of helping students broaden their zone of proximal
development before I introduce the concepts of proof and disproof
proper. So I now spend a few weeks at the beginning of the course
discussing basic notions of elementary logic and giving students
formal and informal practice in working with the language of the
logical connectives and the quantifiers. Also I now order the
mathematical subject matter in a way that takes students' cognitive
development into account. I begin the discussion of proof and
counterexample by considering properties of numbers (which are
familiar objects) and wait to cover set theory (whose proofs involve
nested quantification) until somewhat later.
One benefit of this approach is that students like it. It
provides them with a supportive framework which they can lean on while
the various aspects of proof and counterexample are falling into
place. It also gives them the impression that the course as a whole
has been carefully thought out and thereby increases their confidence
in the educational enterprise and their willingness to cooperate with
me. Moreover, preceding the discussion of proof and disproof with a
treatment of logic gives me a language in which to explain why we do
the things we do in proving and disproving mathematical statements and
a vocabulary with which to communicate with my students when they make
mistakes.
To help make the transition from elementary logic to proof, I
assign a number of puzzle problems similar to Raymond Smullyan's
knights and knaves. (See Smullyan, 1978.) When I discuss solutions
in class, quite a number of students make it clear that the kind of
indirect reasoning needed to solve most of the puzzles does not come
naturally to them. But almost all seem to enjoy working on the
puzzles, and doing so helps them develop a sense for the flow of
deductive reasoning they will use later in mathematical proofs of all
types and provides a basis of intuition for proof by contradiction.
The first statements I ask students to prove or disprove
concern such things as properties of even and odd integers, rational
numbers, divisibility, and so forth. In explaining what is involved
in establishing the truth or falsity of such statements, I rely
heavily on the previous work I've asked students to do in the sections
on logic. For instance, in the logic sections I try to motivate
acceptance for the forms of the negations of each type of statement by
discussing them interactively with the class, and I give students a
lot of practice writing negations (in English) of statements of each
form. My aim is to get students to incorporate into their own
thinking patterns the ability to take negations according to the rules
of formal logic. I reason that if students are eventually to be able
to evaluate mathematical statements for their truth and falsity, they
need to have a good intuition for what it means for various kinds of
statements to be false. In addition, the analysis of truth and
falsity in which students engage during the weeks devoted to logic
gives them insight into aspects of proof and disproof even before
these ideas are introduced formally. So, for example, when I
introduce the concept of disproof by counterexample quite a number of
students immediately understand its relation to the fact that the
negation of a universal statement is existential. And when I present
proof by contradiction, I can point out that such a proof begins by
supposing the negation of the statement to be proved and be confident
that every student will have had experience in learning how to write
negations correctly.
One of the most serious problems which arises in trying to
teach mathematical proof is that even rather simple proofs are built
atop a normally unexpressed substructure of great complexity _
logical, linguistic, and sociolinguistic (i.e., the use of
mathematical slang, in French "abuse de langage," and other
mathematical conventions). A teacher can easily write a "clarifying
analysis" for a proof which if students could read with understanding
they wouldn't need in the first place. Figuring out a way to describe
proof construction in simple terms while explaining enough to be
effective is probably a teacher's greatest challenge.
In my view the most important idea to communicate about proof
is that all proofs flow from something supposed to something to be
shown. It then becomes natural to consider what is supposed and what
is to be shown. The most common type of proof is direct and the most
common type of mathematical statement has the form "For all elements x
in a set D, if (hypothesis) then (conclusion)". A direct proof of
such a universal conditional statement has the following outline:
"Suppose that x is a particular but arbitrarily chosen (or generic)
element of D for which the hypothesis is true. We must show that x
makes the conclusion true also." I sometimes refer to this method,
descriptively albeit ponderously, as "generalizing from the generic
particular."
When I begin discussing this approach to proof, I try to
dramatize its power by showing how one can use it to outline proofs
couched in language one doesn't even understand. For instance, given
the statement "For all toths T, if T has a rath then every wade of T
is brillig," the outline of a proof would be "Suppose T is any toth
which has a rath. We must show that every wade of T is brillig."
This transformation may seem simple to us, but I am convinced that the
student who truly understands how to do it has taken a giant step
toward mathematical maturity.
Later on, after I've introduced proof by contraposition and
proof by contradiction as well as direct proof, I try to help students
keep the three basic proof methods separate by pointing out that while
for each method there is something that we suppose and something that
we show, these "somethings" are dramatically different in each case.
In a direct proof we suppose we have a particular but arbitrarily
chosen object that satisfies the hypothesis and show that this object
satisfies the conclusion. In a proof by contraposition we suppose we
have a particular but arbitrarily chosen object for which the
conclusion is false and we show that for this object the hypothesis is
also false. In a proof by contradiction we suppose that the entire
statement to be proved is false and show that this supposition leads
to a contradiction.
I must admit that while my approach works very well with a
certain fraction of students (in the sense that they do excellent work
at each stage of the course but also give me every impression that
they consider the course challenging and worthwhile), a significant
number of students have difficulty when they come actually to write
proofs. Partly, I think this is because the few weeks we've spent on
background material is not sufficient to overcome the casual attitudes
toward language and reasoning that they've developed over their
lifetimes. Some of them can't believe I'm serious about my demand for
coherence, while others accept it but have difficulty putting all the
pieces together correctly.
One countermeasure I've found very effective is to have
students present proofs from their homework assignment for the rest of
the class starting with the very first class period after proofs have
been assigned. I should mention that I try to do this in a way that
preserves the self-esteem of the presenters, thanking them for being
good sports when they volunteer and pointing out that to the extent
that they make mistakes, their mistakes and our discussion of them
will help the rest of the class develop a better understanding. If
the proofs are good, the other students get to see that the demands
made by their teacher can actually be met by one of their own kind.
If the proofs contain mistakes or sections that are not well
expressed, I ask for suggestions for improvement from the rest of the
class, urging them to be super critical, to imagine, for instance,
that the class as a whole is a research team for a company and if they
can come up with a "perfect" answer they'll get to share a large
monetary prize. After the class has finished its critique and some
changes have been recorded, I take my turn, explaining that I'm using
the opportunity to show them the kind of things I'll be looking for
when I grade their papers. I try to be "picky" but also to put my
criticisms in perspective, explaining frankly that certain corrections
are more important than others but that I also care about what might
seem to be relatively small points. For instance, if a student's
proof states that a certain number, say n, is even because it equals
2k, I would ask what was missing. Most likely, based on the emphasis
I'd previously placed on definitions, one of the other students would
say I should add "for some integer k." I would agree, pointing out
that 1 = 2x(1/2) and yet 1 is not even and adding that it's not enough
that n is 2 times something _ that "something" has to be an integer.
My main reason for engaging in this process is to give
students immediate feedback on their proof writing. But I also try to
use these occasions to counteract student anxiety about how their
proofs will be evaluated. Since there is more than one right way to
construct any given proof and since different instructors may well
have different standards of "correctness," I feel obliged to try to
give my students a sense of the range of proof styles I consider
acceptable and to indicate which parts of a proof I consider most
important. So when I critique student proofs, present my own, and
write proofs at the board that have been developed collaboratively
with members of the class, I try to discuss various alternative ways
of expressing the steps which I would consider acceptable. I also
talk about conventions of mathematical writing (such as giving only
part of the reason for a certain step, enough to indicate that the
writer of the proof has considered and resolved the issue but not so
much as to overload the proof with verbiage) [See endnote 2.] and the
fact that the amount of detail included in a proof varies considerably
depending on the audience. In my classes I generally suggest that
students aim their proofs at a fellow student who has missed a few
classes.
Other techniques I use to help students learn to write proofs
are (1) having them complete a few fill-in-the-blank proofs before
they start writing their own, (2) supplying complete answers for some
of their homework problems so that they come to see that I really mean
for their individual work to look something like the kind of thing
we've been doing in class, (3) making sure that even in a large class
I give each student detailed feedback about the work they've done on
each type of proof I assign (one good way to do this is to have
students submit one or two drafts of their solutions to a few selected
problems and make suggestions for improvement on each draft), (4)
discussing some of the kinds of errors often made in writing proofs
and assigning homework problems of the find-the-mistake variety. In
one way or another all these techniques reflect my belief that to
learn as complex a skill as proof construction, most students need
quite a bit of back-and-forth interaction with an instructor. To the
extent that I am not able to supply this personally, I have tried to
devise effective substitutes.
FINAL THOUGHTS
I don't claim that the kind of approaches I've described above
will turn every student who is exposed to them into a fully competent
mathematical reasoner. But I do see significant intellectual
development in most of my students, and I don't think the experience
has harmed those who appear to have benefited less from it. Indeed,
I've sometimes been surprised when students who in my view fell far
short of achieving the levels of accomplishment I strive for tell me
how valuable they found the course in helping them do better work in
their other courses or (I am always pleased to hear) in their jobs.
A couple of years ago I had an experience with one particular
class that made a special impression on me. The class was unusually
small, only twelve students, and was the second quarter of our
sequence. The previous quarter had dealt with logic, an introduction
to direct and indirect proof, mathematical induction, and elementary
combinatorics, all interwoven with various computer science
applications. This second quarter was to cover set theory, function
properties, recursion, some analysis of algorithms, relations on sets,
and an introduction to graph theory, also with an admixture of
applications. The class met only once a week but for a three-hour
session.
The small size of the class and the length of the sessions
gave me a chance to work with students more intimately than I'm used
to. I began each period by having students discuss in groups of three
or four the homework they had prepared for that day. I went from
group to group talking with each at length. Overall the class
atmosphere was excellent, and there were several students especially
who showed the kind of eager, enthusiastic intelligence that is a
teacher's joy. What surprised me was that as the course moved from one
topic to the next, almost all the students who had attained a
relatively sophisticated level of achievement in dealing with a
previous topic made it clear that they felt they had to struggle to
succeed with the next. Yet as we worked through their questions and
difficulties, they ultimately achieved an excellent level of
performance with the new topic as well. Their understanding of
general methodological principles clearly made it easier for them to
learn the new material but it didn't make it trivial for them.
Somehow this experience brought home to me more effectively
than any before that abstract mathematical thinking is not something
that either one is able to do or one is not able to do. Because of
the experience I've become especially conscious of the need to respect
my students and never to act surprised by their questions. Even when a
student asks a question whose answer I've already discussed, I try to
respond to it as if it were fresh. After all, nobody can concentrate
100% of the time when new ideas are coming in fast and furiously. In
all likelihood the student was not mentally prepared to absorb the
answer when I previously talked about it. For the student to
formulate the question at this point means that they've thought about
the issue, want to know the answer, and are probably ready to
understand it. That is cause to celebrate. And, very likely,
clarifying the issue at this point in the course (if possible in a
slightly different way from that presented earlier) will give the
other students in the class greater insight also.
My main advice to those teaching courses whose goal is to
develop students' mathematical reasoning powers is to play an activist
role but recognize that achieving success is a long-term process. The
analogy I like to draw is of a child learning to walk. It takes
months of daily effort for most children to take their first steps and
several more months until they actually become steady on their feet.
When a child is trying to move from one stage to the next in learning
to walk and has failed several times, we don't say "forget it." We
remain calm, good humored, and encouraging. And when the child
finally succeeds, we spare nothing in expressing our delight.
ENDNOTES
[1] The tendency to confuse conditionals and conjunctions is very
strong. Since I know students tend to make this mistake, I discuss
the definition of subset at length with them, eliciting from students
various alternative formal and informal ways of expressing it and
assigning homework exercises designed to force them to think about the
definition in various situations, and I specifically warn them against
confusing "if x e U then x e V" with "x e U and x e V". Considering
all these efforts, one might expect a virtually perfect response to
the following question asked on a quiz given the period after the
initial discussion and when students had had a chance to do the
homework: "Given sets U and V, what does it mean for U to be a subset
of V?" In fact, in a class of 38 students, only 20 gave a correct
answer, 1 answered essentially correctly, 6 answered ambiguously
(e.g., "Every element of U is in V. x e U and x e V."), 5 students
answered "x e U and x e V", 3 answered "Ax, x e U and x e V", and 3
gave miscellaneous incorrect answers. (In this note, A stands for
"for all" and e for "element of".)
[2] I point out that we follow such conventions so that we don't drown
the readers of our proofs in words but that in doing so we increase
our risk of error. Any given class is sure to give rise to examples
to illustrate this point, and I try to take advantage of them in my
discussions with the students. I've actually come to believe that one
of my functions as a teacher is to help students become comfortable
about making mistakes. After all when human beings engage in
mathematical reasoning, mistakes are inevitable. My best students
occasionally made howlers and so do I. Doesn't every mathematician?
Paradoxically, once students accept that mistakes in mathematical
reasoning are part of the game, they become more willing to make the
effort to avoid them.
REFERENCES
Epp, S. (1987). The logic of teaching calculus. In R. G. Douglas
(Ed.), Toward a Lean and Lively Calculus (pp.41-60). Washington, D.
C.: The Mathematical Association of America.
Epp, S. (1990). Discrete Mathematics with Applications. Belmont,
California: Wadsworth Publishing Company. (1995) Discrete Mathematics
with Applications, Second Edition. Boston, Massachusetts: PWS
Publishing.
Gazzaniga, M. S. (1985). The Social Brain: Discovering the Networks
of the Mind. New York: Basic Books.
Minsky, M. (1987). The Society of Mind. London: Heinemann.
Smullyan, R. (1978). What Is the Name of This Book? Englewood
Cliffs, New Jersey: Prentice-Hall.
Vygotsky, L. S. (1935). Mental Development of Children and the
Process of Learning. Translated as part of M. Cole et al. (Ed.)
(1978). Mind in Society. Cambridge, Massachusetts: Harvard University
Press.