Discrete Mathematics - University of Pennsylvania

1 Jean GallierDiscrete MathematicsDecember 11, 2010 SpringerTo my family, especially Anne and Mia, fortheir love and endurancePrefaceThe curriculum of most undergraduate programs in computer science includes acourse titledDiscrete Mathematics . These days, given that many students who grad-uate with a degree in computer science end up with jobs where mathematical skillsseem basically of no use,1one may ask why these students should take such acourse. And if they do, what are the most basic notions that they should learn?As to the first question, I strongly believe thatallcomputer science studentsshould take such a course and I will try justifying this assertion main reason is that, based on my experience of more than twenty-five yearsof teaching, I have found that the majority of the students find it very difficult topresent an argument in a rigorous fashion.

2 The notion of a proof is something veryfuzzy for most students and even the need for the rigorous justification of a claimis not so clear to most of them. Yet, they will all write complex computer programsand it seems rather crucial that they should understand the basic issues of programcorrectness. It also seems rather crucial that they should possess some basic mathe-matical skills to analyze, even in a crude way, the complexity of the programs theywill write. Don Knuth has argued these points more eloquently than I can in hisbeautiful book,Concrete Mathematics , and I do not elaborate on this any a scholarly level, I argue that some basic mathematical knowledge should bepart of the scientificcultureof any computer science student and more broadly, ofany engineering , if we believe that computer science students should have some basic math-ematical knowledge, what should it be?

3 There is no simple answer. Indeed, students with an interest in algorithms andcomplexity will need some Discrete Mathematics such as combinatorics and graphtheory but students interested in computer graphics or computer vision will needsome geometry and some continuous Mathematics . Students interested in databaseswill need to know some mathematical logic and students interested in computerarchitecture will need yet a different brand of Mathematics . So, what s the commoncore?1In fact, some people would even argue that such skills constitute a handicap!viiviiiPrefaceAs I said earlier, most students have a very fuzzy idea of what a proof is. Thisis actually true of most people. The reason is simple: it is quite difficult to defineprecisely what a proof is. To do this, one has to define precisely what are the rulesof mathematical reasoning and this is a lot harder than it looks.

4 Of course, definingand analyzing the notion of proof is a major goal of mathematical attempted some twenty years ago to demystify logic for computer sci-entists and being an incorrigible optimist, I still believe that there is great value inattempting to teach people the basic principles of mathematical reasoning in a pre-cise but not overly formal manner. In these notes, I define the notion of proof as acertain kind of tree whose inner nodes respect certain proof rules presented in thestyle of a natural deduction system a la Prawitz. Of course, this has been done be-fore ( , in van Dalen [6]) but our presentation has more of a computer science flavor which should make it more easily digestible by our intended audience. Usingsuch a proof system, it is easy to describe very clearly what is a proof by contra-diction and to introduce the subtle notion of constructive proof.

5 We even questionthe supremacy of classical logic, making our students aware of the fact that thereisn t just one logic, but different systems of logic, which often comes as a shock provided a firm foundation for the notion of proof, we proceed with aquick and informal review of the first seven axioms of Zermelo Fraenkel set are usually surprised to hear that axioms are needed to ensure such a thingas the existence of the union of two sets and I respond by stressing that one shouldalways keep a healthy dose of skepticism in next? Again, my experience has been that most students do not have a clearidea of what a function is, even less of a partial function. Yet, computer programsmay not terminate for all input, so the notion of partial function is crucial. Thus, wecarefully define relations, functions, and partial functions and investigate some oftheir properties (being injective, surjective, bijective).

6 One of the major stumbling blocks for students is the notion of proof by induc-tion and its cousin, the definition of functions by recursion. We spend quite a bit oftime clarifying these concepts and we give a proof of the validity of the inductionprinciple from the fact that the natural numbers are well ordered. We also discussthe pigeonhole principle and some basic facts about equinumerosity, without intro-ducing cardinal introduce some elementary concepts of combinatorics in terms of countingproblems. We introduce the binomial and multinomial coefficients and study someof their properties and we conclude with the inclusion exclusion , we introduce partial orders, well-founded sets, and complete way, students become aware of the fact that the induction principle applies tosets with an ordering far more complex that the ordering on the natural an application, we prove the unique prime factorization inZand discuss gcdsand versions of the Euclidean algorithm to compute gcds including the so-calledextended Euclidean algorithm which relates to the Bezout extremely important concept is that of an equivalence relation and therelated notion of a applications of the material on elementary number theory presented in Sec-tion.

7 In Section we give an introduction to Fibonacci and Lucas numbers aswell as Mersenne numbers and in Sections , , and , we present some ba-sics of public key cryptography and the RSA system. These sections contain somebeautiful material and they should be viewed as an incentive for the reader to take adeeper look into the fascinating and mysterious world of prime numbers and moregenerally, number theory. This material is also a gold mine of programming assign-ments and of problems involving proofs by have included some material on lattices, Tarski s fixed point theorem, dis-tributive lattices, Boolean algebras, and Heyting algebras. These topics are some-what more advanced and can be omitted from the core .The last topic that we consider crucial is graph theory. We give a fairly completepresentation of the basic concepts of graph theory: directed and undirected graphs,paths, cycles, spanning trees, cocycles, cotrees, flows, and tensions, Eulerian andHamiltonian cycles, matchings, coverings, and planar graphs.

8 We also discuss thenetwork flow problem and prove the max-flow min-cut theorem in an original waydue to M. notes grew out of lectures I gave in 2005 while teaching CIS260, Math-ematical Foundations of Computer Science. There is more material than can becovered in one semester and some choices have to be made regarding what to , when I taught this course, I was unable to cover any graph theory. Ialso did not cover lattices and Boolean the notion of a graph is so fundamental in computer science (and else-where), I have restructured these notes by splitting the material on graphs into twoparts and by including the introductory part on graphs (Chapter 3) before the in-troduction to combinatorics (Chapter 4). The only small inconvenience in doingso is that this causes a forward reference to the notion of an equivalence relationwhich only appears in Chapter 5.

9 This is not a serious problem. In fact, this givesus a chance to introduce the important concept of an equivalence relation early on,without any proof, and then to revisit this notion more rigorously later readers may be disappointed by the absence of an introduction to prob-ability theory. There is no question that probability theory plays a crucial role incomputing, for example, in the design of randomized algorithms and in the proba-bilistic analysis of algorithms. Our feeling is that to do justice to the subject wouldrequire too much space. Unfortunately, omitting probability theory is one of thetough choices that we decided to make in order to keep the manuscript of manage-able size. Fortunately, probability and its applications to computing are presented ina beautiful book by Mitzenmacher and Upfal [4] so we don t feel too bad about ourdecision to omit these are quite a few books covering Discrete Mathematics .

10 According to mypersonal taste, I feel that two books complement and extend the material presentedhere particularly well: Discrete Mathematics , by Lov asz, Pelik an, and Vesztergombi[3], a very elegant text at a slightly higher level but still very accessible, andDiscreteMathematics, by Graham, Knuth, and Patashnik [2], a great book at a significantlyhigher unconventional approach of starting with logic may not work for everybody,as some individuals find such material too abstract. It is possible to skip the chapteron logic and proceed directly with sets, functions, and so on. I admit that I haveraised the bar perhaps higher than the average compared to other books on discretemaths. However, my experience when teaching CIS260 was that 70% of the studentsenjoyed the logic material, as it reminded them of programming.