WIXLIB

A Course in Discrete StructuresRafael PassWei-Lung Dustin Tseng

PrefaceDiscrete mathematics deals with objects that come in discrete bundles, e.g.,1 or 2 babies. In contrast, continuous mathematics deals with objects thatvary continuously, e.g., 3.42 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 protocols.Discrete mathematics uses a range of techniques, some of which is seldom found in its continuous counterpart. This course will roughly cover thefollowing topics and specific applications in computer science.1. Sets, functions and relations2. 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 theoryi

a) 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 zeroknowledge 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 Relations1.1 Sets . . . . . . . . . . . . . .1.2 Relations . . . . . . . . . . .1.3 Functions . . . . . . . . . . .1.4 Set Cardinality, revisited . . .2 Proofs and Induction2.1 Basic Proof Techniques . . .2.2 Proof by Cases and Examples2.3 Induction . . . . . . . . . . .2.4 Inductive Definitions . . . . .2.5 Fun Tidbits . . . . . . . . . .3 Number Theory3.1 Divisibility . . . . . . . .3.2 Modular Arithmetic . . .3.3 Primes . . . . . . . . . . .3.4 The Euler φ Function . .3.5 Public-Key Cryptosystems.11578.131315172631. . . . . . . . . . . . . . . . . . . . .and RSA.373741475256.616163656972.4 Counting4.1 The Product and Sum Rules . .4.2 Permutations and Combinations4.3 Combinatorial Identities . . . . .4.4 Inclusion-Exclusion Principle . .4.5 Pigeonhole Principle . . . . . . .5 Probability.73iii

5.15.25.35.45.5Probability Spaces . . . . .Conditional Probability andRandom Variables . . . . .Expectatation . . . . . . . .Variance . . . . . . . . . . .6 Logic6.1 Propositional Logic6.2 Logical Inference .6.3 First Order Logic .6.4 Applications . . . . . . . . . . .Independence. . . . . . . . . . . . . . . . . . . . . .7377858792.95951001051087 Graphs7.1 Graph Isomorphism . . . .7.2 Paths and Cycles . . . . . .7.3 Graph Coloring . . . . . . .7.4 Random Graphs [Optional].109112115120122.8 Finite Automata1258.1 Deterministic Finite Automata . . . . . . . . . . . . . . . . . . 1258.2 Non-Deterministic Finite Automata . . . . . . . . . . . . . . . 1308.3 Regular Expressions and Kleene’s Theorem . . . . . . . . . . . 133A Problem Sets137A.1 Problem Set A . . . . . . . . . . . . . . . . . . . . . . . . . . . 137B Solutions to Problem Sets141B.1 Problem Set A . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Chapter 1Sets, 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 Downs1.1SetsA set is one of the most fundamental object in mathematics.Definition 1.1 (Set, informal). A set is an unordered collections of objects.Our definition is informal because we do not define what a “collection” is;a deeper study of sets is out of the scope of this course.Example 1.2. The following notations all refer to the same set:{1, 2}, {2, 1}, {1, 2, 1, 2}, {x x is an integer, 1 x 2}The last example read as “the set of all x such that x is 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 integersN {1, 2, 3, . . . }, the positive integersZ {. . . , 2, 1, 0, 1, 2 . . . }, the integersQ {q q a/b, a, b Z, b 6 0}, the rational numbersQ {q q Q, q 0}, the positive rationalsR, the real numbers1

2sets, functions and relations R , the positive realsGiven a collection of objects (a set), we may want to know how large is thecollection:Definition 1.3 (Set cardinality). The cardinality of a set A is the number of(distinct) objects in A, written as A . When A N (a finite integer), A is afinite set; otherwise A is an infinite set. We discuss the cardinality of infinitesets later.Example 1.4. {1, 2, 3} {1, 2, {1, 2}} 3.Given 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 1.5 (Set equality). Two sets S and T are equal, written as S T ,if S and T contains exactly the same elements, i.e., for every x, x S x T .Definition 1.6 (Subsets). A set S is a subset of set T , written as S T , ifevery element in S is also in T, i.e., for every x, x S x T . Set S is astrict subset of T, written as S T if S T , and there exist some elementx T such that x / S.Example 1.7. {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 set S, S.For every set S 6 , S.S T and T S if and only if S T .Finally, 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). 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 1.8 (Set operations). Given sets S and T , we define the followingoperations:

1.1. SETS3 Power Sets. P(S) is the set of all subsets of S. Cartesian Product. S T {(s, t) s S, t T }. Union. S T {x x S or x T }, set of elements in S or T . Intersection. S T {x x S, x T }, set of elements in S and T . Difference. S T {x x S, x / T }, set of elements in S but not T . Complements. S {x x / S}, set of elements not in S. This isonly meaningful when we have an implicit universe U of objects, i.e.,S {x x U, x / S}.Example 1.9. Let S {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 Figure1.1. To give an example of working with these set operations, consider thefollowing set identity.Theorem 1.10. For all sets S and T , S (S T ) (S T ).Proof. We can visualize the set identity using Venn diagrams (see Figure 1.1band 1.1c). To formally prove the identity, we will show both of the following:S (S T ) (S T )(1.1)(S T ) (S T ) S(1.2)To prove (1.1), consider any element x S. Either x T or x / T. If x T , then x S T , and thus also x (S T ) (S T ). If x / T , then x (S T ), and thus again x (S T ) (S T ).To prove (1.2), consider any x (S T ) (S T ). Either x S T orx S T If x S T , then x S

4sets, functions and relationsUSUTS(a) S TT(b) S TUSUTS(c) S TT(d) SVST(e) Venn diagram with three sets.Figure 1.1: Venn diagrams of sets S, T , and V under universe U. If x S T , then x S. In computer science, we frequently use the following additional notation(these notation can be viewed as short hands):Definition 1.11. Given a set S and a natural number n N, S n is the set of length n “strings” (equivalently n-tuples) with alphabetS. Formally we define it as the product of n copies of S (i.e., S S · · · S). S is the set of finite length “strings” with alphabet S. Formally wedefine it as the union of S 0 S 1 S 2 · · · , where S 0 is a set thatcontains only one element: the empty string (or the empty tuple “()”).

1.2. RELATIONS5 [n] is the set {0, 1, . . . , n 1}.Commonly seen set includes {0, 1}n as the set of n-bit strings, and {0, 1} as the set of finite length bit strings. Also observe that [n] n.Before 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, S is the set of all sets that don’t contain themselves as an element.This might seem like a natural “collection”, but is S S? It’s not hard tosee that S S S / S. The conclusion today is that S is not a good“collection” of objects; it is not a set.So how will know if {x x satisfies 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. Let Ebe all the objects that we are interested in (numbers, letters, etc.), and let U E P(E) P(P(E)), i.e., E, subsets of E and subsets of subsets of E. In fact,we may extend U with three power set operations, or indeed any finite numberof power set operations. Then, S {x x U and some condition holds} isalways a set.1.2RelationsDefinition 1.12 (Relations). A relation on sets S and T is a subset of S T .A relation on a single set S is a subset of S S.Example 1.13. “Taller-than” is a relation on people; (A, B) ”Taller-than”if person A is taller than person B. “ ” is a relation on R; “ ” {(x, y) x, y R, x y}.Definition 1.14 (Reflexitivity, symmetry, and transitivity). A relation R onset S is: Reflexive if (x, x) R for all x S. Symmetric if whenever (x, y) R, (y, x) R.1A 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?