Discrete Structures Lecture Notes - Stanford University

1 Discrete StructuresLecture NotesVladlen Koltun1 Winter 20081 Computer Science Department, 353 Serra Mall, Gates 374, Stanford University , Stanford , CA94305, Sets and Defining sets .. Set operations .. More sets ..42 Introducing induction .. Strong induction .. Why is the induction principle true? ..83 More Proof Proofs by contradiction .. Direct proofs ..124 The division algorithm .. Remainders .. Greatest common divisors .. Greatest common divisors and linear combinations.

2 185 Prime The fundamental theorem of arithmetic .. The infinity of primes ..226 Modular Congruences .. Modular division ..277 Relations and Ordered pairs .. Relations .. Kinds of relations .. Creating relations .. Functions ..358 Mathematical Propositions and predicates .. Quantifiers .. Negations .. Logical connectives .. Tautologies and logical inference ..419 Fundamental principles .. Basic counting problems ..4410 Binomial Basic properties .. Binomial theorem.

3 5011 The Inclusion-Exclusion Statement and proof of the principle .. Derangements ..5412 The Pigeonhole Statements of the principle .. Simple applications .. Advanced applications ..5813 Asymptotic Definitions .. Examples and properties ..6214 Introduction .. Common graphs .. Some important concepts .. Kinds of graphs ..6715 More Graphs Eulerian, Bipartite, and Eulerian graphs .. Graph coloring .. Bipartite graphs and matchings ..7116 Basic properties of trees .. Spanning trees.

4 7717 Planar Drawing graphs in the plane .. Euler s formula .. Coloring planar graphs .. Concluding remarks ..84iiChapter 1 Sets and Defining an unordered collection of distinct objects. The objects in aset are called theelements,ormembers,of the set. A set is said tocontainits set can be defined by simply listing its members inside curly braces. For example,the set{2,4,17,23}is the same as the set{17,4,23,2}. To denote membership weuse the symbol, as in 4 {2,4,17,23}. On the other hand, non-membership isdenoted as in 56 {2,4,17,23}.

5 If we want to specify a long sequence that follows a pattern, we can use the ellipsisnotation, meaning fill in, using the same pattern . The ellipsis is often used after twoor more members of the sequence, and before the last one, as follows:{1,2, .. , n}.The pattern denoted by the ellipsis should be apparent at first sight! For instance,{1, .. , n}is generally regarded as underspecified (that is, too ambiguous). Of course, even {1,2, .. , n}is still ambiguous did we mean all integers between 1 andn, allpowers of two up ton, or perhaps the set{1,2,25, n}?

6 But is generally sufficient,unless you really do mean all powers of two up ton, in which case{20,21,22, .. ,2k}for an appropriatekis a better choice. The ellipsis can also be used to define aninfinite set, as in the set ofnatural numbersornonnegative integers, denoted byN, isdefined as{0,1,2, ..}.To avoid ambiguities it is often useful to use theset buildernotation, which listson the right side of the colon the property that any set element, specified on the leftside of the colon, has to satisfy. Let s define the positive integers using the set buildernotation:N+={x:x Nandx >0}.

7 We can also writeN+={x N:x >0}.1 This is a matter of taste. In general, use the form that will be easiest for the readerof your work to understand. Often it is the least cluttered , now onto the integers:Z={x:x Nor x N}.Hmm, perhaps in this case it is actually better to writeZ={.. , 2, 1,0,1,2, ..}.Remember, when you write mathematics, you should keep your readers perspectivein mind. For now, we the staff of this course are your readers. In the future itmight be your colleagues, supervisors, or the readers of your published work.

8 Inaddition to being reasonably formal and unambiguous, your mathematical writingshould be as clear and understandable to your intended readership as are therational numbers:Q={ab:a Z, b Z, b6= 0}.Instead ofa Z, b Z, you can writea, b Z, which is more concise and generallymore readable. Don t go overboard, though, with writing something likea, b6= 0 Z,this is way too confusing and does not say what you want it , the set ofreal numbersis denoted byR. All the reals that are not rationalare calledirrational.

9 These include the familiar = ,e= , 2, and infinitely many others. (How do we know that these numbers are irrational,do you ask? Actually, we will see a proof of this for 2 shortly. The proofs for anderequire mathematical analysis and are outside our scope.)On being the above definitions formal enough? The answer is: itdepends. For example, defining the natural numbers is an important and non-trivialaccomplishment of mathematics. After all, what do these symbols 1 , 2 , 3 ,actuallymean? These numbers can be formally defined in terms of sets.

10 even moreinvolved is the formal definition of the reals, usually covered in a first mathematicalanalysis we cannot afford to cover everything in complete detail, which would have toinclude, among other things, basic algebra and trigonometry. Furthermore, the vastmajority of mathematical works, while considered to be formal , gloss over detailsall the time. For example, you ll be hard-pressed to find a mathematical paper thatgoes through the trouble of justifying the equationa2 b2= (a b)(a+b). In effect,every mathematical paper or Lecture assumes a shared knowledge base with its readersor listeners.