Discrete Mathematics with Applications (5th Edition) PDF

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203  discrete mathematics with applications...

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203  discrete mathematics with applications FiFth editiON SUSANNA S. EPP DePaul University Australia Brazil Mexico Singapore United Kingdom United States Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 1 13/11/18 6:40 pm  Cover Photo: The stones are discrete objects placed one on top of another like a chain of careful reasoning. A person who decides to build such a tower aspires to the heights and enjoys playing with a challenging problem. Choosing the stones takes both a scientific and an aesthetic sense. Getting them to balance requires patient effort and careful thought. And the tower that results is beautiful. A perfect metaphor for discrete mathematics! Discrete Mathematics with Applications, © 2020, 2011, 2004 Cengage Learning, Inc. Fifth Edition Susanna S. Epp Unless otherwise noted, all content is © Cengage. Product Director: Mark Santee ALL RIGHTS RESERVED. No part of this work covered by the copyright Product Manager: Spencer Arritt herein may be reproduced or distributed in any form or by any means, except as permitted by U.S. copyright law, without the prior written Learning Designer: Mona Zeftel, permission of the copyright owner. Laura Gallus Content Manager: Lynh Pham, Christy Frame For product information and technology assistance, contact us at Cengage Product Assistant: Amanda Rose Customer & Sales Support, 1-800-354-9706 or support.cengage.com. E2E Project Manager: Peggy Buskey For permission to use material from this text or product, submit all requests online at www.cengage.com/permissions. Marketing Manager: Shannon Hawkins, Further permissions questions can be emailed to Giana Manzi [email protected]. IP Analyst: Reba Frederics IP Project Manager: Carly Belcher Library of Congress Control Number: 2018953604 Production Service: MPS Limited Student Edition: Compositor: MPS Limited ISBN: 978-1-337-69419-3 Designer: Diana Graham Loose-leaf Edition: Cover Image: Katherine Gendreau ISBN: 978-0-357-03523-8 Photography/Getty Images Cengage 20 Channel Center Street Boston, MA 02210 USA Cengage is a leading provider of customized learning solutions with employees residing in nearly 40 different countries and sales in more than 125 countries around the world. Find your local representative at www.cengage.com. Cengage products are represented in Canada by Nelson Education, Ltd. To learn more about Cengage platforms and services, register or access your online learning solution, or purchase materials for your course, visit www.cengage.com. Printed in the United States of America Print Number: 01 Print Year: 2018 Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 2 12/11/18 6:52 pm  To my husband, Helmut, and my children, Amanda, Catherine, and Caroline Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 3 12/11/18 6:52 pm  Know if you’re prepared for class! STUDY SMARTER 93% correlation between homework scores and in-class Ever wonder if you studied enough? WebAssign from performance Cengage can help. WebAssign is an online learning platform for your math, statistics and science courses. It helps you practice, focus your study time, and absorb what you learn. When class comes—you’re way more confident. With WebAssign you will: Get instant feedback Know how well you and grading understand concepts Watch videos and tutorials Perform better on when you’re stuck in-class assignments Ask your instructor today how you can get access to WebAssign! cengage.com/webassign Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 4 13/11/18 4:38 pm  ConTenTS ChApTER 1 Speaking Mathematically 1 1.1 Variables 1 Using Variables in Mathematical Discourse; Introduction to Universal, Existential, and Conditional Statements 1.2 The Language of Sets 6 The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products; Strings 1.3 The Language of Relations and Functions 15 Definition of a Relation from One Set to Another; Arrow Diagram of a Relation; Definition of Function; Function Machines; Equality of Functions 1.4 The Language of Graphs 24 Definition and Representation of Graphs and Directed Graphs; Degree of a Vertex; Examples of Graphs Including a Graph Coloring Application ChApTER 2 The Logic of Compound Statements 37 2.1 Logical Form and Logical Equivalence 37 Statements; Compound Statements; Truth Values; Evaluating the Truth of More General Compound Statements; Logical Equivalence; Tautologies and Contradictions; Summary of Logical Equivalences 2.2 Conditional Statements 53 Logical Equivalences Involving S; Representation of If-Then As Or; The Negation of a Conditional Statement; The Contrapositive of a Conditional Statement; The Converse and Inverse of a Conditional Statement; Only If and the Biconditional; Necessary and Sufficient Conditions; Remarks 2.3 Valid and Invalid Arguments 66 Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of Inference 2.4 Application: Digital Logic Circuits 79 Black Boxes and Gates; The Input/Output Table for a Circuit; The Boolean Expression Corresponding to a Circuit; The Circuit Corresponding to a Boolean Expression; Finding v Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 5 13/11/18 6:45 pm  vi ConTenTs a Circuit That Corresponds to a Given Input/Output Table; Simplifying Combinational Circuits; NAND and NOR Gates 2.5 Application: Number Systems and Circuits for Addition 93 Binary Representation of Numbers; Binary Addition and Subtraction; Circuits for Computer Addition; Two’s Complements and the Computer Representation of Negative Integers; 8-Bit Representation of a Number; Computer Addition with Negative Integers; Hexadecimal Notation ChAPTER 3 the Logic of Quantified statements 108 3.1 Predicates and Quantified Statements I I08 The Universal Quantifier: 5; The Existential Quantifier: E; Formal versus Informal Language; Universal Conditional Statements; Equivalent Forms of Universal and Existential Statements; Bound Variables and Scope; Implicit Quantification; Tarski’s World 3.2 Predicates and Quantified Statements II 122 Negations of Quantified Statements; Negations of Universal Conditional Statements; The Relation among 5, E, `, and ~; Vacuous Truth of Universal Statements; Variants of Universal Conditional Statements; Necessary and Sufficient Conditions, Only If 3.3 Statements with Multiple Quantifiers 131 Translating from Informal to Formal Language; Ambiguous Language; Negations of Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation; Prolog 3.4 Arguments with Quantified Statements 146 Universal Modus Ponens; Use of Universal Modus Ponens in a Proof; Universal Modus Tollens; Proving Validity of Arguments with Quantified Statements; Using Diagrams to Test for Validity; Creating Additional Forms of Argument; Remark on the Converse and Inverse Errors ChAPTER 4 elementary Number theory and methods of Proof 160 4.1 Direct Proof and Counterexample I: Introduction 161 Definitions; Proving Existential Statements; Disproving Universal Statements by Counterexample; Proving Universal Statements; Generalizing from the Generic Particular; Method of Direct Proof; Existential Instantiation; Getting Proofs Started; Examples 4.2 Direct Proof and Counterexample II: Writing Advice 173 Writing Proofs of Universal Statements; Common Mistakes; Examples; Showing That an Existential Statement Is False; Conjecture, Proof, and Disproof 4.3 Direct Proof and Counterexample III: Rational Numbers 183 More on Generalizing from the Generic Particular; Proving Properties of Rational Numbers; Deriving New Mathematics from Old Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 6 12/11/18 6:53 pm  ConTenTs vii 4.4 Direct Proof and Counterexample IV: Divisibility 190 Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique Factorization of Integers Theorem 4.5 Direct Proof and Counterexample V: Division into Cases and the Quotient-Remainder Theorem 200 Discussion of the Quotient-Remainder Theorem and Examples; div and mod; Alternative Representations of Integers and Applications to Number Theory; Absolute Value and the Triangle Inequality 4.6 Direct Proof and Counterexample VI: Floor and Ceiling 211 Definition and Basic Properties; The Floor of ny2 4.7 Indirect Argument: Contradiction and Contraposition 218 Proof by Contradiction; Argument by Contraposition; Relation between Proof by Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool 4.8 Indirect Argument: Two Famous Theorems 228 The Irrationality of Ï2; Are There Infinitely Many Prime Numbers?; When to Use Indirect Proof; Open Questions in Number Theory 4.9 Application: The handshake Theorem 235 The Total Degree of a Graph; The Handshake Theorem and Consequences; Applications; Simple Graphs; Complete Graphs; Bipartite Graphs 4.10 Application: Algorithms 244 An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division Algorithm; The Euclidean Algorithm ChAPTER 5 sequences, mathematical induction, and recursion 258 5.1 Sequences 258 Explicit Formulas for Sequences; Summation Notation; Product Notation; Properties of Summations and Products; Change of Variable; Factorial and n Choose r Notation; Sequences in Computer Programming; Application: Algorithm to Convert from Base 10 to Base 2 Using Repeated Division by 2 5.2 Mathematical Induction I: Proving Formulas 275 Principle of Mathematical Induction; Sum of the First n Integers; Proving an Equality; Deducing Additional Formulas; Sum of a Geometric Sequence 5.3 Mathematical Induction II: Applications 289 Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibility Properties; Proving Inequalities; Trominoes and Other Applications Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 7 12/11/18 6:53 pm  viii ConTenTs 5.4 Strong Mathematical Induction and the Well-Ordering Principle for the Integers 301 Strong Mathematical Induction; The Well-Ordering Principle for the Integers; Binary Representation of Integers and Other Applications 5.5 Application: Correctness of Algorithms 314 Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of the Euclidean Theorem 5.6 Defining Sequences Recursively 325 Examples of Recursively Defined Sequences; Recursive Definitions of Sum and Product 5.7 Solving Recurrence Relations by Iteration 340 The Method of Iteration; Using Formulas to Simplify Solutions Obtained by Iteration; Checking the Correctness of a Formula by Mathematical Induction; Discovering That an Explicit Formula Is Incorrect 5.8 Second-Order Linear homogeneous Recurrence Relations with Constant Coefficients 352 Derivation of a Technique for Solving These Relations; The Distinct-Roots Case; The Single-Root Case 5.9 General Recursive Definitions and Structural Induction 364 Recursively Defined Sets; Recursive Definitions for Boolean Expressions, Strings, and Parenthesis Structures; Using Structural Induction to Prove Properties about Recursively Defined Sets; Recursive Functions ChAPTER 6 set theory 377 6.1 Set Theory: Definitions and the Element Method of Proof 377 Subsets: Introduction to Proof and Disproof for Sets; Set Equality; Venn Diagrams; Operations on Sets; The Empty Set; Partitions of Sets; Power Sets; An Algorithm to Check Whether One Set Is a Subset of Another (Optional) 6.2 Properties of Sets 391 Set Identities; Proving Subset Relations and Set Equality; Proving That a Set Is the Empty Set 6.3 Disproofs and Algebraic Proofs 407 Disproving an Alleged Set Property; Problem-Solving Strategy; The Number of Subsets of a Set; “Algebraic” Proofs of Set Identities 6.4 Boolean Algebras, Russell’s Paradox, and the halting Problem 414 Boolean Algebras: Definition and Properties; Russell’s Paradox; The Halting Problem Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 8 12/11/18 6:53 pm  ConTenTs ix ChAPTER 7 Properties of Functions 425 7.1 Functions Defined on General Sets 425 Dynamic Function Terminology; Equality of Functions; Additional Examples of Functions; Boolean Functions; Checking Whether a Function Is Well Defined; Functions Acting on Sets 7.2 One-to-One, Onto, and Inverse Functions 439 One-to-One Functions; One-to-One Functions on Infinite Sets; Application: Hash Functions and Cryptographic Hash Functions; Onto Functions; Onto Functions on Infinite Sets; Relations between Exponential and Logarithmic Functions; One-to-One Correspondences; Inverse Functions 7.3 Composition of Functions 461 Definition and Examples; Composition of One-to-One Functions; Composition of Onto Functions 7.4 Cardinality with Applications to Computability 473 Definition of Cardinal Equivalence; Countable Sets; The Search for Larger Infinities: The Cantor Diagonalization Process; Application: Cardinality and Computability ChAPTER 8 Properties of relations 487 8.1 Relations on Sets 487 Additional Examples of Relations; The Inverse of a Relation; Directed Graph of a Relation; N-ary Relations and Relational Databases 8.2 Reflexivity, Symmetry, and Transitivity 495 Reflexive, Symmetric, and Transitive Properties; Properties of Relations on Infinite Sets; The Transitive Closure of a Relation 8.3 Equivalence Relations 505 The Relation Induced by a Partition; Definition of an Equivalence Relation; Equivalence Classes of an Equivalence Relation 8.4 Modular Arithmetic with Applications to Cryptography 524 Properties of Congruence Modulo n; Modular Arithmetic; Extending the Euclidean Algorithm; Finding an Inverse Modulo n; RSA Cryptography; Euclid’s Lemma; Fermat’s Little Theorem; Why Does the RSA Cipher Work?; Message Authentication; Additional Remarks on Number Theory and Cryptography 8.5 Partial Order Relations 546 Antisymmetry; Partial Order Relations; Lexicographic Order; Hasse Diagrams; Partially and Totally Ordered Sets; Topological Sorting; An Application; PERT and CPM Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 9 12/11/18 6:53 pm  x ConTenTs ChAPTER 9 counting and Probability 564 9.1 Introduction to Probability 564 Definition of Sample Space and Event; Probability in the Equally Likely Case; Counting the Elements of Lists, Sublists, and One-Dimensional Arrays 9.2 Possibility Trees and the Multiplication Rule 573 Possibility Trees; The Multiplication Rule; When the Multiplication Rule Is Difficult or Impossible to Apply; Permutations; Permutations of Selected Elements 9.3 Counting Elements of Disjoint Sets: The Addition Rule 589 The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule 9.4 The Pigeonhole Principle 604 Statement and Discussion of the Principle; Applications; Decimal Expansions of Fractions; Generalized Pigeonhole Principle; Proof of the Pigeonhole Principle 9.5 Counting Subsets of a Set: Combinations 617 r-Combinations; Ordered and Unordered Selections; Relation between Permutations and Combinations; Permutation of a Set with Repeated Elements; Some Advice about Counting; The Number of Partitions of a Set into r Subsets 9.6 r-Combinations with Repetition Allowed 634 Multisets and How to Count Them; Which Formula to Use? 9.7 Pascal’s Formula and the Binomial Theorem 642 Combinatorial Formulas; Pascal’s Triangle; Algebraic and Combinatorial Proofs of Pascal’s Formula; The Binomial Theorem and Algebraic and Combinatorial Proofs for It; Applications 9.8 Probability Axioms and Expected Value 655 Probability Axioms; Deriving Additional Probability Formulas; Expected Value 9.9 Conditional Probability, Bayes’ Formula, and Independent Events 662 Conditional Probability; Bayes’ Theorem; Independent Events ChAPTER 10 theory of Graphs and trees 677 10.1 Trails, Paths, and Circuits 677 Definitions; Connectedness; Euler Circuits; Hamiltonian Circuits 10.2 Matrix Representations of Graphs 698 Matrices; Matrices and Directed Graphs; Matrices and Undirected Graphs; Matrices and Connected Components; Matrix Multiplication; Counting Walks of Length N 10.3 Isomorphisms of Graphs 713 Definition of Graph Isomorphism and Examples; Isomorphic Invariants; Graph Isomorphism for Simple Graphs Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 10 12/11/18 6:53 pm  ConTenTs xi 10.4 Trees: Examples and Basic Properties 720 Definition and Examples of Trees; Characterizing Trees 10.5 Rooted Trees 732 Definition and Examples of Rooted Trees; Binary Trees and Their Properties; Binary Search Trees 10.6 Spanning Trees and a Shortest Path Algorithm 742 Definition of a Spanning Tree; Minimum Spanning Trees; Kruskal’s Algorithm; Prim’s Algorithm; Dijkstra’s Shortest Path Algorithm ChAPTER 11 analysis of algorithm efficiency 760 11.1 Real-Valued Functions of a Real Variable and Their Graphs 760 Graph of a Function; Power Functions; The Floor Function; Graphing Functions Defined on Sets of Integers; Graph of a Multiple of a Function; Increasing and Decreasing Functions 11.2 Big-O, Big-Omega, and Big-Theta Notations 769 Definition and General Properties of O-, V-, and Q-Notations; Orders of Power Functions; Orders of Polynomial Functions; A Caution about O-Notation; Theorems about Order Notation 11.3 Application: Analysis of Algorithm Efficiency I 787 Measuring the Efficiency of an Algorithm; Computing Orders of Simple Algorithms; The Sequential Search Algorithm; The Insertion Sort Algorithm; Time Efficiency of an Algorithm 11.4 Exponential and Logarithmic Functions: Graphs and Orders 800 Graphs of Exponential and Logarithmic Functions; Application: Number of Bits Needed to Represent an Integer in Binary Notation; Application: Using Logarithms to Solve Recurrence Relations; Exponential and Logarithmic Orders 11.5 Application: Analysis of Algorithm Efficiency II 813 Binary Search; Divide-and-Conquer Algorithms; The Efficiency of the Binary Search Algorithm; Merge Sort; Tractable and Intractable Problems; A Final Remark on Algorithm Efficiency ChAPTER 12 regular expressions and Finite-state automata 828 12.1 Formal Languages and Regular Expressions 829 Definitions and Examples of Formal Languages and Regular Expressions; The Language Defined by a Regular Expression; Practical Uses of Regular Expressions 12.2 Finite-State Automata 841 Definition of a Finite-State Automaton; The Language Accepted by an Automaton; The Eventual-State Function; Designing a Finite-State Automaton; Simulating a Finite-State Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 11 12/11/18 6:53 pm  xii ConTenTs Automaton Using Software; Finite-State Automata and Regular Expressions; Regular Languages 12.3 Simplifying Finite-State Automata 858 *-Equivalence of States; k-Equivalence of States; Finding the *-Equivalence Classes; The Quotient Automaton; Constructing the Quotient Automaton; Equivalent Automata APPENDIx A Properties of the real Numbers a-1 APPENDIx B solutions and hints to selected exercises a-4 Index I-1 Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 12 12/11/18 6:53 pm  PreFace My purpose in writing this book was to provide a clear, accessible treatment of discrete mathematics for students majoring or minoring in computer science, mathematics, math- ematics education, and engineering. The goal of the book is to lay the mathematical foun- dation for computer science courses such as data structures, algorithms, relational database theory, automata theory and formal languages, compiler design, and cryptography, and for mathematics courses such as linear and abstract algebra, combinatorics, probability, logic and set theory, and number theory. By combining discussion of theory and practice, I have tried to show that mathematics has engaging and important applications as well as being interesting and beautiful in its own right. A good background in algebra is the only prerequisite; the course may be taken by stu- dents either before or after a course in calculus. Previous editions of the book have been used successfully by students at hundreds of institutions in North and South America, Europe, the Middle East, Asia, and Australia. Recent curricular recommendations from the Institute for Electrical and Electronic Engineers Computer Society (IEEE-CS) and the Association for Computing Machinery (ACM) include discrete mathematics as the largest portion of “core knowledge” for com- puter science students and state that students should take at least a one-semester course in the subject as part of their first-year studies, with a two-semester course preferred when possible. This book includes the topics recommended by those organizations and can be used effectively for either a one-semester or a two-semester course. At one time, most of the topics in discrete mathematics were taught only to upper-level undergraduates. Discovering how to present these topics in ways that can be understood by first- and second-year students was the major and most interesting challenge of writing this book. The presentation was developed over a long period of experimentation during which my students were in many ways my teachers. Their questions, comments, and written work showed me what concepts and techniques caused them difficulty, and their reaction to my exposition showed me what worked to build their understanding and to encourage their interest. Many of the changes in this edition have resulted from continuing interaction with students. Themes of a Discrete Mathematics Course Discrete mathematics describes processes that consist of a sequence of individual steps. This contrasts with calculus, which describes processes that change in a continuous fash- ion. Whereas the ideas of calculus were fundamental to the science and technology of the industrial revolution, the ideas of discrete mathematics underlie the science and technol- ogy of the computer age. The main themes of a first course in discrete mathematics are logic and proof, induction and recursion, discrete structures, combinatorics and discrete probability, algorithms and their analysis, and applications and modeling. xiii Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 13 12/11/18 6:53 pm  xiv PrefACe Logic and Proof Probably the most important goal of a first course in discrete mathemat- ics is to help students develop the ability to think abstractly. This means learning to use logically valid forms of argument and avoid common logical errors, appreciating what it means to reason from definitions, knowing how to use both direct and indirect arguments to derive new results from those already known to be true, and being able to work with symbolic representations as if they were concrete objects. induction and recursion An exciting development of recent years has been the increased appreciation for the power and beauty of “recursive thinking.” To think recursively means to address a problem by assuming that similar problems of a smaller nature have already been solved and figuring out how to put those solutions together to solve the larger prob- lem. Such thinking is widely used in the analysis of algorithms, where recurrence relations that result from recursive thinking often give rise to formulas that are verified by math- ematical induction. discrete structures Discrete mathematical structures are the abstract structures that de- scribe, categorize, and reveal the underlying relationships among discrete mathematical objects. Those studied in this book are the sets of integers and rational numbers, general sets, Boolean algebras, functions, relations, graphs and trees, formal languages and regular expressions, and finite-state automata. combinatorics and discrete Probability Combinatorics is the mathematics of count- ing and arranging objects, and probability is the study of laws concerning the measure- ment of random or chance events. Discrete probability focuses on situations involving discrete sets of objects, such as finding the likelihood of obtaining a certain number of heads when an unbiased coin is tossed a certain number of times. Skill in using combina- torics and probability is needed in almost every discipline where mathematics is applied, from economics to biology, to computer science, to chemistry and physics, to business management. algorithms and their analysis The word algorithm was largely unknown in the middle of the twentieth century, yet now it is one of the first words encountered in the study of computer science. To solve a problem on a computer, it is necessary to find an algorithm, or step-by-step sequence of instructions, for the computer to follow. Designing an algorithm requires an understanding of the mathematics underlying the problem to be solved. Deter- mining whether or not an algorithm is correct requires a sophisticated use of mathematical induction. Calculating the amount of time or memory space the algorithm will need in order to compare it to other algorithms that produce the same output requires knowledge of combinatorics, recurrence relations, functions, and O-, V-, and Q-notations. applications and modeling Mathematical topics are best understood when they are seen in a variety of contexts and used to solve problems in a broad range of applied situations. One of the profound lessons of mathematics is that the same mathematical model can be used to solve problems in situations that appear superficially to be totally dissimilar. A goal of this book is to show students the extraordinary practical utility of some very abstract mathematical ideas. Special Features of This Book mathematical reasoning The feature that most distinguishes this book from other dis- crete mathematics texts is that it teaches—explicitly but in a way that is accessible to Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 14 12/11/18 6:53 pm  PrefACe xv first- and second-year college and university students—the unspoken logic and reason- ing that underlie mathematical thought. For many years I taught an intensively interactive transition-to-abstract-mathematics course to mathematics and computer science majors. This experience showed me that while it is possible to teach the majority of students to understand and construct straightforward mathematical arguments, the obstacles to doing so cannot be passed over lightly. To be successful, a text for such a course must address students’ difficulties with logic and language directly and at some length. It must also include enough concrete examples and exercises to enable students to develop the mental models needed to conceptualize more abstract problems. The treatment of logic and proof in this book blends common sense and rigor in a way that explains the essentials, yet avoids overloading students with formal detail. spiral approach to concept development A number of concepts in this book appear in increasingly more sophisticated forms in successive chapters to help students develop the ability to deal effectively with increasing levels of abstraction. For example, by the time students encounter the relatively advanced mathematics of Fermat’s little theorem in Sec- tion 8.4, they have been introduced to the logic of mathematical discourse in Chapters 1, 2, and 3, learned the basic methods of proof and the concepts of mod and div in Chapter 4, explored mod and div as functions in Chapter 7, and become familiar with equivalence relations in Sections 8.2 and 8.3. This approach builds in useful review and develops math- ematical maturity in natural stages. support for the student Students at colleges and universities inevitably have to learn a great deal on their own. Though it is often frustrating, learning to learn through self-study is a crucial step toward eventual success in a professional career. This book has a number of features to facilitate students’ transition to independent learning. Worked Examples The book contains over 500 worked examples, which are written using a problem- solution format and are keyed in type and in difficulty to the exercises. Many solutions for the proof problems are developed in two stages: first a discussion of how one might come to think of the proof or disproof and then a summary of the solution, which is enclosed in a box. This format allows students to read the problem and skip imme- diately to the summary, if they wish, only going back to the discussion if they have trouble understanding the summary. The format also saves time for students who are rereading the text in preparation for an examination. Marginal Notes and Test Yourself Questions Notes about issues of particular importance and cautionary comments to help students avoid common mistakes are included in the margins throughout the book. Questions designed to focus attention on the main ideas of each section are located between the text and the exercises. For convenience, the questions use a fill-in-the-blank format, and the answers are found immediately after the exercises. Exercises The book contains almost 2600 exercises. The sets at the end of each section have been designed so that students with widely varying backgrounds and ability levels will find some exercises they can be sure to do successfully and also some exercises that will challenge them. Solutions for Exercises To provide adequate feedback for students between class sessions, Appendix B con- tains at least one, and often several, complete solutions for every type of exercise Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 15 12/11/18 6:53 pm  xvi PrefACe in the book. A blue exercise number indicates that there is a solution in Appendix B; the letter H is added for a solution that is less than complete. When two or more exercises use the same solution strategy, there is a full solution for the first and ei- ther another full solution or a partial solution for later ones. Exercises with several parts often have an answer and/or hint for one or more of the parts to help students determine whether they are on track so that they can make adjustments if needed. Students are strongly urged not to consult solutions until they have tried their best to answer questions on their own. Once they have done so, however, comparing their answers with those given can lead to significantly improved understanding. There are also plenty of exercises without solutions to help students learn to grapple with math- ematical problems in a realistic environment. Reference Features Many students have written me to say that the book helped them succeed in their ad- vanced courses. One even wrote that he had used one edition so extensively that it had fallen apart, and he actually went out and bought a copy of the next edition, which he was continuing to use in a master’s program. Figures and tables are included where doing so would help readers to a better understanding. In most, a second color is used to highlight meaning. My rationale for screening statements of definitions and theo- rems, for putting titles on exercises, and for giving the meanings of symbols and a list of reference formulas in the endpapers is to make it easier for students to use this book for review in a current course and as a reference in later ones. support for the instructor I have received a great deal of valuable feedback from in- structors who have used previous editions of this book. Many aspects of the book have been improved through their suggestions. In addition to the following items, there is ad- ditional instructor support on the book’s website, described later in the preface. Exercises The large variety of exercises at all levels of difficulty allows instructors great free- dom to tailor a course to the abilities of their students. Exercises with solutions in the back of the book have numbers in blue, and those whose solutions are given in a separate Student Solutions Manual and Study Guide have numbers that are a multiple of three. There are exercises of every type in the book that have no answer in either location so that instructors can assign whatever mixture they prefer of exercises with and without answers. The ample number of exercises of all kinds gives instructors a significant choice of problems to use for review assignments and exams. Instructors are invited to use the many exercises stated as questions rather than in “prove that” form to stimulate class discussion on the role of proof and coun- terexample in problem solving. Flexible Sections Most sections are divided into subsections so that an instructor can choose to cover certain subsections only and either omit the rest or leave them for students to study on their own. The division into subsections also makes it easier for instructors to break up sections if they wish to spend more than one day on them. Presentation of Proof Methods It is inevitable that most of the proofs and disproofs in this book will seem easy to instructors. Many students, however, find them difficult. In showing students how to discover and construct proofs and disproofs, I have tried to describe the kinds of approaches that mathematicians use when confronting challenging problems in their own research. Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 16 12/11/18 6:53 pm  PrefACe xvii Complete Instructor Solutions Complete instructor solutions to all exercises are available to anyone teaching a course from this book. They are available through the Instructor’s Companion Website. Highlights of the Fifth Edition The changes made for this edition are based on suggestions from colleagues and other long-time users of previous editions, on continuing interactions with my students, and on developments within the evolving fields of computer science and mathematics. Reorganization In response to instructor requests to move the introduction of certain topics ear- lier in the book, Section 1.2 now includes a definition and examples of strings. In addition, a new Section 1.4 contains definitions and examples of graphs and includes an introduction to graph coloring and the four-color theorem. The handshake theorem and its applications have been moved from Chapter 10 to Section 4.9. This gives students an early experience of using direct and indirect proof in a novel setting and was made possible because the elements of graph theory are now introduced in Chapter 1. Improved Pedagogy The exposition has been reexamined throughout and carefully revised as needed. Exercises have been added for topics where students seemed to need addi- tional practice, and they have been modified, as needed, to address student difficulties. Additional hints and full answers have been incorporated into Appendix B to give students more help for difficult topics. The introductory material in Chapter 4 was made more accessible by being di- vided into two sections. The first introduces basic concepts about proof and dis- proof in the context of elementary number theory, and the second adds examples and advice for writing proofs. Logic and Applications Discussion was added about the role of bound variables and scope in mathemati- cal writing and computer programming. The section on two’s complements was significantly simplified. Language for expressing universal quantifiers was revised to provide a clearer basis for the idea of the generic particular in mathematical proof. The material on Boolean algebras was expanded. Proof and Applications A greater variety of examples and exercises for number theory and set theory proofs is now included. The directions for writing proofs and the discussion of common mistakes have been revised and expanded in response to interaction with students. Discussion of historical background and recent mathematical results has been augmented. Material was added on using cryptographic hash functions to secure the trans- mission of digital data and on using cryptography to authenticate the sender of a transmitted message. Induction and Recursion The sections on ordinary and strong mathematical induction were reorganized and expanded to increase the emphasis on applications. Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 17 12/11/18 6:53 pm  xviii PrefACe In the section on recursive definitions, the format used for proofs by structural induction was revised to parallel the format used for proofs by ordinary and strong mathematical induction. The set of examples and exercises illustrating recursive definitions and structural induction was significantly increased. The recursive definition for the set of strings over a finite set and for the length of a string were revised, and structural induction proofs for fundamental string prop- erties are now included. Graph Theory and the Analysis of Algorithm Efficiency Instructors who wish to give their students an early experience of graph theory can now do so by combining the introduction to graphs in Chapter 1 with the handshake theorem in Chapter 4. There is a new subsection on binary search trees in Chapter 10. The discussion of O-, V-, and Q-notations was significantly simplified. Many exercises on algorithm efficiency were added or revised to make the con- cepts more accessible. Student Resources The Student Companion Website for this book includes: A general orientation for each chapter Review materials for each chapter Proof tips A link to the author’s personal website, which contains errata information and links for interactive animations, tutorials, and other discrete mathematics resources on the Internet Instructor’s Resources login.cengage.com The Instructor’s Companion Website for this book contains: Suggestions for how to approach the material of each chapter The Complete Instructor’s Solutions Manual Ideas for projects and writing assignments Review materials to share with students Lecture Note PowerPoint slides Images from the book A test bank of questions for exams and quizzes Migration guide from 4th to 5th edition Additional resources for the book are available at http://condor.depaul.edu/sepp. WebAssign www.webassign.com WebAssign from Cengage Discrete Mathematics with Applications, Fifth Edition, is an online homework system, which instructors can choose to pair with the book. For stu- dents, it offers tutorial help in solving exercises, including review of relevant material, short instructional videos, and instant feedback on how they are doing. For instructors, it offers the ability to create customized homework sets, most of which are graded automati- cally and produce results directly into an online grade roster. Real-time access to their Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 18 12/11/18 6:53 pm  PrefACe xix students’ performance makes it possible for instructors to adjust the presentation of mate- rial on an ongoing basis. Student Solutions Manual and Study Guide (ISBN: 978-0-357-03520-7) In writing this book, I hoped that the exposition in the text, the worked examples, and the exercise solutions would provide all that a student would need to successfully master the material of the course. I continue to believe that any student who understands the solutions for all the exercises with complete solutions in Appendix B will have achieved an excellent command of the subject. Nonetheless, in response to requests for supplementary materials, I developed the Student Solutions Manual and Study Guide, available separately from the book, which contains complete solutions for all the exercises whose numbers are a multiple of 3. The guide also includes alternative explanations for some of the concepts and review questions for each chapter. Organization This book may be used effectively for a one- or two-semester course. Chapters contain core sections, sections covering optional mathematical material, and sections covering optional applications. Instructors have the flexibility to choose whatever mixture will best serve the needs of their students. The following table shows a division of the sections into categories. Sections Containing Optional Sections Containing Optional Chapter Core Sections Mathematical Material Computer Science Applications 1 1.1–1.3 1.4 1.4 2 2.1–2.3 2.5 2.4, 2.5 3 3.1–3.4 3.3 3.3 4 4.1–4.5, 4.7 4.6, 4.8, 4.9 4.10 5 5.1, 5.2, 5.6, 5.7 5.3, 5.4, 5.8 5.1, 5.5, 5.9 6 6.1 6.2–6.4 6.1, 6.4 7 7.1, 7.2 7.3, 7.4 7.1, 7.2, 7.4 8 8.1–8.3 8.4, 8.5 8.4, 8.5 9 9.1–9.4 9.5–9.9 9.3 10 10.1, 10.4 10.2, 10.3, 10.5 10.1, 10.4–10.6 11 11.1, 11.2 11.4 11.3, 11.5 12 12.1, 12.2 12.3 12.1–12.3 The following tree diagram shows, approximately, how the chapters of this book depend on each other. Chapters on different branches of the tree are sufficiently independent that instructors need to make at most minor adjustments if they skip chapters, or sections of chapters, but follow paths along branches of the tree. In most cases, covering only the core sections of the chapters is adequate preparation for moving down the tree. Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 19 12/11/18 6:53 pm  xx PrefACe 1 2 3 34 5 6 10 12* 7 8 9 11 Acknowledgments I owe a debt of gratitude to many people at DePaul University for their support and en- couragement throughout the years I worked on editions of this book. A number of my col- leagues used early versions and previous editions and provided many excellent suggestions for improvement. For this, I am thankful to Louis Aquila, J. Marshall Ash, Allan Berele, Jeffrey Bergen, William Chin, Barbara Cortzen, Constantine Georgakis, Sigrun Goes, Jerry Goldman, Lawrence Gluck, Leonid Krop, Carolyn Narasimhan, Walter Pranger, Eric Rieders, Ayse Sahin, Yuen-Fat Wong, and, most especially, Jeanne LaDuke. The thousands of students to whom I have taught discrete mathematics have had a profound influence on the presentation of the material in the book. By sharing their thoughts and thought processes with me, they taught me how to teach them better. I am very grateful for their help. I owe the DePaul University administration, especially deans, Charles Suchar, Michael Mezey, and Richard Meister, a special word of thanks for considering the writing of this book a worthwhile scholarly endeavor. My thanks go to the reviewers for their valuable suggestions for this edition of the book: Naser Al-Hasan, Newberry College; Linda Fosnaugh, Midwestern State Univer- sity; Robert Gessel, University of Akron; Juan Henriquez, University of New Orleans; Amy Hlavacek, Saginaw Valley State University; Kevin Lillis, Saint Ambrose University; Ramón Mata-Toledo, James Madison University; Bin Shao, University of San Francisco; Charles Qiao Zhang, Texas Christian University; and Cathleen Zucco-Teveloff, Rowan University. For their help with previous editions of the book, I am grateful to David Addis, Texas Christian University; Rachel Esselstein, California State University-Monterrey Bay; William Marion, Valparaiso University; Michael McClendon, University of Central Okla- homa; Steven Miller, Brown University; Itshak Borosh, Texas A & M University; Douglas M. Campbell, Brigham Young University; David G. Cantor, University of California at Los Angeles; C. Patrick Collier, University of Wisconsin-Oshkosh; Kevan H. Croteau, Francis Marion University; Irinel Drogan, University of Texas at Arlington; Pablo Echeverria, Camden County College; Henry A. Etlinger, Rochester Institute of Technology; Melvin J. Friske, Wisconsin Lutheran College; William Gasarch, University of Maryland; Ladnor Section 8.3 is needed for Section 12.3 but not for Sections 12.1 and 12.2. * Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 20 12/11/18 6:53 pm  PrefACe xxi Geissinger, University of North Carolina; Jerrold R. Griggs, University of South Carolina; Nancy Baxter Hastings, Dickinson College; Lillian Hupert, Loyola University Chicago; Joseph Kolibal, University of Southern Mississippi; Benny Lo, International Technologi- cal University; George Luger, University of New Mexico; Leonard T. Malinowski, Finger Lakes Community College; John F. Morrison, Towson State Unviersity; Paul Pederson, University of Denver; George Peck, Arizona State University; Roxy Peck, California Poly- technic State University, San Luis Obispo; Dix Pettey, University of Missouri; Anthony Ralston, State University of New York at Buffalo; Norman Richert, University of Houston- Clear Lake; John Roberts, University of Louisville; and George Schultz, St. Petersburg Junior College, Clearwater. Special thanks are due John Carroll, San Diego State Univer- sity; Dr. Joseph S. Fulda; and Porter G. Webster, University of Southern Mississippi; Peter Williams, California State University at San Bernardino; and Jay Zimmerman, Towson University for their unusual thoroughness and their encouragement. I have also benefitted greatly from the suggestions of the many instructors who have generously offered me their ideas for improvement based on their experiences with pre- vious editions of the book, especially Jonathan Goldstine, Pennsylvania State University; David Hecker, St. Joseph’s University; Edward Huff, Northern Virginia Community College; Robert Messer, Albion College; Sophie Quigley, Ryerson University; Piotr Rudnicki, University of Alberta; Anwar Shiek, Dine College; Norton Starr, Amherst College; Eng Wee, National University of Singapore; Doug Hogan, University of Illinois at Chicago; James Vanderhyde, Benedictine University; Ali Shaqlaih, University of North Texas at Dallas; Sam Needham, Diablo Valley College; Mohamed Aboutabl and Ramon A. Mata-Toledo, James Madison University; Larry Russ, Stevens Institute of Technology; Tomas Klos, Delft University; Margaret McQuain, Virginia Polytechnic Institute and State University; J. William Cupp, Indiana Wesleyan University; Jeffrey Mank, Framingham State University; Or Meir, University of Haifa; Audrey Julia Walegwa Mbogho, Pwani University, Kenya; Nariman Ammar, Birzeit University; Joshua T. Guerin, University of Tennessee at Martin; Jici Huang, Montana State University; Jerry Shi, University of Connecticut; Phuc Duong, Ton Duc Thang University, Vietnam; Abdul Rehman Abid, Iqra University, Pakistan; Yogesh More, SUNY Old Westbury; Mark Kaplan, Towson State University; Eric Neufeld, University of Saskatchewan; and Jeremy Tucker, Montana State University. Production of the third edition received valuable assistance from Christopher Novak, University of Michigan, Dearborn, and Ian Crewe, Ascension Collegiate School. For the third and fourth editions I am grateful for the many excellent suggestions for improvement made by Tom Jenkyns, Brock University, and for the fifth edition I am indebted to Roger Lipsett for his knowledgeable and careful attention to detail. I am also extremely grateful for the many appreciative messages I have received from students who have used previous editions of the book. They have inspired me to continue to find ever better ways to meet their needs in this edition, and I thank them for making the effort to contact me. I owe many thanks to the Cengage staff, especially my editors, Laura Gallus, Mona Zeftel, Lynh Pham, and Spencer Arritt, for their thoughtful advice and reassuringly calm direction of the production process, and my previous editors, Dan Seibert, Stacy Green, Robert Pirtle, Barbara Holland, and Heather Bennett, for their encouragement and enthusiasm. The older I get the more I realize the profound debt I owe my own mathematics teach- ers for shaping the way I perceive the subject. My first thanks must go to my husband, Helmut Epp, who, on a high school date (!), introduced me to the power and beauty of the field axioms and the view that mathematics is a subject with ideas as well as formulas and techniques. In my formal education, I am most grateful to Daniel Zelinsky and Ky Fan at Northwestern University and Izaak Wirszup, I. N. Herstein, and Irving Kaplansky at the Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 21 12/11/18 6:53 pm  xxii PrefACe University of Chicago, all of whom, in their own ways, helped lead me to appreciate the elegance, rigor, and excitement of mathematics. To my family, I owe thanks beyond measure. I am grateful to my mother, whose keen interest in the workings of the human intellect started me many years ago on the track that led ultimately to this book, and to my father, whose devotion to the written word has been a constant source of inspiration. I thank my children and grandchildren for their affection and cheerful acceptance of the demands this book has placed on my life. And, most of all, I am grateful to my husband, who for many years has encouraged me with his faith in the value of this project and supported me with his love and his wise advice. Susanna Epp Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-200-203 94193_fm_ptg01.indd 22 12/11/18 6:53 pm  Chapter 1 SPEAKING MATHEMATICALLY Therefore O students study mathematics and do not build without foundations. —Leonardo da Vinci (1452–1519) The aim of this book is to introduce you to a mathematical way of thinking that can serve you in a wide variety of situations. Often when you start work on a mathematical prob- lem, you may have only a vague sense of how to proceed. You may begin by looking at examples, drawing pictures, playing around with notation, rereading the problem to focus on more of its details, and so forth. The closer you get to a solution, however, the more your thinking has to crystallize. And the more you need to understand, the more you need language that expresses mathematical ideas clearly, precisely, and unambiguously. This chapter will introduce you to some of the special language that is a foundation for much mathematical thought, the language of variables, sets, relations, and functions. Think of the chapter like the exercises you would do before an important sporting event. Its goal is to warm up your mental muscles so that you can do your best. 1.1 Variables A variable is sometimes thought of as a mathematical “John Doe” because you can use it as a placeholder when you want to talk about something but either (1) you imagine that it has one or more values but you don’t know what they are, or (2) you want whatever you say about it to be equally true for all elements in a given set, and so you don’t want to be restricted to considering only a particular, concrete value for it. To illustrate the first use, consider asking Is there a number with the following property: doubling it and adding 3 gives the same result as squaring it? In this sentence you can introduce a variable to replace the potentially ambiguous word “it”: Is there a number x with the property that 2x 1 3 5 x2? The advantage of using a variable is that it allows you to give a temporary name to what you are seeking so that you can perform concrete computations with it to help discover its possible values. To emphasize the role of the variable as a placeholder, you might write the following: Is there a number n with the property that 2? n 1 3 5 n 2? The emptiness of the box can help you imagine filling it in with a variety of different val- ues, some of which might make the two sides equal and others o