文档介绍：Discrete Math puter Science
Ken Bogart Cliff Stein
Dept. of Mathematics Dept. puter Science
Dartmouth College Dartmouth College
June 23, 2002
2
This is a working draft of a textbook for a discrete mathematics course. This course is
designed to be taken puter science students. The prerequisites are first semester calculus
(Math 3) and the puter science course (CS 5). The class is meant to be taken
concurrently with or after the puter science course, Data Structures puter
Programming (CS 15). This class is a prerequite to Algorithms (CS 25) and it is mended
that it be taken before all CS courses other than 5 and 15.
c Copyright h P. Bogart and Cliff Stein 2002
Chapter 1
Counting
Basic Counting
About the course
In these notes, student activities alternate with explanations and extensions of the point of the
activities. The best way to use these notes is to try to master the student activity before beginning
the explanation that follows. The activities are largely meant to be done in groups in class; thus
for activities done out of class we mend trying to form a group of students to work together.
The reason that the class and these notes are designed in this way is to help students develop
their own habits of mathematical thought. There is considerable evidence that students who
are actively discovering what they are learning remember it far longer and are more likely to be
able to use it out of the context in which it was learned. Students are much more likely to ask
questions until they understand a subject when they are working in a small group with peers
rather than in a larger class with an instructor. There is also evidence that explaining ideas to
someone else helps anize these ideas in our own minds. However, different people learn
differently. Also the amount of material in discrete mathematics that is desirable puter
science students to learn is much more than can be covered in an academic term if all learning
is to be done th