Discrete Mathematics An Open Introduction PDF

Discrete Mathematics An Open Introduction, 4th edition Discrete Mathematics An Open Introduction Oscar Levin 4th Edition Oscar Levin School of Mathematical Science University of Northern Colorado Greeley, Co 80639 [email protected] http://math.oscarlevin.com/ © 2013-2024 by Oscar Levin This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/4.0/. 4th Edition A current version can always be found for free at http://discrete.openmathbooks.org/ Cover image: Tiling with Fibonacci and Pascal. For Madeline and Teagan Acknowledgements This book would not exist if not for “Discrete and Combinatorial Mathematics” by Richard Grassl and Tabitha Mingus. It is the book I learned discrete math out of, and what taught with the semester before I began writing this text. I wanted to maintain the inquiry-based feel of their book but update, expand and rearrange some of the material. Some of the best exposition and exercises here were graciously donated from this source. Thanks to the graduate students who have co-taught the Discrete Mathematics course with me over the years, including Evan Czysz, Alees Lee, and Sarah Sparks, who helped develop new activities and exercises that have been incorporated into this text. Michelle Morgan provided copy-editing support and Jennifer Zakotnik- Gutierrez helped code many of the interactive exercises in the online version of the book. Thanks also to Katie Morrison, Nate Eldredge, and Richard Grassl (again) for their suggestions after using parts of this text in their classes. The online version of the book is written in PreTeXt and hosted on Runestone Academy thanks to the tremendous development work of Rob Beezer, Brad Miller, David Farmer, and Alex Jordan along with the rest of the participants of the pretext-support group1. Finally, a thank you to the numerous students who have pointed out typos and made suggestions over the years, and a thanks in advance to those who will do so in the future. 1 groups.google.com/g/pretext-support vii Preface This text aims to introduce select topics in discrete mathematics at a level appropriate for first or second-year undergraduate math and computer science majors, especially those who intend to teach middle and high school mathematics. The book began as a set of notes for the Discrete Mathematics course at the University of Northern Colorado. This course serves both as a survey of the topics in discrete math and as the “bridge” course for math majors, as UNC does not offer a separate “introduction to proofs” course. As this course has evolved to support our computer science major, so has the text. The current version of the book is intended to support inquiry-based teaching for understanding that is so crucial for future teachers, while also providing the necessary mathematical foundation and application-based motivation for computer science students. While teaching the course in Spring 2024 using an early version of this edition, I was pleasantly surprised by how many students reported that they, for the first time, saw how useful math could be in the “real world.” I hope that this experience can be replicated in other classes using this text. This book is intended to be used in a class taught using problem-oriented or inquiry-based methods. Each section begins with a preview of the content that includes an open-ended Investigate! motivating question, as well as a structured preview activity. The preview activities are carefully scaffolded to provide an entry-point to the section’s topic and prime students to engage deeply in the material. Depending on the pace of the class, I have found success assigning only the section preview before class, using the preview activity as in-class group work, or assigning the entire section to be read before class (each section concludes with a small set of reading questions that can be assigned to encourage students to actually read). For those readers using this book for self-study, the organization of the sections will hopefully mimic the style of a rich inquiry-based classroom. The topics covered in this text were chosen to match the needs of the students I teach at UNC. The main areas of study are logic and proof, graph theory, combina- torics, and sequences. Induction is covered at the end of the chapter on sequences. Discrete structures are introduced “as needed”, but a more thorough treatment of sets and functions is included as a separate chapter, which can be studied in- dependent of the other content. Then final chapter covers two additional topics: generating functions and number theory. While I believe this selection and order of topics is optimal, you should feel free to skip around to what interests you. There are occasionally examples and exercises that rely on earlier material, but I have tried to keep these to a minimum and usually can either be skipped or understood without too much additional study. If you are an instructor, you can also create a custom version by editing the PreTeXt source to fit your needs. ix x Improvements to the 4th Edition. Many of the sections have been rewritten to improve the clarity of the exposition. Nearly 300 new exercises, bringing the total to more than 750. These are better divided into preview activity questions, reading questions, practice problems, and additional exercises. Most of the new exercises are interactive for the online version. New sections on probability, relations, and discrete structures and their proofs. Some other sections have been split up to make it more likely that a single class period can be devoted to a single topic. Improved presentation for the counting chapter with a focus on considering sets of outcomes more than following rules. The Investigate! activities of the 3rd edition have been split up into two types: Investigate! questions and Preview Activities. The former are open-ended questions designed to engage you with the topic soon to be discussed. The latter are structured preview activities that you should be able to completely answer before reading the section. The previous editions (3rd edition, released in 2019, 2nd edition, released in 2016, and the Fall 2015 edition) will still be available for instructors who wish to use those versions due to familiarity. I plan to continue improving the book. Some of this will happen in real-time by updating the online versions to include new content (numbering will remain consistent). Thus I encourage you to send along any suggestions and comments as you have them. Oscar Levin, Ph.D. University of Northern Colorado, 2024 How to use this book In addition to expository text, this book has a few features designed to encourage you to interact with the mathematics. Investigate! questions. Sprinkled throughout the sections (usually at the very beginning of a topic) you will find open-ended questions designed to engage you with the topic soon to be discussed. You really should spend some time thinking about, or even working through, these problems before reading the section. However, don’t worry if you cannot find a satisfying solution right away. The goal is to pique your interest so you will read what is next looking for answers. Preview Activities. Most sections include a structured preview activity. These contain leading questions that you should be able to completely answer before reading the section. The idea is that the questions prime you to engage meaningfully with the new content ahead. If you are using the online version, most of these questions will provide you w immediate feedback so you can be confident moving forward. Examples. I have tried to include the “correct” number of examples. For those examples that include problems, full solutions are included. Before reading the solution, try to at least have an understanding of what the problem is asking. Unlike some textbooks, the examples are not meant to be all-inclusive for problems you will see in the exercises. They should not be used as a blueprint for solving other problems. Instead, use the examples to deepen our understanding of the concepts and techniques discussed in each section. Then use this understanding to solve the exercises at the end of each section. Exercises. You get good at math through practice. Each section concludes with practice problems meant to solidify concepts and basic skills presented in that section; the online version provides immediate feedback on these problems. There are then additional exercises that are more challenging and open-ended. These might be assigned as written homework or used in class as group work. Some of the additional exercises have hints or solutions in the back of the book, but use these as little as possible. Struggle is good for you. At the end of each chapter, a larger collection of similar exercises is included (as a sort of “chapter review”) which might bridge the material of different sections in that chapter. Interactive Online Version. For those of you reading this in print or as a PDF, I encourage you to also check out the interactive online version. Many of the preview activities and exercises are interactive and can give you immediate feedback. Some of xi xii these have randomized components, allowing you to practice many similar versions of the same problems until you master the topic. Hints and solutions to examples are also hidden away behind an extra click to encourage you to think about the problem before reading the solution. There is a good search feature available as well, and the index has expandable links to see the content without jumping to the page immediately. There is also a python scratch pad (the pencil icon) so you can try out some code if you feel so inclined. Additional interactivity is planned. These “bonus” features will be added on a rolling basis, so keep an eye out! You can view the interactive version for free at discrete.openmathbooks.org or by scanning the QR code below. Contents Acknowledgements vii Preface ix How to use this book xi 0 Introduction and Preliminaries 1 0.1 What is Discrete Mathematics?............... 1 Reading Questions..................... 4 0.2 Discrete Structures.................... 5 0.2.1 Introduction..................... 5 0.2.2 Sets........................ 5 0.2.3 Functions...................... 6 0.2.4 Sequences...................... 8 0.2.5 Relations...................... 9 0.2.6 Graphs....................... 10 0.2.7 Even More Structures................. 10 0.2.8 Reading Questions.................. 11 1 Logic and Proofs 13 1.1 Mathematical Statements.................. 13 1.1.1 Section Preview................... 14 1.1.2 Atomic and Molecular Statements............ 17 1.1.3 Quantifiers and Predicates............... 22 1.1.4 Reading Questions.................. 25 1.1.5 Practice Problems................... 26 1.1.6 Additional Exercises................. 28 1.2 Implications....................... 30 1.2.1 Section Preview................... 30 1.2.2 Understanding the Truth Table............. 32 1.2.3 Related Statements.................. 35 1.2.4 Reading Questions.................. 40 1.2.5 Practice Problems................... 40 1.2.6 Additional Exercises................. 42 1.3 Rules of Logic...................... 44 1.3.1 Section Preview................... 44 1.3.2 Truth Tables..................... 46 1.3.3 Logical Equivalence.................. 48 xiii xiv Contents 1.3.4 Equivalence for Quantified Statements.......... 51 1.3.5 Deductions..................... 55 1.3.6 Reading Questions.................. 57 1.3.7 Practice Problems................... 57 1.3.8 Additional Exercises................. 58 1.4 Proofs......................... 62 1.4.1 Section Preview................... 62 1.4.2 Direct Proof..................... 64 1.4.3 Proof by Contrapositive................ 69 1.4.4 Proof by Contradiction................ 71 1.4.5 Summary of Proof Styles................ 74 1.4.6 Reading Questions.................. 76 1.4.7 Practice Problems................... 77 1.4.8 Additional Exercises................. 79 1.5 Proofs about Discrete Structures............... 83 1.5.1 Section Preview................... 83 1.5.2 Proofs about sets................... 85 1.5.3 Proofs about functions................. 87 1.5.4 Proofs about relations................. 89 1.5.5 Proofs about graphs.................. 90 1.5.6 Reading Questions.................. 92 1.5.7 Practice Problems................... 92 1.5.8 Additional Exercises................. 94 1.6 Chapter Summary.................... 96 Chapter Review...................... 97 2 Graph Theory 99 2.1 Problems and Definitions.................. 99 2.1.1 Section Preview................... 100 2.1.2 What is a Graph?................... 102 2.1.3 Reading Questions.................. 111 2.1.4 Practice Problems................... 111 2.1.5 Additional Exercises................. 113 2.2 Trees.......................... 117 2.2.1 Section Preview................... 117 2.2.2 Properties of Trees.................. 119 2.2.3 Spanning Trees.................... 122 2.2.4 Rooted Trees.................... 123 2.2.5 Reading Questions.................. 125 2.2.6 Practice Problems................... 125 2.2.7 Additional Exercises................. 126 Contents xv 2.3 Planar Graphs...................... 129 2.3.1 Section Preview................... 129 2.3.2 Euler’s formula for planar graphs............ 131 2.3.3 Non-planar Graphs.................. 132 2.3.4 Polyhedra...................... 134 2.3.5 Reading Questions.................. 137 2.3.6 Practice Problems................... 137 2.3.7 Additional Exercises................. 138 2.4 Euler Trails and Circuits.................. 141 2.4.1 Section Preview................... 141 2.4.2 Conditions for Euler Trials............... 143 2.4.3 Hamilton Paths................... 144 2.4.4 Reading Questions.................. 145 2.4.5 Practice Problems................... 146 2.4.6 Additional Exercises................. 147 2.5 Coloring........................ 150 2.5.1 Section Preview................... 150 2.5.2 Coloring Vertices................... 152 2.5.3 Coloring Edges................... 157 2.5.4 Reading Questions.................. 158 2.5.5 Practice Problems................... 158 2.5.6 Additional Exercises................. 159 2.6 Relations and Graphs................... 163 2.6.1 Section Preview................... 163 2.6.2 Relations Generally.................. 165 2.6.3 Properties of Relations................. 170 2.6.4 Equivalence Relations................. 172 2.6.5 Equivalence Classes and Partitions............ 174 2.6.6 Reading Questions.................. 177 2.6.7 Practice Problems................... 177 2.6.8 Additional Exercises................. 179 2.7 Matching in Bipartite Graphs................ 181 Exercises......................... 183 2.8 Chapter Summary.................... 186 Chapter Review...................... 186 3 Counting 191 3.1 Pascal’s Arithmetical Triangle................ 191 3.1.1 Section Preview................... 192 3.1.2 Lattice Paths..................... 195 3.1.3 Bit Strings...................... 197 3.1.4 Subsets and Pizzas.................. 199 3.1.5 Algebra?...................... 201 3.1.6 Reading Questions.................. 202 xvi Contents 3.1.7 Practice Problems................... 203 3.1.8 Additional Exercises................. 204 3.2 Combining Outcomes................... 205 3.2.1 Section Preview................... 205 3.2.2 What are Outcomes?.................. 206 3.2.3 The Sum and Product Principles............. 207 3.2.4 Combining principles................. 213 3.2.5 Reading Questions.................. 215 3.2.6 Practice Problems................... 215 3.2.7 Additional Exercises................. 217 3.3 Non-Disjoint Outcomes.................. 218 3.3.1 Section Preview................... 218 3.3.2 Counting with Venn Diagrams............. 219 3.3.3 The Principle of Inclusion/Exclusion........... 222 3.3.4 Overlaps and the Product Principle........... 225 3.3.5 Reading Questions.................. 226 3.3.6 Practice Problems................... 227 3.3.7 Additional Exercises................. 228 3.4 Combinations and Permutations............... 230 3.4.1 Section Preview................... 230 3.4.2 Counting Sequences................. 232 3.4.3 Counting Sets.................... 234 3.4.4 The Quotient Principle................. 239 3.4.5 Reading Questions.................. 241 3.4.6 Practice Problems................... 241 3.4.7 Additional Exercises................. 243 3.5 Counting Multisets.................... 244 3.5.1 Section Preview................... 244 3.5.2 Have some cookies.................. 246 3.5.3 Representing multisets with bit strings.......... 249 3.5.4 Reading Questions.................. 252 3.5.5 Practice Problems................... 253 3.5.6 Additional Exercises................. 254 3.6 Combinatorial Proofs................... 256 3.6.1 Section Preview................... 256 3.6.2 Patterns in Pascal’s Triangle............... 258 3.6.3 More Proofs..................... 262 3.6.4 Reading Questions.................. 267 3.6.5 Practice Problems................... 267 3.6.6 Additional Exercises................. 268 3.7 Applications to Probability................. 273 3.7.1 Section Preview................... 273 3.7.2 Computing Probabilities................ 275 3.7.3 Probability Rules................... 278 3.7.4 Conditional Probability................ 283 Contents xvii 3.7.5 Reading Questions.................. 285 3.7.6 Practice Problems................... 286 3.7.7 Additional Exercises................. 288 3.8 Advanced Counting Using PIE............... 290 3.8.1 Section Preview................... 290 3.8.2 PIE for multisets................... 291 3.8.3 Counting Derangements................ 295 3.8.4 Counting Functions.................. 296 3.8.5 Practice Problems................... 302 3.8.6 Additional Exercises................. 304 3.9 Chapter Summary.................... 305 Chapter Review...................... 306 4 Sequences 311 4.1 Describing Sequences................... 311 4.1.1 Section Preview................... 311 4.1.2 Sequences and Formulas................ 313 4.1.3 Partial Sums and Differences.............. 319 4.1.4 Sequences in python................. 322 4.1.5 Reading Questions.................. 323 4.1.6 Practice Problems................... 323 4.1.7 Additional Exercises................. 324 4.2 Rate of Growth...................... 327 4.2.1 Section Preview................... 327 4.2.2 Arithmetic Sequences................. 328 4.2.3 Geometric Sequences................. 330 4.2.4 Beyond Arithmetic and Geometric Sequences....... 332 4.2.5 Reading Questions.................. 334 4.2.6 Practice Problems................... 334 4.2.7 Additional Exercises................. 335 4.3 Polynomial Sequences................... 338 4.3.1 Section Preview................... 338 4.3.2 Summing Arithmetic Sequences: Reverse and Add..... 340 4.3.3 Higher Degree Polynomials............... 342 4.3.4 Solving Systems of Equations with Technology....... 347 4.3.5 Reading Questions.................. 348 4.3.6 Practice Problems................... 349 4.3.7 Additional Exercises................. 350 4.4 Exponential Sequences................... 353 4.4.1 Section Preview................... 353 4.4.2 Summing Geometric Sequences: Multiply, Shift and Subtract. 354 4.4.3 The Characteristic Root Technique............ 356 4.4.4 Reading Questions.................. 359 4.4.5 Practice Problems................... 360 xviii Contents 4.4.6 Additional Exercises................. 360 4.5 Proof by Induction.................... 363 4.5.1 Section Preview................... 363 4.5.2 Recursive Reasoning................. 364 4.5.3 Formalizing Proofs.................. 364 4.5.4 Examples...................... 366 4.5.5 Reading Questions.................. 369 4.5.6 Practice Problems................... 370 4.5.7 Additional Exercises................. 373 4.6 Strong Induction..................... 377 4.6.1 Section Preview................... 377 4.6.2 Divide and conquer.................. 379 4.6.3 Reading Questions.................. 381 4.6.4 Practice Problems................... 381 4.6.5 Additional Exercises................. 382 4.7 Chapter Summary.................... 385 Chapter Review...................... 386 5 Discrete Structures Revisited 389 5.1 Sets.......................... 389 5.1.1 Notation...................... 389 5.1.2 Relationships Between Sets............... 393 5.1.3 Operations On Sets.................. 395 5.1.4 Venn Diagrams................... 398 5.1.5 Exercises...................... 399 5.2 Functions........................ 403 5.2.1 Describing Functions................. 404 5.2.2 Surjections, Injections, and Bĳections........... 409 5.2.3 Image and Inverse Image................ 411 5.2.4 Exercises...................... 414 6 Additional Topics 421 6.1 Generating Functions................... 421 6.1.1 Building Generating Functions............. 422 6.1.2 Differencing..................... 424 6.1.3 Multiplication and Partial Sums............. 427 6.1.4 Solving Recurrence Relations with Generating Functions... 428 6.1.5 Exercises...................... 429 6.2 Introduction to Number Theory............... 432 6.2.1 Divisibility..................... 432 6.2.2 Remainder Classes.................. 435 6.2.3 Properties of Congruence............... 437 6.2.4 Solving Congruences................. 441 6.2.5 Solving Linear Diophantine Equations.......... 443 Contents xix 6.2.6 Exercises...................... 447 Appendices A Selected Hints 449 B Selected Solutions 459 C List of Symbols 517 Back Matter Index 519 Chapter 0 Introduction and Preliminaries Welcome to Discrete Mathematics. If this is your first time encountering the subject, you will probably find discrete mathematics quite different from other math subjects. You might not even know what discrete math is! Hopefully this short introduction will shed some light on what the subject is about and what you can expect as you move forward in your studies. 0.1 What is Discrete Mathematics? dis·crete / dis’krët. Adjective: Individually separate and distinct. Synonyms: separate - detached - distinct - abstract. Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics? The study of numbers? In part yes, but you also study functions and lines and triangles and parallelepipeds and vectors and.... Or perhaps you want to say that mathematics is a collection of tools that allow you to solve problems. What sort of problems? Well, those that involve numbers, functions, lines, triangles,.... Whatever your conception of what mathematics is, try applying the concept of “discrete” to it, as defined above. Some math fundamentally deals with stuff that is individually separate and distinct. In an algebra or calculus class, you might have found a particular set of numbers (perhaps they constitute the range of a function). You would represent this set as an interval: [0, ∞) is the range of 𝑓 (𝑥) = 𝑥 2 since the set of outputs of the function are all real numbers 0 and greater. This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them that are also in the set. Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function that gives the number of children of each person reading this. What is the range? I’m guessing it is something like {0, 1, 2, 3, 4}. Maybe 5 or 6 is in there too.1 But certainly nobody reading this has 1.32419 children. This output set is discrete because the elements are separate. The inputs to the function also form a discrete set because each input is an individual person. There are many discrete mathematical objects besides sets of numbers; we will introduce some of these in Section 0.2. Studying these discrete structures is the main 1 Even larger natural numbers for old ladies who live in shoes. 1 2 0. Introduction and Preliminaries focus of discrete mathematics and this book. However, the reason we want to study these structures is because they provide a way to model “real-world” problems.2 To get a feel for the subject, let’s consider the types of problems you solve in discrete math. Here are a few simple examples: Investigate! Note: Throughout the book you will see Investigate! activities like this one. Answer the questions in these as best you can to give yourself a feel for what is coming next. 1. The most popular mathematician in the world is throwing a party for all of his friends. To kick things off, they decide that everyone should shake hands. Assuming all 10 people at the party each shake hands with every other person (but not themselves, obviously) exactly once, how many handshakes take place? 2. At the warm-up event for Oscar’s All-Star Hot Dog Eating Contest, Al ate one hot dog. Bob then showed him up by eating three hot dogs. Not to be outdone, Carl ate five. This continued with each contestant eating two more hot dogs than the previous contestant. How many hot dogs did Zeno (the 26th and final contestant) eat? How many hot dogs were eaten in total? 3. After excavating for weeks, you finally arrive at the burial chamber. The room is empty except for two large chests. On each is carved a message (strangely in English): Exactly one of these For either chest, if the chests contains a trea- chest’s message is true, sure, while the other is then the chest contains filled with deadly im- treasure. mortal scorpions. The problem is, you don’t know whether the messages are true or false. What do you do? 4. Back in the days of yore, five small towns decided they wanted to build roads directly connecting each pair of towns. While the towns had plenty of money to build roads as long and as winding as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed, for moral reasons. Is it possible for each of these towns to build a road to each of the four other towns without creating any intersections? 2 Many of the problems discussed in this book are admittedly contrived and clearly fictional, but hopefully you will see how these toy problems can be generalized to actually represent problems that people would care about in reality. 0.1. What is Discrete Mathematics? 3 As you consider the problems above, don’t worry if it is not obvious to you what the solutions are. We are more interested here in what sort of information we need to be able to answer the questions. How can we represent the situation using individually separate and distinct objects? Don’t read on until you have thought about at least this for each of the questions. Ready? Here are some things you might have thought about: 1. The people at the party are individuals. We can consider the set of people. We can also consider sets of pairs of people, since it takes exactly two people to shake hands. So the question is really about, how many pairs can you make using elements from a 10-element set? For example, if there were three people at the party, conveniently named 1, 2, and 3, then the pairs would be (1, 2), (1, 3), and (2, 3). Or should we include (2, 1), (3, 1), and (3, 2) as well? 2. To count the number of hot dogs eaten, either by an individual or in total, we could use a sequence of integers (whole numbers). The 𝑛th term in the sequence might represent the number of hot dogs eaten by the 𝑛th contestant. We can consider a second sequence, also of integers, that gives the total number of hot dogs eaten by the first 𝑛 contestants combined. The solution to the problem will then be the value of the 26th term in the sequence. To help us find this, we could consider the rate of growth of the sequences, as well as how these two sequences relate to each other. 3. Logic questions also belong under the discrete math umbrella: each statement can have a value of True or False (and there is nothing in-between). To answer questions like that of the chests of scorpions, we must understand the structure of the statements, and how the truth values of the parts of the statements interact to determine the truth value of the whole statement. 4. The last question is about a discrete structure called a graph, not to be confused with a graph of a function or set of points. We can use a graph to represent which elements of a set (or towns) are related to each other (or connected by a road). In this case, the question becomes, can we draw a graph with five vertices (towns) and ten edges (roads) such that no two edges intersect? The four problems above illustrate the four main topics of this book: combina- torics (the theory of ways things combine; in particular, how to count these ways), sequences, symbolic logic, and graph theory. However, there are other topics that are also considered part of discrete mathematics, including computer science, abstract algebra, number theory, game theory, probability, and geometry (some of these, particularly the last two, have both discrete and non-discrete variants). Ultimately the best way to learn what discrete math is about is to do it. Let’s get started! Before we can begin answering more complicated (and fun) problems, we will consider a very brief overview of the types of discrete structures we will be using. 4 0. Introduction and Preliminaries Reading Questions Each section of the book will end with a small number of Reading Questions like the ones below. These are designed to help you reflect on what you have read. In particular, the final reading question asks you to ask a question of your own. Thinking about what you don’t yet know is a wonderful way to further your understanding of what you do. 1. Right now, how would you describe what discrete mathematics is about, if you were telling your friends about the class you are in? Write one or two sentences. 2. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about. 0.2 Discrete Structures 0.2.1 Introduction Investigate! A double-six domino set consists of tiles containing pairs of numbers, each from 0 to 6. How many tiles are in a double-six domino set? How many dominoes are in a double-nine domino set? How many dominoes are in a double-𝑛 domino set? Try it 0.2.1 Spend a few minutes thinking about the questions above. Then write 2-3 sentences describing your thoughts. You do not need to find a complete solution, but you should describe what you could try and what you think you might need to do to find a solution. We are taking a problem-solving approach to discrete mathematics: we will consider a large variety of questions that have a discrete feel to them, and consider how to answer those questions (and prove that our answers are correct). This is not the only way to study discrete math. Another approach would be to study the tools used to solve the problems. If we were art students, we could study paintbrushes and easels and the composition of paint, which would be interesting for sure, but I think it is more enjoyable to actually paint those happy little trees. That said, understanding your tools does help you use them, so in this section, we will consider some basic tools used in discrete mathematics. We will come back to these throughout our studies and understand them better as we need to. The tools in our subject are called discrete structures. They are the mathematical objects that we use to represent parts of the problems we are solving. “Structure” is a good word here, since these “things” have fairly rigid constraints that make them what they are, just like an apartment building is going to have different characteristics than an airplane hangar or a suspension bridge (these types of physical structures, not mathematical structures, just to be overly clear and destroy the metaphor). The structures we will use most in discrete math are sets, functions, sequences, relations, and graphs. We now briefly preview each of these. As we progress through our studies, each will be explored in more detail. 0.2.2 Sets A set is an unordered collection of elements. This is fairly vague, but unless we want to spend a whole book trying to understand sets more precisely, it will be good enough for us. It is possible to define all of mathematics using just sets (even numbers can be thought of as sets themselves), but this is also not what we will do. 5 6 0. Introduction and Preliminaries Rather, we want to be able to talk about collections of numbers and other objects, and we will collect them in something we call a set. We can describe sets by saying exactly what elements are members of the set. We could specify this membership in words (e.g., Let 𝐴 be the set of all natural numbers less than 10), or by explicitly listing all the elements (e.g., 𝐴 = {3, 5, 7}), or using something called set comprehension (also called set builder notation). An example of this is 𝐴 = {𝑥 ∈ ℕ : 𝑥 < 10}. We would read that as “𝐴 is the set of natural numbers that satisfy the property that they are less than 10.” More precisely, the ℕ symbol represents the natural numbers, which is itself a set: ℕ = {0, 1, 2, 3,...} (this shows another way to describe a set). The ∈ symbol means “is an element of”. The : is read “such that” and tells us that what comes next is the condition that must be true of the set’s elements. By the way... In this book, we define the natural numbers to be the whole numbers starting with 0. Not every book includes 0 in this set. It largely depends on what area of mathematics you study. Since there are multiple ways to describe the same set, we should be careful about what it means for sets to be the same or different. A set is determined by its membership, so all four of the following describe exactly the same set: 1. {1, 2, 3, 4}. 2. {1, 2, 1 + 1, 1 + 2, 2 + 2}. (How many numbers belong to this set? It’s not 5.) 3. {2, 4, 1, 3}. (All that matters is what elements are in the collection, not what order they were written down in.) 4. {𝑥 ∈ ℕ : 𝑥 < 5 and 𝑥 ≥ 1}. There are lots of things you can do with sets, which we will consider in more detail as we need to. We will see that it is often helpful to build new sets from ones we already have (by taking the union or intersection of sets, for example), to compare sets (asking if one set is a subset of another), and to find the number of elements of a set (called its cardinality). We might also want to match up elements of one set with another: to do this, we might use a function, which we will discuss next. Awesomely, we can also use sets themselves to describe functions. Let’s check it out. 0.2.3 Functions One way to define a function is as a rule that assigns each input exactly one output. The output is called the image of the input. Functions also come equipped with a domain, the set of all inputs, and codomain, the set of all allowable outputs. You might also speak of the range of the function, which is the set of all actual outputs, or put another way, the set of all images of elements from the domain. 0.2. Discrete Structures 7 We write 𝑓 : 𝑋 → 𝑌 to describe a function with name 𝑓 , domain 𝑋 and codomain 𝑌. This does not tell us which function 𝑓 is though. To define the function, we must describe the rule. Often this is done with a formula (for example, 𝑓 (𝑥) = 𝑥 2 says that each element of the domain is mapped to its square), or in words (like how we just described the squaring function). We could also define a function with a table or a graph. The key thing that makes a rule a function is that there is exactly one output for each input. That is, the rule must be a good rule. What output do we assign to the input 7? There can only be one answer for any particular function. Since a function maps one set (the domain) to another set (the codomain), there is an obvious connection between sets and functions. There is another connection worth considering though: the graph of a function is often described as a set of points. Here is an example. Example 0.2.2 Consider the function 𝑓 : {1, 2, 3} → {2, 4, 6} defined by 𝑓 (𝑥) = 2𝑥. If we wanted to plot a graph of this function, we would draw the points (1, 2), (2, 4), and (3, 6) (but we would not connect these points with lines, since we are studying discrete math; the domain only contains three elements, not the infinitely many between them). So associated with the function is the set of points {(1, 2), (2, 4), (3, 6)}. In fact, this set of points is associated exactly with this (and only this) function. So we can think of this set of points as the function itself. Of course, we are using a mathematical object here: an ordered pair. This is not a set (since sets are unordered). How should we talk about ordered things? We will take this question up in the next section. There is one more important consideration about how we define a function with a rule. A closed formula is one in which each output is given by an explicit rule based solely on its input. This is what most of us think of as a formula. For example, 𝑓 (𝑛) = 3𝑛 + 1 is a closed formula, since to find 𝑓 (5) (say) we take the input 5 and do something to it: multiply it by 5 and then add 1. What else could a formula possibly be? A recursive definition of a function tells us how to compute the output for a given input based on other outputs of the function. For example, we might insist that 𝑓 (𝑛) = 2 · 𝑓 (𝑛 − 1). If we also specify an initial condition that 𝑓 (0) = 3, then we can find 𝑓 (1) = 2 · 3 = 6, and then 𝑓 (2) = 2 · 6 = 12, and so on. What is 𝑓 (5) here? The only way to answer that is to find 𝑓 (4), which means we need to find 𝑓 (3), which we could do, since we have computed 𝑓 (2). Recursive definitions of functions might be less useful for finding a particular output, but they are often easier to specify for a particular application. We will explore this phenomenon more when we study sequences. Speaking of which... 8 0. Introduction and Preliminaries 0.2.4 Sequences Sometimes we are interested not just in a collection of numbers, but in what order those numbers appear. In such cases, we cannot use sets, since they do not distinguish between the order of their elements. Instead, we consider sequences. We will consider both finite and infinite sequences. A finite sequence may be something as simple as (1, 2, 3); that is a sequence with 3 elements, in that particular order. We might also call this an ordered triple, the same way that (7, 3) is an ordered pair. In general, we could call this an 𝑛-tuple if it has 𝑛 elements (we assume that tuples are ordered). The key difference between the sequence (1, 2, 3) and the set {1, 2, 3} is that we “care” about the order. That is, the sequence (1, 2, 3) is different from the sequence (2, 3, 1), while the set {1, 2, 3} is identical to {2, 3, 1}. We will often use sequences as a counting tool. For example, a very simple counting question is, “how many wheels do 100 cars have?” Instead of answering just this one question, we could generalize and ask how many wheels 𝑛 cars have, and get a sequence of answers. This yields the infinite sequence (4, 8, 12,...). The order these multiples of 4 appear in is important, since each number in the sequence corresponds to a specific version of the question. It is fine to think of a sequence of numbers as an ordered list. We can refer to the terms simply as 𝑎0 , 𝑎1 , 𝑎2 ,... and might refer to the entire sequence as (𝑎 𝑛 )𝑛≥0 or (𝑎 𝑛 )𝑛∈ℕ. If we want to be a little more precise and more abstract, we can think of a sequence as a function. The domain is the natural numbers or some subset of consecutive natural numbers (like {1, 2, 3, 4}). The codomain is some set. We think of the domain as the positions in the sequence, and the image of those inputs as the terms in the sequence. For example, we might consider the Fibonacci sequence ( 𝑓𝑛 )𝑛≥1 , which starts 1, 1, 2, 3, 5, 8,.... What is the 4th term in the sequence? We might say 𝑓4 = 3 (this is assuming the first 1 is the first term and not the 0th term). Note that there can only be one 4th term. There can only be one 𝑛-th term for any particular value of 𝑛. So for any input (the position of the term), there is only one output (the term). It would be perfectly reasonable to write 𝑓 (4) = 3, and that really does look like a function. But we like to use subscripts. We can also describe the terms in a sequence using a table. We might write something like the following: 𝑛 1 2 3 4... 𝑎𝑛 1 3 6 10... This looks exactly like how you would represent a function, even though this table describes the sequence of triangular numbers (we will see why they are called this later). Since sequences are functions, we can use any of the techniques to describe functions to describe sequences. In particular, we might give a closed formula for a 0.2. Discrete Structures 9 sequence by explicitly giving the function for the 𝑛-th term. For example, 𝑛(𝑛 + 1) 𝑎𝑛 =. 2 Alternatively, we could define a sequence recursively by saying how to get from one term to the next. This is especially useful for the Fibonacci sequence: 𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−2 ; 𝑓1 = 1, 𝑓2 = 1. Much of our effort in understanding sequences will go into taking a recursive definition and finding a closed formula for the sequence. We will study this, and everything else sequence related in Chapter 4. 0.2.5 Relations How are the numbers 2 and 6 related? Oh, I know: 2 < 6. Also, 6 is a multiple of 2. The two numbers are also both even. And here is another fact: they are not equal. All four of these are examples of relations: less than, multiple of, both even, not equal. And there are many more (infinitely many) relations that might or might not hold of a pair of two numbers. The examples above are all binary relations in that they relate two elements. You could also consider relations between more than two elements. For example, we could consider the relation “Pythagorean triple” that holds of three numbers precisely if they are the side lengths of a right triangle. So the relation is true of the triple (3, 4, 5), but not of (4, 5, 6) (since 32 + 42 = 52 but 42 + 52 ≠ 62 ). Notice that we can talk about a pair or triple satisfying a relation. We might say that a pair belongs to the relation. The careful and formal way to define a relation is as a set of ordered pairs (or triples, etc.). Consider the (infinite) set of all ordered pairs (𝑎, 𝑏) such that 𝑎 < 𝑏. Every element of this set contains numbers for which the relation “less than” is true, and every pair of numbers for which the relation is true is a pair in the set. So we can say that this set of pairs is the relation. Relations can have some standard properties, and deciding whether a particular relation has a given property can often help us understand the relation better. The less-than relation is, for example, irreflexive because there are no elements that are less than themselves. It is also antisymmetric since there are no distinct numbers 𝑎 and 𝑏 such that 𝑎 < 𝑏 and 𝑏 < 𝑎. It is also transitive since if 𝑎 < 𝑏 and 𝑏 < 𝑐 then it must follow that 𝑎 < 𝑐. These are just a few examples of relation properties though. Why would we care about these properties? It turns out that some groups of properties happen together frequently, and for such collections of properties, we can prove general results about the relations that satisfy them. So if we can prove that a given relation is reflexive, symmetric, and transitive (whatever those mean), then we know the relation is an equivalence relation, and therefore we know it has a bunch of other properties. A large portion of discrete mathematics is about studying particular types of relations. One of my favorites is a relation that gives us a graph. 10 0. Introduction and Preliminaries 0.2.6 Graphs Consider the set 𝑉 = {1, 2, 3, 4, 5, 6}. Which pairs of numbers from that set add up to 7? We could have {1, 6} or {2, 5} or {3, 4}. We can picture the set and the interesting (unordered) pairs (i.e., two-element subsets) as a picture called a graph: 6 1 5 2 4 3 On the other hand, we might want to consider pairs of numbers whose sum is even. Then, we would get the following picture. 6 1 5 2 4 3 We call these discrete structures graphs. A graph is a type of relation, one that is symmetric (if 𝑎 is related to 𝑏, then 𝑏 is related to 𝑎) and irreflexive (no element is related to itself). However, we mostly think of graphs as the drawings of dots and lines, or more precisely as a set of vertices together with a set of edges, where each edge is a two-element subset of the vertices. Notice that even here, we are using the structure set to define the structure graph. Graphs show up in all sorts of real-world applications: in a class, some students are friends with each other, so take the students to be the vertices and the edges to be the friendships. In geography, some countries share a border, so take the countries to be the vertices and connect a pair of vertices with an edge if the countries share a border. Perhaps you are planning a trip and want to fly from Denver to Paris. Is there a direct flight, or must you stop in Newark? That is, does the graph of flights have an edge between Denver and Paris or only between Denver and Newark and between Newark and Paris? When your Amazon driver delivers packages to 10 houses in your neighborhood, how does her app know in which order to deliver the packages? Graph theory! The study of graphs is a subject in its own right, in which many mathematicians hold doctorate degrees and write hundreds of papers each year. We will scratch the surface of this fascinating subject in Chapter 2 0.2.7 Even More Structures Our list of structures could go on and on, but we will stop here. We will spend just a little time looking at multisets, which are just like sets except can have repeated elements. Since this is not a geometry class, we will not consider finite geometries, or 0.2. Discrete Structures 11 designs (which are somewhere between graphs and geometries). Discrete structures are useful in computer science, but we will stop short of studying linked lists or red-black trees. Although abstract algebra is a fascinating subject, we will not get to groups or rings or metroids or POSets or Boolean algebras or... These are examples of sets on which we define additional operations and study the algebraic structure of how the sets and operations interact. The point is, discrete mathematics is awesome and you can spend multiple lifetimes studying it. So what are we waiting for? Let’s dive in and solve some problems. 0.2.8 Reading Questions 1. Think back to the domino problem at the beginning of this section. We asked how many dominoes are in a double-six domino set. Is this really a set, in our mathematical sense? What discrete structure would you use to represent each domino individually? 2. A double-zero domino set would contain only one domino (both sides showing 0). A double-one set would contain this plus the dominoes (1, 0) and (1, 1). We can continue in this way, creating a sequence of domino sets. Find the next three terms of the sequence. 1, 3, , , ,... 3. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about. Chapter 1 Logic and Proofs Logic is the study of consequence. Given a few mathematical statements or facts, we would like to be able to draw some conclusions. For example, if I told you that a particular real-valued function was continuous on the interval [0, 1], and 𝑓 (0) = −1 and 𝑓 (1) = 5, can we conclude that there is some point between [0, 1] where the graph of the function crosses the 𝑥-axis? Yes, we can, thanks to the Intermediate Value Theorem from calculus. Can we conclude that there is exactly one point? No. Whenever we find an “answer” in math, we really have a (perhaps hidden) argument. Mathematics is really about establishing general statements (like the Intermediate Value Theorem). This is done via an argument called a proof. We start with some given conditions, the premises of our argument, and from these, we find a consequence of interest, our conclusion. The problem is, as you no doubt know from arguing with friends, not all arguments are good arguments. A bad argument is one in which the conclusion does not follow from the premises, i.e., the conclusion is not a consequence of the premises. Logic is the study of what makes an argument good or bad. In other words, logic aims to determine in which cases a conclusion is, or is not, a consequence of a set of premises. We will start in Section 1.1 by considering statements, the building blocks of arguments. Understanding what counts as a statement and what form statements can take is the first step in understanding arguments. We will take a closer look at how statements can be combined in Section 1.2. Then we will see what mathematical tools we can develop to better analyze these statements and how they interact in Section 1.3. Finally, we will put all of this together in Section 1.4 and Section 1.5 to see how we can use these tools to construct arguments and prove statements. 1.1 Mathematical Statements Objectives After completing this section, you should be able to do the following. 1. Identify the logical structure of statements to determine their truth value in terms of the truth values of their parts. 2. Identify the use of quantifiers in a statement and determine the truth value of the statement based on those quantifiers. 3. Translate between statements in natural language and logical symbols. 13 14 1. Logic and Proofs 1.1.1 Section Preview Investigate! While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave. Each troll makes a single statement: Troll 1: If I am a knave, then there are exactly two knights here. Troll 2: Troll 1 is lying. Troll 3: Either we are all knaves or at least one of us is a knight. Which troll is which? Try it 1.1.1 Spend a few minutes thinking about the Investigate problem above. What could you conclude if you knew Troll 1 really was a knave (i.e., their statement was false)? Share your initial thoughts on this. In order to do mathematics, we must be able to talk and write about mathematics. Perhaps your experience with mathematics so far has mostly involved finding numerical answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process. In fact, the primary goal of mathematics, as an academic discipline in its own right, is to establish general mathematical truths. How can we know whether these facts, perhaps called theorems or propositions, are true? We construct valid arguments, called proofs, which establish the truth of the statements. Here, an argument is not the sort of thing you have with your Mom when you disagree about what to have for dinner. Rather, we have a technical definition of the term. Definition 1.1.2 Argument. An argument is a sequence of statements, the last of which is called the conclusion and the rest of which are called premises. An argument is said to be valid provided the conclusion must be true whenever the premises are all true. An argument is invalid if it is not valid; that is, all the premises can be true and the conclusion could still be false. An argument is sound provided it is valid and all the premises are true. A proof of a statement is a sound argument whose conclusion is the statement. 1.1. Mathematical Statements 15 By the way... Our definitions of argument, valid argument, and sound argument are the same ones used in philosophy, the other primary academic discipline concerned with logic and reasoning. To determine whether we have a proof of a statement, we must decide both whether every premise is true, and whether the argument is valid: whether the conclusion follows from the premises. How can we do this? Example 1.1.3 Consider the following two arguments: If Edith eats her vegetables, then she can have a cookie. Edith eats her vegetables. ∴ Edith gets a cookie. Florence must eat her vegetables to get a cookie. Florence eats her vegetables. ∴ Florence gets a cookie. (The symbol “∴ ” means “therefore”) Are these arguments valid? Solution. Do you agree that the first argument is valid but the second argument is not? We will soon develop a better understanding of the logic involved in this analysis, but if your intuition agrees with this assessment, then you are in good shape. Notice the two arguments look almost identical. Edith and Florence both eat their vegetables. In both cases, there is a connection between the eating of vegetables and cookies. Yet we claim that it is valid to conclude that Edith gets a cookie, but not that Florence does. The difference must be in the connection between eating vegetables and getting cookies. We need to be skilled at reading and comprehending these sentences. Do the two sentences mean the same thing? Unfortunately, in everyday language we are often sloppy, and you might be tempted to say they are equivalent. But notice that just because Florence must eat her vegetables, we have not claimed that doing so would be enough (she might also need to clean her room, for example). In everyday (non- mathematical) practice, you might be tempted to say this “other direction” is implied. In mathematics, we never get that luxury. Remark 1.1.4 The arguments in the example above illustrate another important point: even if you don’t care about the advancement of human knowledge in 16 1. Logic and Proofs the field of mathematics, becoming skilled at analyzing arguments is useful. And even if you don’t want to give your grandmother a cookie. If you are using mathematics to solve problems in some other discipline, it is still necessary to demonstrate that your solution is correct. You better have a good argument that it is! Since arguments are built up of statements, we must agree on what counts as a statement. Definition 1.1.5 A statement is a declarative sentence that is either true or false. If the sentences in an argument could not be true or false, there would be no way to determine whether the argument was valid, since validity describes a relationship between the truth values of the premises and conclusions. The goal of this section is to explore the different “shapes” a statement can take. We will see that more complicated statements can be built up from simpler ones, in ways that entirely determine their truth value based on the truth values of their parts. Preview Activity Before reading on to the main content of the section, complete this preview activity to start thinking about the types of questions this section will address. 1. Which of the following sentences should count as statements? That is, for which of the sentences below, could you potentially claim the sentence was either true or false? Select all that apply. A. The sum of the first 100 positive integers. B. What is the sum of the first 100 positive integers? C. The sum of the first 100 positive integers is 5050. D. Is the sum of the first 100 positive integers 5050? E. The sum of the first 100 positive integers is 17. 2. You and your roommate are arguing and they make the audacious claim that pineapple is good both on pizza and in smoothies. Which of the following are reasonable responses to this claim, from a logical point of view? A. The statement is false because even though pineapple is good in smoothies, it is NOT good on pizza. B. The statement is false because while pineapple is good on pizza and pineapple is good in smoothies, a pizza smoothie is never good. 1.1. Mathematical Statements 17 C. The statement is half true because regardless of what you think about pineapple on pizza, we can all agree at least that pineapple is good in smoothies. D. The statement is false because everyone who likes pineapple on pizza does NOT like pineapple in smoothies. 3. Your roommate now makes an even more outrageous claim: if a superhero movie is part of the Marvel Cinematic Universe, then it is good. Which of the following are reasonable responses to this claim, from a logical point of view? A. This is false because there are good superhero movies, like Wonder Woman and Dark Knight, that are based on DC Comics, and so not part of the Marvel Cinematic Universe. B. The statement is false because there is at least one superhero movie that is part of the Marvel Cinematic Universe that is also not good. C. The statement is false because, for example, Green Lantern is neither Marvel nor good. D. The statement is true because more than half of the Marvel movies are good. 4. Your roommate just won’t let up with their outrageous claims. Now they claim that either every troll is a knave, or there is at least one troll that is a knight. What can you say to this? A. Yes, this is true because every troll is either a knight or a knave. If it is not the case that all trolls are knaves, then there must be some troll that is a knight. B. This is false because some trolls are knights and some other trolls are knaves. C. The statement is false because there is no way to verify which of the two options is the case. D. The statement is false because no troll could say that all trolls are knaves, since knaves always lie. 1.1.2 Atomic and Molecular Statements A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular. 18 1. Logic and Proofs Example 1.1.6 These are statements (in fact, atomic statements): Telephone numbers in the USA have 10 digits. The moon is made of cheese. 42 is a perfect square. Every even number greater than 2 can be expressed as the sum of two primes. 3 + 7 = 12 And these are not statements: Would you like some cake? The sum of two squares. 1 + 3 + 5 + 7 + · · · + 2𝑛 + 1. Go to your room! 3 + 𝑥 = 12 The reason the sentence “3 + 𝑥 = 12” is not a statement is that it contains a variable. Depending on what 𝑥 is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done by setting a specific substitution, for example, “3 + 𝑥 = 12 where 𝑥 = 9,” which is a true statement. Or you could capture the free variable by quantifying over it, as in, “For all values of 𝑥, 3 + 𝑥 = 12,” which is false. We will discuss quantifiers in more detail in the subsection Quantifiers and Predicates below. You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement: Telephone numbers in the USA have 10 digits and 42 is a perfect square. Note that we can break this down into two smaller statements. The two shorter statements are connected by an “and.” We will consider 5 connectives: “and” (Sam is a man and Chris is a woman), “or” (Sam is a man or Chris is a woman), “if... , then... ” (if Sam is a man, then Chris is a woman), “if and only if” (Sam is a man if and only if Chris is a woman), and “not” (Sam is not a man). The first four are called binary connectives (because they connect two statements) while “not” is an example of a unary connective (since it applies to a single statement). These molecular statements are, of course, still statements, so they must be either true or false. The crucial observation here is that which truth value the molecular 1.1. Mathematical Statements 19 statement achieves is completely determined by the type of connective and the truth values of the parts. We do not need to know what the parts actually say or whether they have some material connection to each other, only whether those parts are true or false. To analyze logical connectives, it is enough to consider propositional variables (sometimes called sentential variables), usually capital letters in the middle of the alphabet: 𝑃, 𝑄, 𝑅, 𝑆,.... We think of these as standing in for (usually atomic) statements, but there are only two values the variables can achieve: true or false.1 We also have symbols for the logical connectives: ∧, ∨, →, ↔, ¬. Definition 1.1.7 Logical Connectives. We define the following logical connectives. 𝑃 ∧ 𝑄 is read “𝑃 and 𝑄,” and is called a conjunction. 𝑃 ∨ 𝑄 is read “𝑃 or 𝑄,” and is called a disjunction. 𝑃 → 𝑄 is read “if 𝑃 then 𝑄,” and is called an implication or conditional. 𝑃 ↔ 𝑄 is read “𝑃 if and only if 𝑄,” and is called a biconditional. ¬𝑃 is read “not 𝑃,” and is called a negation. The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connectives: Definition 1.1.8 Truth Conditions for Connectives. The truth conditions for the logical connectives are defined as follows. 𝑃 ∧ 𝑄 is true when both 𝑃 and 𝑄 are true. 𝑃 ∨ 𝑄 is true when 𝑃 or 𝑄 or both are true. 𝑃 → 𝑄 is true when 𝑃 is false or 𝑄 is true (or both). 𝑃 ↔ 𝑄 is true when 𝑃 and 𝑄 are both true, or both false. ¬𝑃 is true when 𝑃 is false. Each of the above definitions can be represented in a table, called a truth table. We simply list what the truth value of the statement is for each possible combination of truth values of the parts. 1 In computer programming, we should call such variables Boolean variables. 20 1. Logic and Proofs 𝑃 𝑄 𝑃∧𝑄 𝑃 𝑄 𝑃∨𝑄 𝑃 𝑄 𝑃→𝑄 𝑃 𝑄 𝑃↔𝑄 T T T T T T T T T T T T T F F T F T T F F T F F F T F F T T F T T F T F F F F F F F F F T F F T 𝑃 ¬𝑃 T F F T Figure 1.1.9 Truth tables for logical connectives For example, we can use the truth table for 𝑃 → 𝑄 to decide whether the statement, “If 5 is even, then 6 is even,” is true or false. Here 𝑃 is the statement “5 is even” and 𝑄 is the statement “6 is even.” Since 5 is not even, the statement 𝑃 is false. Since 6 is even, the statement 𝑄 is true. The truth table tells us that the statement 𝑃 → 𝑄 is true when 𝑃 is false and 𝑄 is true (the 3rd row). So the statement, “If 5 is even, then 6 is even,” is true. (If you don’t like that the statement is true, hold on to that thought and we will hopefully resolve it soon.) Note that for us, or is the inclusive or (and not the sometimes used exclusive or) meaning that 𝑃 ∨ 𝑄 is in fact true when both 𝑃 and 𝑄 are true. As for the other connectives, “and” behaves as you would expect, as does negation. The biconditional (if and only if) might seem a little strange, but you should think of this as saying the two parts of the statements are equivalent in that they have the same truth value. This leaves only the implication 𝑃 → 𝑄 which has a slightly different meaning in mathematics than in ordinary usage. However, implications are so common and useful in mathematics that we must develop a level of fluency with their use which warrants a whole section (Section 1.2). Example 1.1.10 Using the truth conditions for the logical connectives, determine which statements below are true and which are false. 1. 17 is prime and 17 is odd. 2. 17 is prime and 18 is prime. 3. 17 is prime or 18 is prime. 4. 17 is prime or 19 prime. 5. If 17 is prime, then 19 is prime. 6. If 18 is prime, then my favorite number is 17. 7. 17 is prime if and only if 19 is prime. 8. 17 is not prime if and only if 19 is not prime. 1.1. Mathematical Statements 21 Solution. First, let’s agree on some facts: 17 really is prime and odd, 18 is not either, and 19 is prime. 1. True. Both parts of the conjunction are true, so the entire statement is true. 2. False. The first part is true, but the second part is false, so the entire statement is false. 3. True. The first part is true, so the entire statement is true. As soon as we see one true statement in a disjunction, we can stop checking and declare the entire statement true. 4. True. Since we use the inclusive or, the statement is true when both parts are true. 5. True. Don’t be worried that there isn’t a good reason that 17 being prime causes 19 to be prime. That is not what we mean by a conditional statement. Since the “then” part is true, we know that the statement overall is true. 6. True. The “if” part of the statement is false. That’s all we need. I bet you don’t even know what my favorite number is, and you don’t need to. The statement is true. 7. True. Do both parts have the same truth value? Yes, since they are both true. So the entire statement is true. 8. True as well. Now both parts are false (since both are the negation of a true statement), so the entire statement is true. The way we define logical connectives and their truth value is very precise and technical. Often, language is not. Part of learning how to communicate mathematics is learning the cultural norms of mathematical language and how to translate statements in ordinary language into these technical statements. This will get easier with practice, so make sure you are talking to lots of people about the math you are studying. Here are a few examples of how ordinary language might be difficult to translate. Example 1.1.11 Identify the logical structure of each of the following statements. 1. 4 and 5 are both prime. 2. Only one of 4 or 5 is prime. 3. You must attend every day and do the homework to pass this class. 22 1. Logic and Proofs 4. Every number is even or odd. Solution. 1. Do you agree this is the same statement as “4 is prime and 5 is prime”? Notice that it would not make sense to write this as 𝑃 ∧ 𝑄 where 𝑃 is “4” and 𝑄 is “5 is prime”. But if we let 𝑃 be the statement, “4 is prime,” then both parts of the conjunction are statements. 2. Again, we can’t just put what is on one side of the “or” as a statement. But if we let 𝑃 be “4 is prime” and 𝑄 be “5 is prime,”, then we can write this as (𝑃 ∨ 𝑄) ∧ ¬(𝑃 ∧ 𝑄). That is, either 4 is prime or 5 is prime, and it is not the case that both 4 is prime and 5 is prime. 3. Here is another way you could phrase the same statement: If you pass the class, then it must be the case that you attended every day and that you did the homework. If we agree that this is just a clearer way to state the original statement, then we could illustrate its structure as 𝑃 → (𝑄 ∧ 𝑅). 4. Notice that this is not the same as saying, “Every number is even or every number is odd.” Of course, saying, “3 is even or odd,” is the same as saying, “3 is even or 3 is odd.” Language is confusing! We don’t yet have the logical technology to translate this statement as anything more than 𝑃, where 𝑃 is the statement, “Every number is even or odd.” Luckily, that technology is available, starting... now! 1.1.3 Quantifiers and Predicates Did you know that all mammals have hair? That every integer is even or odd? That some odd numbers are not prime? Our goal is to explore how to write statements such as these in mathematical notation to highlight the logical structure of the statements. This will require considering a new sort of basic sentence called a predicate, which is like a statement, but contains a free variable. When you replace that variable with a constant of some sort, then the sentence becomes a statement proper. Think of a predicate as making a claim about the values that are substituted for the “placeholder” variable(s). A predicate can be made into a (true or false) statement by evaluating it at some constant(s), or we can claim that some or all possible constants would make the resulting statement true or false. This is done using quantifiers. 1.1. Mathematical Statements 23 Definition 1.1.12 Quantifiers. The universal quantifier is written ∀ and is read, “for all.” The existential quantifier is written ∃ and is read, “there exists” or “for some.” We usually write predicates similar to how you write a function, although with capital letters. For example, we might use the predicate 𝑃(𝑥) to represent “𝑥 is prime”. We can then say that 𝑃(7) is true (since 7 is prime) and that 𝑃(8) is false. Or using quantifiers, we can (falsely) claim that all numbers are prime by writing ∀𝑥𝑃(𝑥) or (truthfully) claim that there is at least one prime number, by writing ∃𝑥𝑃(𝑥). Example 1.1.13 Translate the statement, “Every number is even or odd,” into symbols. Solution. Before we even start using symbols, it is helpful to rephrase this in a way that captures the logical structure of the statement. What is the claim saying? Given any number, it will either be the case that the number is even, or that the number is odd. In particular, we are not claiming that either all numbers are even or all numbers are odd. Let’s use 𝐸(𝑥) to say that 𝑥 is even, and 𝑂(𝑥) to say that 𝑥 is odd. Then we can write, 𝐸(𝑥) ∨ 𝑂(𝑥) to say that 𝑥 is even or 𝑥 is odd. Which 𝑥 is that true for (according to the claim)? All of them. So we write the statement as, ∀𝑥(𝑂(𝑥) ∨ 𝐸(𝑥)). We added some parentheses to emphasize that the scope of the universal quantifier includes both predicates. Note that if we incorrectly interpreted the statement as claiming that either all numbers are even or all numbers are odd, we could write that as ∀𝑥𝑂(𝑥) ∨ ∀𝑥𝐸(𝑥). This is not the same! Just like we did for propositional logic and the logical connectives, we should decide what it means for a quantified predicate to be true or false. We say ∀𝑥𝑃(𝑥) is true if 𝑃(𝑎) is true no matter what constant 𝑎 we substitute for 𝑥. And similarly, ∃𝑥𝑃(𝑥) is true if there is at least one value 𝑎 for which 𝑃(𝑎) is true. However, we must be careful here. Consider the statement ∀𝑥∃𝑦(𝑦 < 𝑥). You would read this, “for every 𝑥 there is some 𝑦 such that 𝑦 is less than 𝑥.” Note that < is a predicate with two free variables, we have chosen to write it with the symbol between the variables instead of the funky-looking 𝐿(𝑦, 𝑥) or < (𝑦, 𝑥). 24 1. Logic and Proofs Is this statement true? The answer depends on our domain of discourse. When we say “for all” 𝑥, do we mean all positive integers or all real numbers or all elephants or...? Usually, this information is implied by the context of the statement. In discrete mathematics, we almost always quantify over the natural numbers, 0, 1, 2,..., so let’s take that for our domain of discourse here. For the statement to be true, we need, no matter what natural number we select, for there to be some natural number that is strictly smaller. Perhaps we could let 𝑦 be 𝑥 − 1? But here is the problem: what if 𝑥 = 0? Then 𝑦 = −1 and that is not a number! (in our domain of discourse). Thus we see that the statement is false because there is a number less than or equal to all other numbers. In symbols, ∃𝑥∀𝑦(𝑦 ≥ 𝑥). We will explore some rules for working with quantifiers and other connectives in Section 1.3. For now, we will focus on translating between informal statements in ordinary language and the more precise language of logic. There is no perfect algorithm for doing this translation, but here are a few useful rules of thumb. Every blank is blank. Any statement of the form, “Every 𝑃-thing is a 𝑄-thing” can be written as ∀𝑥(𝑃(𝑥) → 𝑄(𝑥)). Example: all mammals have hair, becomes ∀𝑥(𝑀(𝑥) → 𝐻(𝑥)), where 𝑀(𝑥) means 𝑥 is a mammal, and 𝐻(𝑥) means 𝑥 has hair. To make sense of this, think about what we mean by statements like these in terms of sets. We claim that the set of mammals is contained in, or is a subset of, the set of hairy things. What we mean by “𝐴 is a subset of 𝐵” is precisely that every element of 𝑥 is an element of 𝑦. This can also be expressed by saying that “if 𝑥 is an element of 𝐴, then 𝑥 is also an element of 𝐵.” Some blanks are blank. Any statement of the form, “Some 𝑃-things are 𝑄-things,” can be written as ∃𝑥(𝑃(𝑥) ∧ 𝑄(𝑥)). Example: Some cats can swim, becomes ∃𝑥(𝐶(𝑥) ∧ 𝑆(𝑥)), where 𝐶(𝑥) means 𝑥 is a cat, and 𝑆(𝑥) means 𝑥 can swim. Again, it is helpful to think of how to express such statements in terms of sets. To say that some cats can swim is to say that there are things that belong both to the set of cats and to the set of swimming things. Such animals belong to the intersection of these two sets, which you can describe as belonging to the first set and the second set. Existential statements of this form claim that the intersection of the two sets is not empty. 1.1. Mathematical Statements 25 Implicit Quantifiers. It is always a good idea to be precise in mathematics. Some- times though, we can relax a bit, as long as we all agree on a convention. An example of such a convention is to assume that sentences containing predicates with free variables are intended as statements, where the variables are universally quantified. For example, do you believe that if a shape is a square, then it is a rectangle? But how can that be true if it is not a statement? To be a little more precise, we have two predicates: 𝑆(𝑥) for “𝑥 is a square” and 𝑅(𝑥) for “𝑥 is a rectangle”. The sentence we are looking at is 𝑆(𝑥) → 𝑅(𝑥). This is neither true nor false, as it is not a statement. But come on! We all know that we meant to consider the statement, ∀𝑥(𝑆(𝑥) → 𝑅(𝑥)), and this is what our convention tells us to consider. We call the resulting statement the universal generalization of the original sentence. Definition 1.1.14 Given a sentence with free variables, the universal generalization of that sentence is the statement obtained by adding enough universal quantifiers to the beginning of the sentence so that all free variables become bound. Similarly, we will often be a bit sloppy about the distinction between a predicate and a statement. For example, we might write, let 𝑃(𝑛) be the statement, “𝑛 is prime,” which is technically incorrect. It is implicit that we mean that we are defining 𝑃(𝑛) to be a predicate, which for each 𝑛 becomes the statement, 𝑛 is prime. 1.1.4 Reading Questions 1. Match each statement in symbols with its type of statement. 𝑃∧𝑄 If 𝑃, then 𝑄, (implication) 𝑃→𝑄 𝑃 or 𝑄 (disjunction) 𝑃∨𝑄 𝑃 and 𝑄 (conjunction) ¬𝑃 Not 𝑃 (negation) 2. Consider the sentence, “If 𝑥 > 3, then 𝑥 is even.” Which of the following statements are true about the sentence? Select all that apply. A. The sentence is a false statement since it has a free variable. B. The universal generalization of the sentence is a statement. C. If you substitute 10 for 𝑥, the resulting statement is true. D. The sentence becomes a true statement no matter what natural number you substitute for 𝑥 26 1. Logic and Proofs 3. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about. 1.1.5 Practice Problems 1. For each sentence below, decide whether it is an atomic statement, a molecular statement, or not a statement at all. (a) Some say the end is near and some say we’ll see Armageddon soon. (b) Mom’s coming ’round to put it back the way it ought to be. (c) Learn to swim. 2. Classify each of the sentences below as an atomic statement, a molecular statement, or not a statement at all. If the statement is molecular, say what kind it is (conjuction, disjunction, conditional, biconditional, negation). (a) Everybody can be fooled sometimes. (b) Every natural number greater than 1 is either prime or composite. (c) Go to your room! (d) The Broncos will win the Super Bowl or I’ll eat my hat. (e) This shirt is not black. 3. Determine whether each molecular statement below is true or false, or whether it is impossible to determine. Assume you do not know what my favorite number is (but you do know which numbers are prime). (a) If 4 is my favorite number, then 4 + 1 is my favorite number (b) 8 is my favorite number and 3 is not prime. (c) 4 is my favorite number or 4 is prime. (d) If 4 is prime, then 2 · 4 is prime (e) If 3 is prime, then 3 is my favorite number. (f) 8 is my favorite number and 4 is not prime. 4. Let 𝑃(𝑥, 𝑦) be the predicate, “person 𝑥 can be fooled at time 𝑦.” Match each statement with its representation in symbols. Some people can be fooled all of the time. ∀𝑦∃𝑥𝑃(𝑥, 𝑦) Everyone can be fooled sometimes. ∃𝑦∀𝑥𝑃(𝑥, 𝑦) It is always true that some people can be fooled. ∀𝑥∃𝑦𝑃(𝑥, 𝑦) Sometimes everyone can be fooled. ∃𝑥∀𝑦𝑃(𝑥, 𝑦) 1.1. Mathematical Statements 27 5. Your friend believes that you cannot fool everyone at the same time. What is another way of saying this, and how would you write that in symbols (using 𝑃(𝑥, 𝑦) to say you can fool 𝑥 at time 𝑦). A. Someone is never fooled. ∃𝑥∀𝑦¬𝑃(𝑥, 𝑦) B. Everyone is never fooled. ∀𝑥∀𝑦¬𝑃(𝑥, 𝑦) C. Someone is not fooled sometimes. ∃𝑥∃𝑦¬𝑃(𝑥, 𝑦) D. Everyone is not fooled sometimes. ∀𝑥∃𝑦¬𝑃(𝑥, 𝑦) 6. Regardless of your beliefs of how many people can be fooled at various times, what could you conclude if we reinterpret 𝑃(𝑥, 𝑦) to mean 𝑥 < 𝑦 and only quantify over the natural numbers (so ∀𝑥 means “for all natural numbers” and ∃𝑥 means “there exists a natural number”)? Select all of the following that apply. A. ∀𝑥∃𝑦𝑃(𝑥, 𝑦) is true. B. ∃𝑥∀𝑦𝑃(𝑥, 𝑦) is true. C. ∀𝑦∃𝑥𝑃(𝑥, 𝑦) is true. D. ∃𝑦∀𝑥𝑃(𝑥, 𝑦) is true. E. No matter what 𝑃(𝑥, 𝑦) means, we can conclude that ∀𝑥∃𝑦𝑃(𝑥, 𝑦) and ∃𝑦∀𝑥 are NOT logically equivalent 7. Let 𝑃(𝑥) be the predicate, “17𝑥 + 1 is even.” (a) Is 𝑃(15) true or false? (b) What, if anything, can you conclude about ∃𝑥𝑃(𝑥) from the truth value of 𝑃(15)? (c) What, if anything, can you conclude about ∀𝑥𝑃(𝑥) from the truth value of 𝑃(15)? 8. Let 𝑃(𝑥) be the predicate, “18𝑥 + 1 is even.” (a) Is 𝑃(15) true or false? (b) What, if anything, can you conclude about ∃𝑥𝑃(𝑥) from the truth value of 𝑃(15)? (c) What, if anything, can you conclude about ∀𝑥𝑃(𝑥) from the truth value of 𝑃(15)? 9. Consider the sentence, ∃𝑥𝑃(𝑥, 𝑦) → ∀𝑥𝑃(𝑥, 𝑦). What can we say about this sentence? Select all that apply. A. The sentence is a statement because it contains quantifiers. 28 1. Logic and Proofs B. The sentence is not a statement because 𝑥 and 𝑧 are free variables. C. The sentence is not a statement because 𝑦 is a free variable. D. The universal generalization of the sentence is a statement. 10. Suppose 𝑃(𝑥, 𝑦) is some binary predicate defined on a very small domain of discourse: just the integers 1, 2, 3, and 4. For each of the 16 pairs of these numbers, 𝑃(𝑥, 𝑦) is either true or false, according to the following table (𝑥 values are rows, 𝑦 values are columns). 1 2 3 4 1 T F F F 2 F T T F 3 T T T T 4 F F F F For example, 𝑃(1, 3) is false, as indicated by the F in the first row, third column. Use the table to decide whether the following statements are true or false. (a) ∀𝑦∃𝑥𝑃(𝑥, 𝑦). (b) ∃𝑥∀𝑦𝑃(𝑥, 𝑦). (c) ∀𝑥∃𝑦𝑃(𝑥, 𝑦). (d) ∃𝑦∀𝑥𝑃(𝑥, 𝑦). 1.1.6 Additional Exercises 1. Suppose 𝑃 and 𝑄 are the statements: 𝑃: Jack passed math. 𝑄: Jill passed math. (a) Translate “Jack and Jill both passed math” into symbols. (b) Translate “If Jack passed math, then Jill did not” into symbols. (c) Translate “𝑃 ∨ 𝑄” into English. (d) Translate “¬(𝑃 ∧ 𝑄) → 𝑄” into English. (e) Suppose you know that if Jack passed math, then so did Jill. What can you conclude if you know that: i. Jill passed math? ii. Jill did not pass math? 2. Translate into symbols. Use 𝐸(𝑥) for “𝑥 is even” and 𝑂(𝑥) for “𝑥 is odd.” (a) No number is both even and odd. (b) One more than any even number is an odd number. 1.1. Mathematical Statements 29 (c) There is prime number that is even. (d) Between any two numbers there is a third number. (e) There is no number between a number and one more than that number. 3. For each of the statements below, give a domain of discourse for which the statement is true, and a domain for which the statement is false. (a) ∀𝑥∃𝑦(𝑦 2 = 𝑥). (b) ∀𝑥∀𝑦(𝑥 < 𝑦 → ∃𝑧(𝑥 < 𝑧 < 𝑦)). (c) ∃𝑥∀𝑦∀𝑧(𝑦 < 𝑧 → 𝑦 ≤ 𝑥 ≤ 𝑧). 1.2 Implications Objectives After completing this section, you should be able to do the following. 1. Explain the conditions under which an implication is true. 2. Identify statements as equivalent to a given implication or its converse. 3. Explain the relationship between the truth values of an implication, its converse, and its contrapositive. 1.2.1 Section Preview Investigate! Little Timmy’s Mom tells him, “if you don’t eat all your broccoli, then you will not get any ice cream.” Of course, Timmy loves his ice cream, so he quickly eats all his broccoli (which actually tastes pretty good). After dinner, when Timmy asks for his ice cream, he is told no! Does Timmy have a right to be upset? Why or why not? By far, the most important type of statement in mathematics is the implication. It is also the least intuitive of our basic molecular statement types. Our goal in this section is to become more familiar with this key concept. To see why this sort of statement is so prevalent, consider the Pythagorean Theorem. Despite what social media might claim, the Pythagorean Theorem is not 𝑎2 + 𝑏2 = 𝑐2. Okay, sure, that has a variable in it, so we must be using the convention to take the universal generalization, ∀𝑎, 𝑏, 𝑐 ∈ ℝ 𝑎 2 + 𝑏 2 = 𝑐 2. So 12 + 52 = 22 ??? Okay, fine. The equation is true as long as 𝑎 and 𝑏 are the lengths of the legs of a right triangle and 𝑐 is the length of the hypotenuse. In other words: If 𝑎 and 𝑏 are the lengths of the legs of a right triangle with hypotenuse of length 𝑐, then 𝑎 2 + 𝑏 2 = 𝑐 2. Math is about making general claims, but a claim is rarely going to be true of absolutely every mathematical object. The way we restrict our claims to a particular type of object is with an implication: “take any object you like, if it is of the right type, then this thing is true about it.” 30 1.2. Implications 31 Similarly, as we saw in the Quantifiers and Predicates subsection, when we make claims like “every square is a rectangle,” we really have an implication: “if something is a square, then it is a rectangle.” Here is a reminder of what we mean by an implication. Definition 1.2.1 Implication. An implication (or conditional) is a molecular statement of the form 𝑃→𝑄 where 𝑃 and 𝑄 are statements. We say that 𝑃 is the hypothesis (or antecedent). 𝑄 is the conclusion (or consequent). An implication is true provided 𝑃 is false or 𝑄 is true (or both), and false otherwise. In particular, the only way for 𝑃 → 𝑄 to be false is for 𝑃 to be true and 𝑄 to be false. The definition of truth of an implication can also be represented as a truth table: 𝑃 𝑄 𝑃→𝑄 T T T T F F F T T F F T Figure 1.2.2 The truth table for 𝑃 → 𝑄 Does this truth table make sense? Should we believe it? Look in particular at the third row: F, T, T, and consider the implication, “If 5 < 3 then 5 + 3 = 8.” Does that statement feel true? The truth table says it should be (since 5 < 3 is false, and 5 + 3 = 8 is true). Much of what we will do in the remainder of this section is convince ourselves that this truth table makes sense. Preview Activity 1. Consider the statement “If Tommy doesn’t eat his broccoli, then he will not get any ice cream.” Which of the following statements mean the same thing (i.e., will be true in the same situations)? Select all that apply. A. If Tommy does eat his broccoli, then he will get ice cream. B. If Tommy gets ice cream, then he ate his broccoli. C. If Tommy doesn’t get ice cream, then he didn’t eat his broccoli. 32 1. Logic and Proofs D. Tommy ate his broccoli and still didn’t get any ice cream. 2. Suppose that your shady uncle offers you the following deal: If you loan him your car, then he will bring you tacos. In which of the following situations would it be fair to say that your uncle is a liar (i.e., that his statement was false)? Select all that apply. A. You loan him your car. He brings you tacos. B. You loan him your car. He never buys you tacos. C. You don’t loan him your car. He still brings you tacos. D. You don’t loan him your car. He never brings you tacos. 3. Consider the sentence, “if 𝑥 ≥ 10, then 𝑥 2 ≥ 25.” This sentence becomes a statement when we replace 𝑥 by a value, or “capture” the 𝑥 in the scope of a quantifier. Which of the following claims are true (select all that apply)? A. If we replace 𝑥 by 15, then the resulting statement is true. (Note, 152 = 225.) B. If we replace 𝑥 by 3, then the resulting statement is true. C. If we replace 𝑥 by 6, then the resulting statement is true. D. The universal generalization (“for all 𝑥, if 𝑥 ≥ 10 the 𝑥 2 ≥ 25”) is true. E. There is a number we could replace 𝑥 with that makes the statement false. 4. Consider the statement, “If I see a movie, then I eat popcorn” (which happens to be true). Based solely on your intuition of English, which of the following statements mean the same thing? Select all that apply. A. If I eat popcorn, then I see a movie. B. If I don’t eat popcorn, then I don’t see a movie. C. It is necessary that I eat popcorn when I see a movie. D. To see a movie, it is sufficient for me to eat popcorn. E. I only watch a movie if I eat popcorn. 1.2.2 Understanding the Truth Table The truth value of the implication is determined by the truth values of its two parts. Our definition of the truth conditions for an implication says that there is only one way for an implication to be false: when the hypothesis is true and the conclusion is false. 1.2. Implications 33 Example 1.2.3 Consider the statement: If Bob gets a 90 on the final, then Bob wil

Discrete Mathematics An Open Introduction PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue