Discrete Mathematics and Functional Programming Thomas VanDrunen June 23, 2006 Brief contents I Set 1 II Logic 33 III Proof 71 IV Algorithm 91 V Relation 127 VI Function 155 VII Program 181 VIII Graph 215 Contents Preface ix I Set 1 1 Sets and elements 3 1.1 Your mathematical biography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Reasoning about items collectively . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Intuiton about sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Set notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Expressions and Types 11 2.1 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Making your own types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Set Operations 19 3.1 Axiomatic foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Operations and visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Powersets,cartesian products, and partitions . . . . . . . . . . . . . . . . . . . . . . 22 4 Tuples and Lists 25 4.1 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3 Lists vs. tuples vs. arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 II Logic 33 5 Logical Propositions and Forms 35 5.1 Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3 Boolean values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4 Truth tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.5 Logical equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6 Conditionals 43 6.1 Conditional propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.2 Negation of a conditional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.3 Converse, inverse, and contrapositive . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.4 Writing conditionals in English . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.5 Conditional expressions in ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 7 Argument forms 49 7.1 Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2 Common syllogisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.3 Using argument forms for deduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 8 Predicates and quantifiers 55 8.1 Predication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 8.2 Universal quantification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 8.3 Existential quantification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 8.4 Implicit quantification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 8.5 Negation of quantified propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 9 Multiple quantification; representing predicates 61 9.1 Multiple quantification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 9.2 Ambiguous quantification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 9.3 Predicates in ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 9.4 Pattern-matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 III Proof 71 10 Subset proofs 73 10.1 Introductory remarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 10.2 Forms for proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 10.3 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 10.4 Closing remarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 11 Set equality and empty proofs 79 11.1 Set equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 11.2 Set emptiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 11.3 Remarks on proof by contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 12 Conditional proofs 83 12.1 Worlds of make believe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 12.2 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 12.3 Biconditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 12.4 Warnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 13 Special Topic: Russell’s paradox 89 IV Algorithm 91 14 Algorithms 93 14.1 Problem-solvingsteps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 14.2 Repetition and change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 14.3 Packagingand parameterization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 14.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 15 Induction 101 15.1 Calculating a powerset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 15.2 Proof of powerset size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 15.3 Mathematical induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 15.4 Induction gone awry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 15.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 16 Correctness of algorithms 109 16.1 Defining correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 16.2 Loop invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 16.3 Big example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 16.4 Small example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 17 From Theorems to Algorithms 115 17.1 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 17.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 17.3 The Euclidean Algorithm, another way. . . . . . . . . . . . . . . . . . . . . . . . . . 118 18 Recursive algorithms 121 18.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 18.2 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 V Relation 127 19 Relations 129 19.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 19.2 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 19.3 Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 20 Properties of relations 135 20.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 20.2 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 20.3 Equivalence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 20.4 Computing transitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 21 Closures 141 21.1 Transitive failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 21.2 Transitive and other closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 21.3 Computing the transitive closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 21.4 Relations as predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 22 Partial orders 149 22.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 22.2 Comparability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 22.3 Topological sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 VI Function 155 23 Functions 157 23.1 Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 23.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 23.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 23.4 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 24 Images 163 24.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 24.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 24.3 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 25 Function properties 167 25.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 25.2 Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 25.3 Inverse functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 26 Function composition 171 26.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 26.2 Functions as components. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 26.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 27 Special Topic: Countability 177 VII Program 181 28 Recursion Revisited 183 28.1 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 28.2 Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 29 Recursive Types 189 29.1 Datatype constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 29.2 Peano numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 29.3 Parameterized datatype constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 30 Fixed-point iteration 197 30.1 Currying. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 30.2 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 30.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 30.4 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 31 Combinatorics 205 31.1 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 31.2 Permutations and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 31.3 Computing combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 32 Special Topic: Computability 209 33 Special topic: Comparison with object-oriented programming 211 VIII Graph 215 34 Graphs 217 34.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 34.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 34.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 34.4 Game theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 35 Paths and cycles 223 35.1 Walks and paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 35.2 Circuits and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 35.3 Euler circuits and Hamiltonian cycles. . . . . . . . . . . . . . . . . . . . . . . . . . . 225 36 Isomorphisms 229 36.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 36.2 Isomorphic invariants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 36.3 The isomorphic relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 36.4 Final bow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 Preface If you have discussed your schedule this semester with anyone, you have probably been asked what discrete mathematics is—or perhaps someone has asked would could make math indiscreet. While discrete mathematics is something few people outside of mathematical fields have heard of, it is comprised of topics that are fundamental to mathematics; to gather these topics together into one courseisamorerecentphenomenoninmathematicscurriculum. Becausethesetopicsaresometimes treated separately or in various other places in an undergraduate course of study in mathematic, discrete math texts and coursesappearlike hodge-podges,and unifying themes aresometimes hard to identify. Here we will attempt to shed some light on the matter. Discrete mathematics topics include symbolic logic and proofs, including proof by induction; number theory; set theory; functions and relations on sets; graphtheory; algorithms,their analysis, and their correctness; matrices; sequences and recurrence relations; counting and combinatorics; discreteprobability;andlanguagesandautomata. Allofthesewouldbeappropriateinothercourses or in their own course. Why teach them together? For one thing, students in a field like computer science need a basic knowledge of many of these topics but do not have time to take full courses in all of them; one course that meanders through these topics is thus a practical compromise. (And no one-semester course could possibly touch all of them; we will be completely skipping matrices, probability,languages,andautomata,andnumbertheory,sequences,recurrencerelations,counting, and combinatorics will receive only passing attention.) However, all these topics do have something in common which distinguishes them from much of the rest of mathematics. Subjects like calculus, analysis, and differential equations, anything that deals with the real or complex numbers, can be put under the heading of continuous mathematics, where acontinuum of valuesis alwaysin view. In contrastto this, discrete mathematics alwayshas separable, indivisible, quantized (that is, discrete) objects in view—things like sets, integers, truth values, orverticesin a graph. Thusdiscretemath stands towardscontinuousmath in the sameway that digitaldevicesstandtowardanalog. Imaginethe difference betweenan electric stoveanda gas stove. A gas stove has a nob which in theory can be set to an infinite number of positions between high and low, but the discrete states of an electric stove are a finite, numbered set. This particular course, however, does something more. Here we also intertwine functional pro- gramming with the discrete math topics. Functional programming is a different style or paradigm from the procedural, imperative, and/or object-oriented approach that those of you who have pro- grammed before have seen (which, incidentally, should place students who have programming ex- perience and those who have not on a level playing field). Instead of viewing a computer program as a collection of commands given to a computer, we see a program as a collection of interacting functions, in the mathematical sense. Since functions are a major topic of discrete math anyway, the interplay is natural. As we shall see, functional programming is a useful forum for illustrating the other discrete math topics as well. Butlikeanycourse,especiallyataliberalartscollege,ourmaingoalistomakeyouthinkbetter. You should leave this course with a sharper understanding of categorical reasoning, the ability to analyze logic formally, an appreciation for the precision of mathematical proofs, and the clarity of thought necessary to arrange tasks into an algorithm. The slogan of this course is, “Math majors should learn to write programsand computer science majorsshould learnto write proofstogether.” Math majorswill spend most of their time as undergraduatesprovingthings, and computerscience majors will do a lot of programming; yet they both need to do a little of the other. The fact is, robust programs and correct proofs have a lot to do with each other, not the least of which is that they both require clear, logical thinking. We will see how proof techniques will allow us to check that an algorithm is correct, and that proofs can prompt algorithms. Moreover, the programming component motivates the proof-based discrete math for the computer science majors and keeps it relevant; the proof component should lighten the unfamiliarity that math majors often experience in a programmingcourse. There are three major theme pairs that run throughout this course. The theme of proof and program has already been explained. The next is symbol and representation. So much of precise mathematics relies on accurate and informative notation, and it is important to distinguish the difference between a symbol and the idea it represents. This is also a point where math and computer science streams of thought swirl; much of our programming discussions will focus on the best ways to represent mathematical concepts and structure on a computer. Finally, the theme of analysis and synthesis will recur. Analysis is the taking of something apart; synthesis is putting something together. This pattern occurs frequently in proofs. Take any proposition in the form “if q then p.” q will involve some definition that will need to be analyzed straight away to determine what is really being asserted. The proof will end by assembling the components according to the definitionsofthetermsusedinp. Likewiseinfunctionalprogramming,wewillpracticedecomposing a problem into its parts and synthesizing smaller solutions into a complete solution. Thiscoursecoversalotofmaterial,andmuchofitischallenging. However,withcarefulpractice, none of it is beyond the grasp of anyone with the mathematical maturity that is usually achieved around the time a student takes calculus. Part I Set