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 ..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.

2 Quantifiers .. Negations .. Logical connectives .. Tautologies and logical inference ..419 Fundamental principles .. Basic counting problems ..4410 Binomial Basic properties .. Binomial theorem ..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 ..7717 Planar Drawing graphs in the plane .. Euler s formula .. Coloring planar graphs.

3 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}.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.}

4 , 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}? 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}.

5 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. 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.

6 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. 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. 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.

7 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. It is extremely important for an author of mathematics, such as yourselfduring this course, to estimate this shared knowledge base correctly!In CS103X we will assume most of high-school mathematics, including perhapssome AP math like single-variable calculus, as our shared knowledge base. Thusnotions and techniques from this base will generally not be justified in Lecture , andcan be used freely in your homework and exams. Furthermore, once we develop certain2notation or prove some theorem in class, you can use these freely in your homeworkand exams, provided that you clearly cite the appropriate theorems.

8 In writing andspeaking mathematics, a delicate balance is maintained between being formal andnot getting bogged down in balance usually becomes second-naturewith experience. You should all get the hang of it by the end of the Set operationsAis said to be a subset ofBif and only if every element ofAis also an element ofB,in which case we writeA astrict subsetofBifAis a subset ofBandAisnot equal toB, which is denoted byA B. For example,{4,23} {2,4,17,23} {2,4,17,23}.Two setsAandBare considered equal if and only if they have the same is denoted byA=B. More formally,A=Bif and only ifA BandB two setsAandB, the operations of union, intersection, and difference aredefined as follows:A B={x:x Aorx B}A B={x:x Aandx B}A\B={x:x Aandx6 B}The and notation can be extended to the union and intersection of multiple , A2.

9 , An, we can writen i=1 Aifor their union, andn i=1 Aifor their intersection. In fact, this notation is pretty flexible and the same union canbe written asn i=1Ai= 1 i nAi= i {x: 1 x n} is another example: i {x: 1 x 10}iis primeAi=A2 A3 A5 a setA, thecardinalityofA, also known as thesizeofA, is simply the numberof elements inA. The cardinality ofAis denoted by|A|. For example, ifA={2,4,17,23}, then|A|= course, what is considered minutia differs from subfield to subfield, and from classroom More setsTheempty setis denoted by . It is the unique set without elements. It holds that Afor any setA. Why? By definition, this holds if every element of is also anelement ofA. Since has no elements, all possible statements about the elements of are true! In particular, all elements of are also elements ofA.

10 If this is confusingdon t worry, we will go into such matters more rigorously when we get to logic. (Fornow, you can ponder the following: If we know for a fact that there are no unicorns<Gasp!>, then it is definitely true that all unicorns have soft light-blue fur.)A set can contain sets as its elements. For example,{{2,4},{17},23}is a per-fectly valid set with three elements, two of them sets. (The second element isasingleton, a set with one element.) Note that{2,4} {{2,4},{17},23}, but{2,4} {2,4,17,23}, and that 176 {{2,4},{17},23}, but{17} {{2,4},{17},23}.Also,{ }isnotthe empty set. (Think about it.)Thepower setof a setAis the set of all subsets ofA, and is denoted by 2A. Thatis,2A={S:S A}.For example, forA={2,4,17,23}, we have2A={ ,{2},{4},{17},{23},{2,4},{2,17},{2,23},{ 4,17},{4,23},{17,23},{2,4,17},{2,4,23},{ 2,17,23},{4,17,23},{2,4,17,23}}.