To the Instructor Please also read the Why do we teach discrete mathematics?I think there are two good reasons.First, "To the Student." discrete mathematics is useful,especially to students whose interests lie in com- puter science and engineering,as well as those who plan to study probability, statistics,operations research,and other areas of modern applied mathematics. But I believe there is a second,more important reason to teach discrete mathe- matics.Discrete mathematics is an excellent venue for teaching students to write proofs. Thus this book has two primary objectives: to teach students fundamental concepts in discrete mathematics (from count- ing to basic cryptography to graph theory)and to teach students proof-writing skills. Audience and Prerequisites This text is designed for an introductory-level course on discrete mathematics. The aim is to introduce students to the world of mathematics through the ideas and topics of discrete mathematics. A course based on this textrequires only core high school mathematics:algebra and geometry.No calculus is presupposed or necessary. Serving the computer Discrete mathematics courses are taken by nearly all computer science and science/engineering computer engineering students.Consequently,some discrete mathematics courses student. focus on topics such as logic circuits,finite state automata,Turing machines,algo- rithms,and so on.Although these are interesting,important topics,there is more that a computer scientist/engineer should know.We take a broader approach.All of the material in this book is directly applicable to computer science and engineering, but it is presented from a mathematician's perspective.As college instructors,our job is to educate students,not just to train them.We serve our computer science and engineering students better by giving them a broader approach,by exposing them to different ideas and perspectives,and,above all,by helping them to think and write clearly.To be sure,in this book you will find algorithms and their analysis, but the emphasis is on mathematics. Topics Covered and Navigating the Sections The topics covered in this book include the nature of mathematics (definition,theorem,proof,and counterexample), ·basic logic, lists and sets, xix
Please also read the "To the Student." Serving the computer science/engineering student. To the Instructor Why do we teach discrete mathematics? I think there are two good reasons. First, discrete mathematics is useful, especially to students whose interests lie in computer science and engineering, as well as those who plan to study probability, statistics, operations research, and other areas of modem applied mathematics. But I believe there is a second, more important reason to teach discrete mathematics. Discrete mathematics is an excellent venue for teaching students to write proofs. Thus this book has two primary objectives: to teach students fundamental concepts in discrete mathematics (from counting to basic cryptography to graph theory) and to teach students proof-writing skills. Audience and Prerequisites This text is designed for an introductory-level course on discrete mathematics. The aim is to introduce students to the world of mathematics through the ideas and topics of discrete mathematics. A course based on this text requires only core high school mathematics: algebra and geometry. No calculus is presupposed or necessary. Discrete mathematics courses are taken by nearly all computer science and computer engineering students. Consequently, some discrete mathematics courses focus on topics such as logic circuits, finite state automata, Turing machines, algorithms, and so on. Although these are interesting, important topics, there is more that a computer scientist/engineer should know. We take a broader approach. All of the material in this book is directly applicable to computer science and engineering, but it is presented from a mathematician's perspective. As college instructors, our job is to educate students, not just to train them. We serve our computer science and engineering students better by giving them a broader approach, by exposing them to different ideas and perspectives, and, above all, by helping them to think and write clearly. To be sure, in this book you will find algorithms and their analysis, but the emphasis is on mathematics. Topics Covered and Navigating the Sections The topics covered in this book include the nature of mathematics (definition, theorem, proof, and counterexample), basic logic, lists and sets, xix
XX To the Instructor relations and partitions, advanced proof techniques, recurrence relations, functions and their properties, permutations and symmetry, discrete probability theory, number theory. group theory, public-key cryptography, graph theory,and partially ordered sets. Furthermore,enumeration(counting)and proof writing are developed throughout the text.Please consult the table of contents for more detail. Each section of this book corresponds (roughly)to one classroom lecture. Some sections do not require this much attention,and others require two lectures. There is enough material in this book for a year-long course in discrete math- ematics.If you are teaching a year-long sequence,you can cover all the sections. A semester course based on this text can be roughly divided into two halves. In the first half,core concepts are covered.This core consists of Sections 2 through 23(optionally omitting Sections 17 and 18). From there,the choice of topics depends on the needs and interests of the students.Sample course outlines are given below.The interdependence of the various sections is depicted in the following diagram. Fundamentals Collections Counting and Relations More Proof 1+2+3+4+5+6 +8+9+10+ 13→14+15+16 1920+21 12 17 18 22 Functions 46→47+48+49+51→52 广24广28 Graphs 50 23+25+26+27 Number Theory 53→54+55+56→57 34-+35+36+37 58 Partially Ordered Sets 38---- Algebra Probability →29+30+31→32+33 39*40+41-*42 43+44 45
xx To the Instructor relations and partitions, advanced proof techniques, recurrence relations, functions and their properties, permutations and symmetry, discrete probability theory, number theory, group theory, public-key cryptography, graph theory, and partially ordered sets. Furthermore, enumeration (counting) and proof writing are developed throughout the text. Please consult the table of contents for more detail. Each section of this book corresponds (roughly) to one classroom lecture. Some sections do not require this much attention, and others require two lectures. There is enough material in this book for a year-long course in discrete mathematics. If you are teaching a year-long sequence, you can cover all the sections. A semester course based on this text can be roughly divided into two halves. In the first half, core concepts are covered. This core consists of Sections 2 through 23 (optionally omitting Sections 17 and 18). From there, the choice of topics depends on the needs and interests of the students. Sample course outlines are given below. The interdependence of the various sections is depicted in the following diagram. Fundamentals Collections Counting and Relations More Proof 1._2._3._4.-5-+-6t +-7-+-8-+-9--10--11-- ~13-+-14-+-15-+-16 19-+-20-+-21- t 1\ 12 17 1~ I zt I -------------------------------------------------------------------------- I I I Functions t ... r24r28 - -46-+-47-+-48-+-49-+-51-+-52 Graphs t ~23-+-25-+-26-+-27 50 ' Number Theory ~ 53-+-54-+-55-+-56-+-57 + 34-+-35-+-36-+-37 58 t 38-------- ------------~ Partially Ordered Sets I : I I Probability L Algebra : 1 L+-29-30-+-31-+-32--33 I ,,,--,--,~ i-+-39--40-41·--42 43-+-44 I I • 45
To the Instructor XXi Sample Course Outlines Thanks to its plentiful selection of topics,this book can serve a variety of dis- crete mathematics courses.The following outlines provide some ideas on how to structure a course based on this book. Computer science/engineering focus:Cover sections 1-16,19-23,28,29- 33,34-36,46-49,and 51.This plan covers the core material,special com- puter science notation,discrete probability,essential number theory,and graph theory. Abstract algebra focus:Cover sections 1-16,19-27,and 34-45.This plan covers the core material,permutations and symmetry,number theory,group theory,and cryptography. Discrete structures focus:Cover sections 1-26,46-56,and 58.This plan includes the core material,inclusion-exclusion,multisets,permutations,graph theory,and partially ordered sets. Broad focus:Cover sections 1-16,19-23,25-26,34-38,42-45,and 46-52. This plan covers the core material,permutations,number theory,cryptogra- phy,and graph theory.It most closely resembles the course I teach at Johns Hopkins. Special Features Proof templates:Many students find proof writing difficult.When presented with a task such as proving two sets are equal,they have trouble structuring their proof and don't know what to write first.(See Proof Template 5 on page 51.)The proof templates appearing throughout this book give students the basic skeleton of the proof as well as boilerplate language.A list of the proof templates appears on the inside front cover. Growing proofs:Experienced mathematicians can write proofs sentence by sentence in proper order.They are able to do so because they can see the entire proof in their minds before they begin.Novice mathematicians(our students) often cannot see the whole proof before they begin.It is difficult for a student to learn how to write a proof simply by studying completed examples.I instruct students to begin their proofs by first writing the first sentence and next writing the last sentence.We then work the proof from both ends until we (ideally) meet in the middle. This approach is presented in the text through ever-expanding proofs in which the new sentences appear in color.See,for example,the proof of Proposition 11.11 (pages 69-73). Mathspeak:Mathematicians write well.We are concerned with expressing our ideas clearly and precisely.However,we change the meaning of some words (e.g.,injection and group)to suit our needs.We invent new words (e.g., poset and bijection),and we change the part of speech of others (e.g.,we use the noun maximum and the preposition onto as adjectives).I point out and explain many of the idiosyncrasies of mathematical English in marginal notes flagged with the term Mathspeak
To the Instructor xxi Sample Course Outlines Thanks to its plentiful selection of topics, this book can serve a variety of discrete mathematics courses. The following outlines provide some ideas on how to structure a course based on this book. Computer science/engineering focus: Cover sections 1-16, 19-23, 28, 29- 33, 34-36, 46-49, and 51. This plan covers the core material, special computer science notation, discrete probability, essential number theory, and graph theory. · Abstract algebra focus: Cover sections 1-16, 19-27, and 34-45. This plan covers the core material, permutations and symmetry, number theory, group theory, and cryptography. • Discrete structures focus: Cover sections 1-26, 46-56, and 58. This plan includes the core material, inclusion-exclusion, multi sets, permutations, graph theory, and partially ordered sets. · Broad focus: Cover sections 1-16, 19-23, 25-26, 34-38,42-45, and 46-52. This plan covers the core material, permutations, number theory, cryptography, and graph theory. It most closely resembles the course I teach at Johns Hopkins. Special Features • Proof templates: Many students find proof writing difficult. When presented with a task such as proving two sets are equal, they have trouble structuring their proof and don't know what to write first. (See Proof Template 5 on page 51.) The proof templates appearing throughout this book give students the basic skeleton of the proof as well as boilerplate language. A list of the proof templates appears on the inside front cover. Growing proofs: Experienced mathematicians can write proofs sentence by sentence in proper order. They are able to do so because they can see the entire proof in their minds before they begin. Novice mathematicians (our students) often cannot see the whole proof before they begin. It is difficult for a student to learn how to write a proof simply by studying completed examples. I instruct students to begin their proofs by first writing the first sentence and next writing the last sentence. We then work the proof from both ends until we (ideally) meet in the middle. This approach is presented in the text through ever-expanding proofs in which the new sentences appear in color. See, for example, the proof of Proposition 11.11 (pages 69-73). • Mathspeak: Mathematicians write well. We are concerned with expressing our ideas clearly and precisely. However, we change the meaning of some words (e.g., injection and group) to suit our needs. We invent new words (e.g., poset and bijection), and we change the part of speech of others (e.g., we use the noun maximum and the preposition onto as adjectives). I point out and explain many of the idiosyncrasies of mathematical English in marginal notes flagged with the term Mathspeak
xxii To the Instructor Hints:Appendix A contains an extensive collection of hints (and some an- swers).It is often difficult to give hints that point a student in the correct direction without revealing the full answer.Some hints may give away too much,and others may be cryptic,but on balance,students will find this sec- tion enormously helpful.They should be instructed to consult this section only after mounting a hearty first attack on the problems. Answers:An Instructor's Guide and Solutions book is available from Brooks/Cole.Not only does this supplement give solutions to all the problems, it also gives helpful tips for teaching each of the sections. Self tests:Every chapter ends with a self test for students.Complete answers appear in Appendix B.These problems are of varying degrees of difficulty. Instructors may wish to specify which problems students should attempt in case not all sections of a chapter have been covered in class
xxii To the Instructor • Hints: Appendix A contains an extensive collection of hint~ (and some answers). It is often difficult to give hints that point a studerit in the correct direction without revealing the full answer. Some hints may give away too much, and others may be cryptic, but on balance, students will find this section enormously helpful. They should be instructed to consult this section only after mounting a hearty first attack on the problems. · Answers: An Instructor's Guide and Solutions book is available from Brooks/Cole. Not only does this supplement give solutions to all the problems, it also gives helpful tips for teaching each of the sections. Self tests: Every chapter ends with a self test for students. Complete answers appear in Appendix B. These problems are of varying degrees of difficulty. Instructors may wish to specify which problems students should attempt in case not all sections of a chapter have been covered in class
What's new in this Second Edition In addition to correcting various errors (thank you to all those who wrote!),the following new features have been added: Self tests:These are described at the end of the previous section. A new example proof in Section 4:A number of instructors remarked that the first statements proved (sum of evens is even and transitivity of divisibility) are too simplistic.A new example has been added that is moderately more complicated. Section 12 is entirely new and gives a more thorough introduction to combi- natorial proof via two nontrivial examples. Section 21 on induction has been expanded and made essentially independent of Section 20 on proof by smallest counterexample. Section 22 on recurrence relations is entirely new.We develop methods(with full supporting theory)to solve first-and second-order homogeneous constant coefficient recurrence relations.First-order recurrence relations are solved in both the homogeneous and nonhomogeneous cases,whereas the second-order equations are solved only in the homogeneous case(but the more general case is explored in an exercise). We also show how to find the formula for the nth term of a sequence of numbers if that sequence is generated by a polynomial function of n. Section 26 includes a new proof that two decompositions of a permutation into transpositions must have the same parity.The new proof avoids the tedious consideration of inversions in a permutation and is based on T.L.Bartlow, "An historical note on the parity of permutations,"American Mathematical Monthly 79(1972)766-769 and S.Nelson,"Defining the sign of a permuta- tion,"American Mathematical Monthly 94 (1987)543-545. There is a new opening section that describes the pleasure of doing mathe- matics. xxiii
r What's New in This Second Edition In addition to correcting various errors (thank you to all those who wrote!), the following new features have been added: Self tests: These are described at the end of the previous section. A new example proof in Section 4: A number of instructors remarked that the first statements proved (sum of evens is even and transitivity of divisibility) are too simplistic. A new example has been added that is moderately more complicated. Section 12 is entirely new and gives a more thorough introduction to combinatorial proof via two nontrivial examples. Section 21 on induction has been expanded and made essentially independent of Section 20 on proof by smallest counterexample. Section 22 on recurrence relations is entirely new. We develop methods (with full supporting theory) to solve first- and second-order homogeneous constant coefficient recurrence relations. First-order recurrence relations are solved in both the homogeneous and nonhomogeneous cases, whereas the second-order equations are solved only in the homogeneous case (but the more general case is explored in an exercise). We also show how to find the formula for the nth term of a sequence of numbers if that sequence is generated by a polynomial function of n. Section 26 includes a new proof that two decompositions of a permutation into transpositions must have the same parity. The new proof avoids the tedious consideration of inversions in a permutation and is based on T. L. Bartlow, "An historical note on the parity of permutations," American Mathematical Monthly 79 (1972) 766-769 and S. Nelson, "Defining the sign of a permutation," American Mathematical Monthly 94 (1987) 543-545. There is a new opening section that describes the pleasure of doing mathematics. xxiii