A Course in Discrete Structures - Cornell University

1 A Course in Discrete StructuresRafael PassWei-Lung Dustin TsengPrefaceDiscrete mathematics deals with objects that come indiscretebundles, ,1 or 2 babies. In contrast, continuous mathematics deals with objects thatvarycontinuously, , inches from a wall. Think of digital watchesversus analog watches (ones where the second hand loops around continuouslywithout stopping).Why study Discrete mathematics in computer science? It does not directlyhelp us write programs. At the same time, it is the mathematics underlyingalmost all of computer science. Here are a few examples: Designing high-speed networks and message routing paths. Finding good algorithms for sorting. Performing web searches. Analysing algorithms for correctness and efficiency. Formalizing security requirements. Designing cryptographic mathematics uses a range of techniques, some of which is sel-dom found in its continuous counterpart. This Course will roughly cover thefollowing topics and specific applications in computer Sets, functions and relations2.

2 Proof techniques and induction3. Number theorya) The math behind the RSA Crypto system4. Counting and combinatorics5. Probabilitya) Spam detectionb) Formal security6. Logica) Proofs of program correctness7. Graph theoryia) Message Routingb) Social networks8. Finite automata and regular languagesa) CompilersIn the end, we will learn to write precise mathematical statements thatcaptures what we want in each application, and learn to prove things aboutthese statements. For example, how will we formalize the infamous zero-knowledge property? How do we state, in mathematical terms, that a bankingprotocol allows a user to prove that she knows her password, without everrevealing the password itself?ContentsContentsiii1 Sets, Functions and Sets .. Relations .. Functions .. Set Cardinality, revisited ..82 Proofs and Basic Proof Techniques .. Proof by Cases and Examples.

3 Induction .. Inductive Definitions .. Fun Tidbits .. 313 Number Divisibility .. Modular Arithmetic .. Primes .. The Euler Function .. Public-Key Cryptosystems and RSA .. 564 The Product and Sum Rules .. Permutations and Combinations .. Combinatorial Identities .. Inclusion-Exclusion Principle .. Pigeonhole Principle .. 725 Probability Spaces .. Conditional Probability and Independence .. Random Variables .. Expectatation .. Variance .. 926 Propositional Logic .. Logical Inference .. First Order Logic .. Applications .. 1087 Graph Isomorphism .. Paths and Cycles .. Graph Coloring .. Random Graphs [Optional] .. 1228 Finite Deterministic Finite Automata .. Non-Deterministic Finite Automata.

4 Regular Expressions and Kleene s Theorem .. 133A Problem Problem Set A .. 137B Solutions to Problem Problem Set A .. 141 Chapter 1 Sets, Functions and Relations A happy person is not a person in a certain set of circumstances, but rather aperson with a certain set of attitudes. Hugh SetsA set is one of the most fundamental object in (Set, informal).A set is anunorderedcollections of definition is informal because we do not define what a collection is;a deeper study of sets is out of the scope of this following notations all refer to the same set:{1,2},{2,1},{1,2,1,2},{x|xis an integer,1 x 2}The last example read as the set of allxsuch thatxis an integer between 1and 2 (inclusive) .We will encounter the following sets and notations throughout the Course : ={ }, the empty set. N={0,1,2,3,..}, the non-negative integers N+={1,2,3,..}, the positive integers Z={.., 2, 1,0,1, }, the integers Q={q|q=a/b, a,b Z, b6= 0}, the rational numbers Q+={q|q Q, q >0}, the positive rationals R, the real numbers12sets, functions and relations R+, the positive realsGiven a collection of objects (a set), we may want to know how large is thecollection:Definition (Set cardinality).

5 The cardinality of a setAis the number of(distinct) objects inA, written as|A|. When|A| N(a finite integer),Ais afinite set; otherwiseAis an infinite set. We discuss the cardinality of infinitesets |{1,2,3}|=|{1,2,{1,2}}|= two collections of objects (two sets), we may want to know if theyare equal, or if one collection contains the other. These notions are formalizedas set equality and subsets:Definition (Set equality).Two setsSandTare equal, written asS=T,ifSandTcontains exactly the same elements, , for everyx,x S x (Subsets).A setSis a subset of setT, written asS T, ifevery element inSis also in T, , for everyx,x S x T. SetSis astrictsubset of T, written asS TifS T, and there exist some elementx Tsuch thatx / {1,2} {1,2,3}. {1,2} {1,2,3}. {1,2,3} {1,2,3}. {1,2,3}6 {1,2,3}. For any setS, S. For every setS6= , S. S TandT Sif and only ifS= , it is time to formalize operations on sets. Given two collection ofobjects, we may want to merge the collections (set union), identify the objectsin common (set intersection), or identify the objects unique to one collection(set difference).

6 We may also be interested in knowing all possible ways ofpicking one object from each collection (Cartesian product), or all possibleways of picking some objects from just one of the collections ( power set).Definition (Set operations).Given setsSandT, we define the SETS3 power (S) is the set of all subsets ofS. Cartesian T={(s,t)|s S,t T}. T={x|x Sorx T}, set of elements inSorT. T={x|x S,x T}, set of elements inSandT. T={x|x S,x / T}, set of elements inSbut notT. {x|x / S}, set of elements not inS. This isonly meaningful when we have an implicit universeUof objects, ,S={x|x U,x / S}.Example {1,2,3},T={3,4},V={a,b}. Then: P(T) ={ ,{3},{4},{3,4}}. S V={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}. S T={1,2,3,4}. S T={3}. S T={1,2}. If we are dealing with the set of all integers,S={.., 2, 1,0,4,5,..}.Some set operations can be visualized using Venn diagrams. See To give an example of working with these set operations, consider thefollowing set all setsSandT,S= (S T) (S T).

7 Can visualize the set identity using Venn diagrams (see Figure ). To formally prove the identity, we will show both of the following:S (S T) (S T)( )(S T) (S T) S( )To prove ( ), consider any elementx S. Eitherx Torx / T. Ifx T, thenx S T, and thus alsox (S T) (S T). Ifx / T, thenx (S T), and thus againx (S T) (S T).To prove ( ), consider anyx (S T) (S T). Eitherx S Torx S T Ifx S T, thenx S4sets, functions and relationsSTU(a)S TSTU(b)S TSTU(c)S TSTU(d)SSTV(e) Venn diagram with three : Venn diagrams of setsS,T, andVunder universeU. Ifx S T, thenx S. In computer science, we frequently use the following additional notation(these notation can be viewed as short hands):Definition a setSand a natural numbern N, Snis the set of lengthn strings (equivalentlyn-tuples) with alphabetS. Formally we define it as the product ofncopies ofS( ,S S S). S is the set of finite length strings with alphabetS. Formally wedefine it as the union ofS0 S1 S2 , whereS0is a set thatcontains only one element: the empty string (or the empty tuple () ).

8 RELATIONS5 [n] is the set{0,1,..,n 1}.Commonly seen set includes{0,1}nas the set ofn-bit strings, and{0,1} as the set of finite length bit strings. Also observe that|[n]|= we end this section, let us revisit our informal definition of sets: anunordered collection of objects. In 1901, Russel came up with the following set , known as Russel s paradox1:S={x|x / x}That is,Sis the set of all sets that don t contain themselves as an might seem like a natural collection , but isS S? It s not hard tosee thatS S S / S. The conclusion today is thatSis not a good collection of objects; it is not a how will know if{x|xsatisfies some condition}is a set? Formally, setscan be defined axiomatically, where only collections constructed from a carefullist of rules are considered sets. This is outside the scope of this Course . We willtake a short cut, and restrict our attention to a well-behaved universe. LetEbe all the objects that we are interested in (numbers, letters, etc.)

9 , and letU=E P(E) P(P(E)), ,E, subsets ofEand subsets of subsets ofE. In fact,we may extendUwith three power set operations, or indeed anyfinitenumberof power set operations. Then,S={x|x Uand some condition holds}isalways a RelationsDefinition (Relations).A relation on setsSandTis a subset ofS relation on a single setSis a subset ofS Taller-than is a relation on people; (A,B) Taller-than if personAis taller than personB. is a relation onR; ={(x,y)|x,y R, x y}.Definition (Reflexitivity, symmetry, and transitivity).A relationRonsetSis: Reflexiveif (x,x) Rfor allx S. Symmetricif whenever (x,y) R, (y,x) folklore version of this paradox concerns itself with barbers. Suppose in a town, theonly barber shaves all and only those men in town who do not shave themselves. This seemsperfectly reasonable, until we ask: Does the barber shave himself?6sets, functions and relations Transitiveif whenever (x,y),(y,z) R, then (x,z) RExample is reflexive, but < is not.

10 Sibling-of is symmetric, but and sister-of is not. sibling-of , , and < are all transitive, but parent-of is not( ancestor-of is transitive, however).Definition (Graph of relations).The graph of a relationRoverSis andirected graph with nodes corresponding to elements ofS. There is an edgefrom nodextoyif and only if (x,y) R. See Figure a relation overS. Ris reflexive iff its graph has a self-loop on every node. Ris symmetric iff in its graph, every edge goes both ways. Ris transitive iff in its graph, for any three nodesx,yandzsuch thatthere is an edge fromxtoyand fromytoz, there exist an edge fromxtoz. More naturally,Ris transitive iff in its graph, whenever there is a pathfrom nodexto nodey, there is also a direct edge proofs of the first three parts follow directly from the proof of the last bullet relies on induction; we will revisit it later. Definition (Transitive closure).The transitive closure of a relationRis the least ( , smallest) transitive relationR such thatR R.