Susanna Epp Discrete Mathematics Brief Edition 2011 Filetype Pdf

Discrete Mathematics with Applications

Susanna S. Epp

How much do you like this book?

What's the quality of the file?

Download the book for quality assessment

What's the quality of the downloaded files?

Publisher:

Cengage Learning

The file will be sent to your email address. It may take up to 1-5 minutes before you receive it.

The file will be sent to your Kindle account. It may takes up to 1-5 minutes before you received it.

Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.

Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    Australia ● Brazil ● Mexico ● Singapore ● United Kingdom ● United States  discrete mathematics  with applications  FiFth editiON  SUSANNA S. EPP DePaul University  94193_fm_ptg01.indd   1 13/11/18   6:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    © 2020, 2011, 2004 Cengage Learning, Inc.  Unless otherwise noted, all content is © Cengage.  ALL RIGHTS RESERVED. No part of this work covered by the copyright  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  permission of the copyright owner.  For product information and technology assistance, contact us at Cengage  Customer & Sales Support, 1-800-354-9706 or support.cengage.com.  For permission to use material from this text or product,   submit all requests online at www.cengage.com/permissions.   Further permissions questions can be emailed to  permissionrequest@cengage.com.  Library of Congress Control Number: 2018953604  Student Edition:  ISBN: 978-1-337-69419-3  Loose-leaf Edition: ISBN: 978-0-357-03523-8  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  Discrete Mathematics with Applications,  Fifth Edition Susanna S. Epp   Product Director: Mark Santee  Product Manager: Spencer Arritt ;  Learning Designer: Mona Zeftel,   Laura Gallus  Content Manager: Lynh Pham,   Christy Frame  Product Assistant: Amanda Rose  E2E Project Manager: Peggy Buskey  Marketing Manager: Shannon Hawkins,  Giana Manzi  IP Analyst: Reba Frederics  IP Project Manager: Carly Belcher  Production Service: MPS Limited  Compositor: MPS Limited  Designer: Diana Graham  Cover Image: Katherine Gendreau  Photography/Getty Images  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!  94193_fm_ptg01.indd   2 12/11/18   6:52 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    To my husband, Helmut, and my children,   Amanda, Catherine, and Caroline  94193_fm_ptg01.indd   3 12/11/18   6:52 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    STUDY SMARTER Ever wonder if you studied enough? WebAssign from   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   and grading  Know how well you  understand concepts  Watch videos and tutorials  when you're stuck   Perform better on   in-class assignments  Ask your instructor today how you can get   access to WebAssign!   cengage.com/webassign  Know if you're  prepared for class!   93% correlation  between homework  scores and in-class   performance  94193_fm_ptg01.indd   4 13/11/18   4:38 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    v  Speaking Mathematically  1  Variables   1 Using Variables in Mathematical Discourse; Introduction to Universal, Existential,   and Conditional Statements  The Language of Sets   6 The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products; Strings  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  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  The Logic of Compound Statements  37  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  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  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  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   ChApTER  1      1.1  1.2  1.3  1.4  ChApTER  2      2.1  2.2  2.3  2.4  ConTenTS  94193_fm_ptg01.indd   5 13/11/18   6:45 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    vi  ConTenTs  a Circuit That Corresponds to a Given Input/Output Table; Simplifying Combinational  Circuits; NAND and NOR Gates  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  the Logic of Quantified statements  108  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  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  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  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  elementary Number theory and methods  of Proof  160  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  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  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  2.5  ChAPTER  3      3.1  3.2  3.3  3.4  ChAPTER  4      4.1  4.2  4.3  94193_fm_ptg01.indd   6 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    ConTenTs  vii  Direct Proof and Counterexample IV: Divisibility   190 Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique  Factorization of Integers Theorem  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  Direct Proof and Counterexample VI: Floor and Ceiling   211 Definition and Basic Properties; The Floor of ny2   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  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  Application: The handshake Theorem   235 The Total Degree of a Graph; The Handshake Theorem and Consequences; Applications;  Simple Graphs; Complete Graphs; Bipartite Graphs  Application: Algorithms   244 An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division  Algorithm; The Euclidean Algorithm   sequences, mathematical induction,   and recursion  258  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  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  Mathematical Induction II: Applications   289 Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibility  Properties; Proving Inequalities; Trominoes and Other Applications  4.4  4.5  4.6  4.7  4.8  4.9  4.10  ChAPTER  5      5.1  5.2  5.3  94193_fm_ptg01.indd   7 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    viii  ConTenTs  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  Application: Correctness of Algorithms   314 Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of the  Euclidean Theorem  Defining Sequences Recursively   325 Examples of Recursively Defined Sequences; Recursive Definitions of Sum and Product  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  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  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  set theory  377  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)  Properties of Sets   391 Set Identities; Proving Subset Relations and Set Equality; Proving That a Set Is the  Empty Set  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  Boolean Algebras, Russell's Paradox, and the halting Problem   414 Boolean Algebras: Definition and Properties; Russell's Paradox; The Halting Problem   5.4  5.5  5.6  5.7  5.8  5.9  ChAPTER  6      6.1  6.2  6.3  6.4  94193_fm_ptg01.indd   8 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    ConTenTs  ix  Properties of Functions  425  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  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  Composition of Functions   461 Definition and Examples; Composition of One-to-One Functions; Composition of Onto  Functions  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  Properties of relations  487  Relations on Sets   487 Additional Examples of Relations; The Inverse of a Relation; Directed Graph of a  Relation; N-ary Relations and Relational Databases  Reflexivity, Symmetry, and Transitivity   495 Reflexive, Symmetric, and Transitive Properties; Properties of Relations on Infinite Sets;  The Transitive Closure of a Relation  Equivalence Relations   505 The Relation Induced by a Partition; Definition of an Equivalence Relation; Equivalence  Classes of an Equivalence Relation  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  Partial Order Relations   546 Antisymmetry; Partial Order Relations; Lexicographic Order; Hasse Diagrams; Partially  and Totally Ordered Sets; Topological Sorting; An Application; PERT and CPM  ChAPTER  7      7.1  7.2  7.3  7.4  ChAPTER  8      8.1  8.2  8.3  8.4  8.5  94193_fm_ptg01.indd   9 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    x  ConTenTs  counting and Probability  564  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  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  Counting Elements of Disjoint Sets: The Addition Rule   589 The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule  The Pigeonhole Principle   604 Statement and Discussion of the Principle; Applications; Decimal Expansions of  Fractions; Generalized Pigeonhole Principle; Proof of the Pigeonhole Principle  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  r-Combinations with Repetition Allowed   634 Multisets and How to Count Them; Which Formula to Use?  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  Probability Axioms and Expected Value   655 Probability Axioms; Deriving Additional Probability Formulas; Expected Value  Conditional Probability, Bayes' Formula, and Independent Events   662 Conditional Probability; Bayes' Theorem; Independent Events  theory of Graphs and trees  677  Trails, Paths, and Circuits   677 Definitions; Connectedness; Euler Circuits; Hamiltonian Circuits  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  Isomorphisms of Graphs   713 Definition of Graph Isomorphism and Examples; Isomorphic Invariants; Graph  Isomorphism for Simple Graphs  ChAPTER  9      9.1  9.2  9.3  9.4  9.5  9.6  9.7  9.8  9.9  ChAPTER  10  10.1  10.2  10.3  94193_fm_ptg01.indd   10 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    ConTenTs  xi  Trees: Examples and Basic Properties   720 Definition and Examples of Trees; Characterizing Trees  Rooted Trees   732 Definition and Examples of Rooted Trees; Binary Trees and Their Properties; Binary  Search Trees   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  analysis of algorithm efficiency  760  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  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  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  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  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  regular expressions and Finite-state automata  828  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  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   10.4  10.5  10.6  ChAPTER  11  11.1  11.2  11.3  11.4  11.5  ChAPTER  12  12.1  12.2  94193_fm_ptg01.indd   11 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    xii  ConTenTs  Automaton Using Software; Finite-State Automata and Regular Expressions; Regular  Languages  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  Properties of the real Numbers  a-1  solutions and hints to selected exercises  a-4  Index   I-1  12.3  APPENDIx  A      APPENDIx  B      94193_fm_ptg01.indd   12 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    xiii  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.  PreFace  94193_fm_ptg01.indd   13 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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   94193_fm_ptg01.indd   14 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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   94193_fm_ptg01.indd   15 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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.  94193_fm_ptg01.indd   16 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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.  94193_fm_ptg01.indd   17 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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   94193_fm_ptg01.indd   18 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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.  Chapter Core Sections Sections Containing Optional   Mathematical Material Sections Containing Optional   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 inde pendent 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.  94193_fm_ptg01.indd   19 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    xx  PrefACe  34  1  2  33  5  10 12*  6  8  11  7 9  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, Wal ter 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 pro cesses 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, Univer sity of Central Okla- homa; Steven Miller, Brown University; Itshak Borosh, Texas A & M Univer sity; 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 Arling ton; Pablo Echeverria,  Camden County College; Henry A. Etlinger, Rochester Insti tute 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.  94193_fm_ptg01.indd   20 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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 Uni versity 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  Col lege; 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   94193_fm_ptg01.indd   21 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    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  94193_fm_ptg01.indd   22 12/11/18   6:53 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1  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.  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 2x13 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? n13 5  n2?  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 of which might not.  1.1  Chapter 1 SPEAKING  MATHEMATICALLY  94193_ch01_ptg01.indd   1 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    2  CHAPTEr 1 SPEAKING MATHEMATICALLY  In this sense, a variable in a computer program is similar to a mathematical variable  because it creates a location in computer memory (either actual or virtual) into which  values can be placed.  To illustrate the second use of variables, consider the statement   No matter what number might be chosen, if it is greater than 2, then its  square is greater than 4.  In this case introducing a variable to give a temporary name to the (arbitrary) number you  might choose enables you to maintain the generality of the statement, and replacing all in- stances of the word "it" by the name of the variable ensures that possible ambiguity is avoided:  No matter what number n might be chosen, if n is greater than 2, then  n2 is greater than 4.  Writing Sentences Using Variables  Use variables to rewrite the following sentences more formally.  a. Are there numbers with the property that the sum of their squares equals the square of  their sum?  b. Given any real number, its square is nonnegative.  Solution a. Are there numbers a and b with the property that a2 1b2 5 (a1b)2?   Or: Are there numbers a and b such that a2 1b2 5 (a1b)2?   Or: Do there exist any numbers a and b such that a2 1b2 5 (a1b)2?  b. Given any real number r, r2 is nonnegative.   Or: For any real number r, r2 $ 0.   Or: For every real number r, r2 $ 0. ■  Some Important Kinds of Mathematical Statements Three of the most important kinds of sentences in mathematics are universal statements,  conditional statements, and existential statements:  Example 1.1.1  Note In part (a) the  answer is yes. For   instance, a 5 1 and b 5 0   would work. Can you  think of other numbers  that would also work?  A universal statement says that a certain property is true for all elements in a set.  (For example: All positive numbers are greater than zero.)  A conditional statement says that if one thing is true then some other thing also  has to be true. (For example: If 378 is divisible by 18, then 378 is divisible by 6.)  Given a property that may or may not be true, an existential statement says that  there is at least one thing for which the property is true. (For example: There is a  prime number that is even.)  In later sections we will define each kind of statement carefully and discuss all of them  in detail. The aim here is for you to realize that combinations of these statements can be  expressed in a variety of different ways. One way uses ordinary, everyday language and  another expresses the statement using one or more variables. The exercises are designed to  help you start becoming comfortable in translating from one way to another.  94193_ch01_ptg01.indd   2 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.1 VArIAbLES  3  Universal Conditional Statements Universal statements contain some variation of the words "for every" and conditional  statements contain versions of the words "if-then." A universal conditional statement is  a statement that is both universal and conditional. Here is an example:  For every animal a, if a is a dog, then a is a mammal.  One of the most important facts about universal conditional statements is that they can be  rewritten in ways that make them appear to be purely universal or purely conditional. For  example, the previous statement can be rewritten in a way that makes its conditional nature  explicit but its universal nature implicit:  If a is a dog, then a is a mammal.  Or: If an animal is a dog, then the animal is a mammal.  The statement can also be expressed so as to make its universal nature explicit and its  conditional nature implicit:  For every dog a, a is a mammal. Or: All dogs are mammals.  The crucial point is that the ability to translate among various ways of expressing univer- sal conditional statements is enormously useful for doing mathematics and many parts of  computer science.  rewriting a Universal Conditional Statement  Fill in the blanks to rewrite the following statement:  For every real number x, if x is nonzero then x2 is positive.  a. If a real number is nonzero, then its square .  b. For every nonzero real number x, .  c. If x , then .  d. The square of any nonzero real number is .  e. All nonzero real numbers have .  Solution a. is positive  b. x2 is positive  c. is a nonzero real number; x2 is positive  d. positive  e. positive squares (or: squares that are positive) ■  Universal Existential Statements A universal existential statement is a statement that is universal because its first part says  that a certain property is true for all objects of a given type, and it is existential because its  second part asserts the existence of something. For example:  Every real number has an additive inverse.  Example 1.1.2  Note If you introduce x  in the first part of the sen- tence, be sure to include it  in the second part of the  sentence.  Note For a number b to  be an additive inverse for  a number a means that   a1b 5 0.  94193_ch01_ptg01.indd   3 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    4  CHAPTEr 1 SPEAKING MATHEMATICALLY  In this statement the property "has an additive inverse" applies universally to all real num- bers. "Has an additive inverse" asserts the existence of something—an additive inverse— for each real number. However, the nature of the additive inverse depends on the real  number; different real numbers have different additive inverses. Knowing that an additive  inverse is a real number, you can rewrite this statement in several ways, some less formal  and some more formal:*  All real numbers have additive inverses. Or: For every real number r, there is an additive inverse for r. Or:  For every real number r, there is a real number s such that s is an   additive inverse for r.  Introducing names for the variables simplifies references in further discussion. For in- stance, after the third version of the statement you might go on to write: When r is positive,  s is negative, when r is negative, s is positive, and when r is zero, s is also zero.  One of the most important reasons for using variables in mathematics is that it gives you  the ability to refer to quantities unambiguously throughout a lengthy mathematical argu- ment, while not restricting you to consider only specific values for them.  rewriting a Universal Existential Statement  Fill in the blanks to rewrite the following statement: Every pot has a lid.  a. All pots .  b. For every pot P, there is .  c. For every pot P, there is a lid L such that .  Solution a. have lids  b. a lid for P  c. L is a lid for P ■  Existential Universal Statements An existential universal statement is a statement that is existential because its first part  asserts that a certain object exists and is universal because its second part says that the  object satisfies a certain property for all things of a certain kind. For example:  There is a positive integer that is less than or equal to every positive integer.  This statement is true because the number one is a positive integer, and it satisfies the  property of being less than or equal to every positive integer. We can rewrite the statement  in several ways, some less formal and some more formal:  Some positive integer is less than or equal to every positive integer. Or:  There is a positive integer m that is less than or equal to every   positive integer. Or:  There is a positive integer m such that every positive integer is   greater than or equal to m. Or:  There is a positive integer m with the property that for every   positive integer n, m # n.  *A conditional could be used to help express this statement, but we postpone the additional complexity to a  later chapter.  Example 1.1.3  94193_ch01_ptg01.indd   4 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.1 VArIAbLES  5  rewriting an Existential Universal Statement  Fill in the blanks to rewrite the following statement in three different ways:  There is a person in my class who is at least as old as every person in  my class.  a. Some  is at least as old as .  b. There is a person p in my class such that p is .  c. There is a person p in my class with the property that for every person q in my class,  p is .  Solution a. person in my class; every person in my class  b. at least as old as every person in my class  c. at least as old as q ■  Some of the most important mathematical concepts, such as the definition of limit of a  sequence, can only be defined using phrases that are universal, existential, and conditional,  and they require the use of all three phrases "for every," "there is," and "if-then." For  example, if a1, a2, a3, Á is a sequence of real numbers, saying that  the limit of an as n approaches infinity is L  means that  for every positive real number «, there is an integer N such that  for every integer n, if n . N then 2« , an 2L , «.  Example 1.1.4  1. A universal statement asserts that a certain property  is  for .  2. A conditional statement asserts that if one   thing  then some other thing .  3. Given a property that may or may not be true,  an existential statement asserts that  for  which the property is true.  TEST YoUrSELf  answers to test Yourself questions are located at the end of each section.  ExErCISE SET 1.1  Appendix B contains either full or partial solutions to all exercises with blue numbers. When the solution is not complete,  the exercise number has an "H" next to it. A "*" next to an exercise number signals that the exercise is more challenging  than usual. Be careful not to get into the habit of turning to the solutions too quickly. Make every effort to work exercises  on your own before checking your answers. See the Preface for additional sources of assistance and further study.  In each of 1–6, fill in the blanks using a variable or variables  to rewrite the given statement.  1. Is there a real number whose square is 21? a. Is there a real number x such that ? b. Does there exist  such that x2 5 21?  2. Is there an integer that has a remainder of 2 when  it is divided by 5 and a remainder of 3 when it is  divided by 6?  a. Is there an integer n such that n has ? b. Does there exist  such that if n is divided   by 5 the remainder is 2 and if ?  Note: There are integers with this property. Can you  think of one?  3. Given any two distinct real numbers, there is a  real number in between them.  94193_ch01_ptg01.indd   5 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    6  CHAPTEr 1 SPEAKING MATHEMATICALLY  a. Given any two distinct real numbers a and b,  there is a real number c such that c is .  b. For any two ,  such that c is   between a and b.  4. Given any real number, there is a real number that  is greater. a. Given any real number r, there is  s such   that s is . b. For any ,  such that s . r.  5. The reciprocal of any positive real number is positive. a. Given any positive real number r, the reciprocal   of . b. For any real number r, if r is , then . c. If a real number r , then .  6. The cube root of any negative real number is  negative. a. Given any negative real number s, the cube   root of . b. For any real number s, if s is , then . c. If a real number s , then .  7. Rewrite the following statements less formally,  without using variables. Determine, as best as you  can, whether the statements are true or false. a. There are real numbers u and v with the prop-  erty that u1v , u2v. b. There is a real number x such that x2 , x. c. For every positive integer n, n2 $ n. d. For all real numbers a and b, ua1b u # ua u1 ub u.  In each of 8–13, fill in the blanks to rewrite the given  statement.  8. For every object J, if J is a square then J has four  sides. a. All squares . b. Every square .  c. If an object is a square, then it . d. If J , then J . e. For every square J, .  9. For every equation E, if E is quadratic then E has  at most two real solutions. a. All quadratic equations . b. Every quadratic equation . c. If an equation is quadratic, then it . d. If E , then E . e. For every quadratic equation E, .  10. Every nonzero real number has a reciprocal. a. All nonzero real numbers . b. For every nonzero real number r, there is    for r. c. For every nonzero real number r, there is a real   number s such that .  11. Every positive number has a positive square root. a. All positive numbers . b. For every positive number e, there is  for e. c. For every positive number e, there is a positive   number r such that .  12. There is a real number whose product with every  number leaves the number unchanged. a. Some  has the property that its . b. There is a real number r such that the product   of r . c. There is a real number r with the property that   for every real number s, .  13. There is a real number whose product with every  real number equals zero. a. Some  has the property that its . b. There is a real number a such that the product   of a . c. There is a real number a with the property that   for every real number b, .  ANSWErS for TEST YoUrSELf   1. true; all elements of a set 2. is true; also has to be true 3. there is at least one thing  The Language of Sets Á when we attempt to express in mathematical symbols a condition proposed in  words. First, we must understand thoroughly the condition. Second, we must be  familiar with the forms of mathematical expression. —George Polyá (1887–1985)  Use of the word set as a formal mathematical term was introduced in 1879 by Georg  Cantor (1845–1918). For most mathematical purposes we can think of a set intuitively, as   1.2  94193_ch01_ptg01.indd   6 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.2 THE LANGuAGE of SETS  7  Cantor did, simply as a collection of elements. For instance, if C is the set of all countries  that are currently in the United Nations, then the United States is an element of C, and if I  is the set of all integers from 1 to 100, then the number 57 is an element of I.  Set-roster Notation  If S is a set, the notation x [ S means that x is an element of S. The notation x  S   means that x is not an element of S. A set may be specified using the set-roster  notation by writing all of its elements between braces. For example, {1, 2, 3} denotes  the set whose elements are 1, 2, and 3. A variation of the notation is sometimes used  to describe a very large set, as when we write {1, 2, 3, Á , 100} to refer to the set of  all integers from 1 to 100. A similar notation can also describe an infinite set, as when  we write {1, 2, 3, Á } to refer to the set of all positive integers. (The symbol Á is  called an ellipsis and is read "and so forth.")  The axiom of extension says that a set is completely determined by what its elements  are—not the order in which they might be listed or the fact that some elements might be  listed more than once.  Using the Set-roster Notation  a. Let A 5 {1, 2, 3}, B 5 {3, 1, 2}, and C 5 {1, 1, 2, 3, 3, 3}. What are the elements of  A, B, and C? How are A, B, and C related?  b. Is {0} 5  0?  c. How many elements are in the set {1, {1}}?  d. For each nonnegative integer n, let Un 5 {n, 2n}. Find U1, U2, and U0.  Solution a. A, B, and C have exactly the same three elements: 1, 2, and 3. Therefore, A, B, and C   are simply different ways to represent the same set.  b. {0} Þ 0 because {0} is a set with one element, namely 0, whereas 0 is just the symbol  that represents the number zero.  c. The set {1, {1}} has two elements: 1 and the set whose only element is 1.  d. U1 5 {1, 21}, U2 5 {2, 22}, U0 5 {0, 20} 5 {0, 0} 5 {0}. ■  Certain sets of numbers are so frequently referred to that they are given special sym- bolic names. These are summarized in the following table.  Symbol Set  R the set of all real numbers  Z the set of all integers  Q the set of all rational numbers, or quotients of integers  Addition of a superscript 1 or 2 or the letters nonneg indicates that only the positive or  negative or nonnegative elements of the set, respectively, are to be included. Thus R1  denotes the set of positive real numbers, and Znonneg refers to the set of nonnegative  integers: 0, 1, 2, 3, 4, and so forth. Some authors refer to the set of nonnegative integers  as the set of natural numbers and denote it as N. Other authors call only the positive   Example 1.2.1  Note The Z is the first  letter of the German word  for integers, Zahlen. It  stands for the set of all  integers and should not  be used as a shorthand for  the word integer.   When the Symbols R,  Q, and Z are handwrit- ten, they appear as R, Q,  and Z .  94193_ch01_ptg01.indd   7 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    8  CHAPTEr 1 SPEAKING MATHEMATICALLY  integers natural numbers. To prevent confusion, we simply avoid using the phrase natural  numbers in this book.  The set of real numbers is usually pictured as the set of all points on a line, as shown  below. The number 0 corresponds to a middle point, called the origin. A unit of distance is  marked off, and each point to the right of the origin corresponds to a positive real number  found by computing its distance from the origin. Each point to the left of the origin cor- responds to a negative real number, which is denoted by computing its distance from the  origin and putting a minus sign in front of the resulting number. The set of real numbers is  therefore divided into three parts: the set of positive real numbers, the set of negative real  numbers, and the number 0. Note that 0 is neither positive nor negative. Labels are given  for a few real numbers corresponding to points on the line shown below.  –3 –2 –1 0 1 2 3  13 4  1 3  2.6–0.8–Î3 Î25 2  –  The real number line is called continuous because it is imagined to have no holes. The  set of integers corresponds to a collection of points located at fixed intervals along the real  number line. Thus every integer is a real number, and because the integers are all sepa- rated from each other, the set of integers is called discrete. The name discrete mathematics  comes from the distinction between continuous and discrete mathematical objects.  Another way to specify a set uses what is called the set-builder notation.  Set-Builder Notation  Let S denote a set and let P(x) be a property that elements of S may or may not satisfy.  We may define a new set to be the set of all elements x in S such that P(x) is true.  We denote this set as follows:  {x [ S  u   P  (x)}  the set of all such that Q a  Note We read the left- hand brace as "the set of  all" and the vertical line  as "such that." In all oth- er mathematical contexts,  however, we do not use  a vertical line to denote  the words "such that"; we  abbreviate "such that" as  "s. t." or "s. th." or "·]·."  Occasionally we will write {x u  P  (x)} without being specific about where the element x  comes from. It turns out that unrestricted use of this notation can lead to genuine contradic- tions in set theory. We will discuss one of these in Section 6.4 and will be careful to use this  notation purely as a convenience in cases where the set S could be specified if necessary.  Using the Set-Builder Notation  Given that R denotes the set of all real numbers, Z the set of all integers, and Z1 the set of  all positive integers, describe each of the following sets.  a. {x [ R u 22 , x , 5}  b. {x [ Z u 22 , x , 5}  c. {x [ Z1 u 22 , x , 5}  Solution a. {x [ R u 22 , x , 5} is the open interval of real numbers (strictly) between 22 and   5. It is pictured as follows:  –2–3 –1 0 1 2 3 4 5 6 7 8  Example 1.2.2  94193_ch01_ptg01.indd   8 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.2 THE LANGuAGE of SETS  9  b. {x [ Z u 22 , x , 5} is the set of all integers (strictly) between 22 and 5. It is equal  to the set {21, 0, 1, 2, 3, 4}.  c. Since all the integers in Z1 are positive, {x [ Z1 u 22 , x , 5} 5 {1, 2, 3, 4}. ■  Subsets A basic relation between sets is that of subset.  Definition  If A and B are sets, then A is called a subset of B, written A  B, if, and only if, every  element of A is also an element of B.  Symbolically:  A # B means that for every element x, if x [ A then x [ B.  The phrases A is contained in B and B contains A are alternative ways of saying that  A is a subset of B.  It follows from the definition of subset that for a set A not to be a subset of a set B means  that there is at least one element of A that is not an element of B. Symbolically:  A Ü B means that there is at least one element x such that x [ A and x Ó B.  Definition  Let A and B be sets. A is a proper subset of B if, and only if, every element of A is  in B but there is at least one element of B that is not in A.  Subsets  Let A 5 Z1, B 5 {n [ Z u 0 # n # 100}, and C 5 {100, 200, 300, 400, 500}. Evaluate  the truth and falsity of each of the following statements.  a. B # A  b. C is a proper subset of A  c. C and B have at least one element in common  d. C # B  e. C # C  Solution  a. False. Zero is not a positive integer. Thus zero is in B but zero is not in A, and so B Ü A.  b. True. Each element in C is a positive integer and, hence, is in A, but there are elements  in A that are not in C. For instance, 1 is in A and not in C.  c. True. For example, 100 is in both C and B.  d. False. For example, 200 is in C but not in B.  e. True. Every element in C is in C. In general, the definition of subset implies that all  sets are subsets of themselves. ■  Example 1.2.3  94193_ch01_ptg01.indd   9 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    10  CHAPTEr 1 SPEAKING MATHEMATICALLY  Distinction between  and   Which of the following are true statements?  a. 2 [ {1, 2, 3} b. {2} [ {1, 2, 3} c. 2 # {1, 2, 3}  d. {2} # {1, 2, 3} e. {2} # {{1}, {2}} f. {2} [ {{1}, {2}}  Solution Only (a), (d), and (f) are true. For (b) to be true, the set {1, 2, 3} would have to contain the element {2}. But the only   elements of {1, 2, 3} are 1, 2, and 3, and 2 is not equal to {2}. Hence (b) is false. For (c) to be true, the number 2 would have to be a set and every element in the set 2   would have to be an element of {1, 2, 3}. This is not the case, so (c) is false. For (e) to be true, every element in the set containing only the number 2 would have to   be an element of the set whose elements are {1} and {2}. But 2 is not equal to either {1} or  {2}, and so (e) is false. ■  Cartesian Products With the introduction of Georg Cantor's set theory in the late nineteenth century, it  began to seem possible to put mathematics on a firm logical foundation by developing  all of its various branches from set theory and logic alone. A major stumbling block was  how to use sets to define an ordered pair because the definition of a set is unaffected  by the order in which its elements are listed. For example, {a, b} and {b, a} represent  the same set, whereas in an ordered pair we want to be able to indicate which element  comes first.  In 1914 crucial breakthroughs were made by Norbert Wiener (1894–1964), a young  American who had recently received his Ph.D. from Harvard, and the German mathemati- cian Felix Hausdorff (1868–1942). Both gave definitions showing that an ordered pair can  be defined as a certain type of set, but both definitions were somewhat awkward. Finally,  in 1921, the Polish mathematician Kazimierz Kuratowski (1896–1980) published the fol- lowing definition, which has since become standard. It says that an ordered pair is a set of  the form  {{a}, {a, b}}.  This set has elements, {a} and {a, b}. If a Þ b, then the two sets are distinct and a is in both  sets whereas b is not. This allows us to distinguish between a and b and say that a is the  first element of the ordered pair and b is the second element of the pair. If a 5 b, then we  can simply say that a is both the first and the second element of the pair. In this case the set  that defines the ordered pair becomes {{a}, {a, a}}, which equals {{a}}.  However, it was only long after ordered pairs had been used extensively in mathematics  that mathematicians realized that it was possible to define them entirely in terms of sets,  and, in any case, the set notation would be cumbersome to use on a regular basis. The usual  notation for ordered pairs refers to {{a}, {a, b}} more simply as (a, b).  Example 1.2.4  Kazimierz Kuratowski  (1896–1980)  Ar ch  iv eP  L/ Al  am y   St oc  k  Ph  ot o  Notation  Given elements a and b, the symbol (a, b) denotes the ordered pair consisting of  a and b together with the specification that a is the first element of the pair and b  is the second element. Two ordered pairs (a, b) and (c, d) are equal if, and only if,  a 5 c and b 5 d. Symbolically:  (a, b) 5 (c, d) means that a 5 c and b 5 d.  94193_ch01_ptg01.indd   10 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.2 THE LANGuAGE of SETS  11  ordered Pairs  a. Is (1, 2) 5 (2, 1)?  b. Is _3, 510+ 5 _Ï9,  1 2+?  c. What is the first element of (1, 1)?  Solution a. No. By definition of equality of ordered pairs,  (1, 2) 5 (2, 1) if, and only if, 1 5 2 and 2 5 1.  But 1 Þ 2, and so the ordered pairs are not equal.  b. Yes. By definition of equality of ordered pairs,  S3, 510D5SÏ9, 12D if, and only if, 3 5 Ï9 and 510 5 12. Because these equations are both true, the ordered pairs are equal.  c.  In the ordered pair (1, 1), the first and the second elements are both 1. ■  The notation for an ordered n-tuple generalizes the notation for an ordered pair to a set  with any finite number of elements. It also takes both order and multiplicity into account.  Example 1.2.5  Definition  Let n be a positive integer and let x1, x2, Á , xn be (not necessarily distinct) ele- ments. The ordered n-tuple, (x1, x2, . . . , xn), consists of x1, x2, Á , xn together with  the ordering: first x1, then x2, and so forth up to xn. An ordered 2-tuple is called an  ordered pair, and an ordered 3-tuple is called an ordered triple.  Two ordered n-tuples (x1, x2, Á , xn) and (y1, y2, Á , yn) are equal if, and only  if, x1 5 y1, x2 5 y2, Á , and xn 5 yn.  Symbolically:  (x1, x2, Á , xn) 5 (y1, y2, Á , yn) 3 x1 5 y1, x2 5 y2, Á , xn 5 yn.  ordered n-tuples  a. Is (1, 2, 3, 4) 5 (1, 2, 4, 3)?  b. Is _3, (22)2, 12+ 5 _Ï9, 4,  3 6+?  Solution a. No. By definition of equality of ordered 4-tuples,  (1, 2, 3, 4) 5 (1, 2, 4, 3) 3  1 5 1, 2 5 2, 3 5 4, and 4 5 3 But 3 Þ 4, and so the ordered 4-tuples are not equal.  b. Yes. By definition of equality of ordered triples,  S3, (22)2, 12D 5 SÏ9, 4, 36D 3 3 5 Ï9 and (22)2 5 4 and 12 5 36.   Because these equations are all true, the two ordered triples are equal.  ■  Example 1.2.6  94193_ch01_ptg01.indd   11 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    12  CHAPTEr 1 SPEAKING MATHEMATICALLY  Cartesian Products  Let A 5 {x, y}, B 5 {1, 2, 3}, and C 5 {a, b}. a. Find A 3 B.  b. Find B 3 A.  c. Find A 3 A.  d. How many elements are in A 3 B, B 3 A, and A 3 A?  e. Find (A 3 B) 3 C  f. Find A 3 B 3 C  g. Let R denote the set of all real numbers. Describe R 3 R.  Solution a. A 3 B 5 {(x, 1), (y, 1), (x, 2), (y, 2), (x, 3), (y, 3)}  b. B 3 A 5 {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)}  c. A 3 A 5 {(x, x), (x, y), (y, x), (y, y)}  d. A 3 B has 6 elements. Note that this is the number of elements in A times the number  of elements in B. B 3 A has 6 elements, the number of elements in B times the num- ber of elements in A. A 3 A has 4 elements, the number of elements in A times the  number of elements in A.  e. The Cartesian product of A and B is a set, so it may be used as one of the sets making  up another Cartesian product. This is the case for (A 3 B) 3 C.  (A 3 B) 3 C 5 {(u, v)uu [ A 3 B and v [ C} by definition of Cartesian product  5 {((x, 1), a), ((x, 2), a), ((x, 3), a), ((y, 1), a),  ((y, 2), a), ((y, 3), a), ((x, 1), b), ((x, 2), b), ((x, 3), b),  ((y, 1), b), ((y, 2), b), ((y, 3), b)}  f. The Cartesian product A 3 B 3 C is superficially similar to but is not quite the same  mathematical object as (A 3 B) 3 C. (A 3 B) 3 C is a set of ordered pairs of which  one element is itself an ordered pair, whereas A 3 B 3 C is a set of ordered triples. By  definition of Cartesian product,  Example 1.2.7  Note This is why it  makes sense to call a   Cartesian product a  product!  Definition  Given sets A1, A2, Á , An, the Cartesian product of A1, A2, Á , An, denoted   A1 3 A2 3 Á 3 An, is the set of all ordered n-tuples (a1, a2, Á , an) where a1 [ A1, a2 [ A2, Á , an [ An.  Symbolically:  A1 3 A2 3 Á 3 An 5 {(a1, a2, Á , an) u a1 [ A1, a2 [ A2, Á , an [ An}.  In particular,  A1 3 A2 5 {(a1, a2) u  a1 [ A1 and a2 [ A2}  is the Cartesian product of A1 and A2.  94193_ch01_ptg01.indd   12 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.2 THE LANGuAGE of SETS  13  A 3 B 3 C 5 {(u, v, w) u u [ A, v [ B, and w [ Cj   5 {(x, 1, a), (x, 2, a), (x, 3, a), (y, 1, a), (y, 2, a), (y, 3, a), (x, 1, b),  (x, 2, b), (x, 3, b), (y, 1, b), (y, 2, b), (y, 3, b)}.  g. R 3 R is the set of all ordered pairs (x, y) where both x and y are real numbers. If  horizontal and vertical axes are drawn on a plane and a unit length is marked off, then  each ordered pair in R 3 R corresponds to a unique point in the plane, with the first  and second elements of the pair indicating, respectively, the horizontal and vertical  positions of the point. The term Cartesian plane is often used to refer to a plane with  this coordinate system, as illustrated in Figure 1.2.1.   fIGUrE 1.2.1 A Cartesian Plane ■  x  y  1  1  2  3  –2–3–4 –1 –1  –2  –3  2  (1, –2)(–2, –2)  (–3, 2)  (2, 1)  3 4  Another notation, which is important in both mathematics and computer science, denotes  objects called strings.*  Definition  Let n be a positive integer. Given a finite set A, a string of length n over A is an or- dered n-tuple of elements of A written without parentheses or commas. The elements  of A are called the characters of the string. The null string over A is defined to be  the "string" with no characters. It is often denoted l and is said to have length 0. If  A 5 {0, 1}, then a string over A is called a bit string.  Strings  Let A 5 {a, b}. List all the strings of length 3 over A with at least two characters that are  the same.  Solution  aab, aba, baa, aaa, bba, bab, abb, bbb  In computer programming it is important to distinguish among different kinds of data  structures and to respect the notations that are used for them. Similarly in mathematics, it  is important to distinguish among, say, {a, b, c}, {{a, b}, c}, (a, b, c), (a, (b, c)), abc, and so  forth, because these are all significantly different objects. ■  Example 1.2.8  *A more formal definition of string, using recursion, is given in Section 5.9.  94193_ch01_ptg01.indd   13 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    14  CHAPTEr 1 SPEAKING MATHEMATICALLY  1. Which of the following sets are equal?  A 5 {a, b, c, d} B 5 {d, e, a, c}  C 5 {d, b, a, c}  D 5 {a, a, d, e, c, e}  2. Write in words how to read each of the following  out loud. a. {x [ R1 u 0 , x , 1} b. {x [ R u x # 0 or x $ 1} c. {n [ Z u n is a factor of 6} d. {n [ Z1 u n is a factor of 6}  3. a. Is 4 5 {4}? b. How many elements are in the set {3, 4, 3, 5}? c. How many elements are in the set {1, {1}, {1, {1}}}?   4. a. Is 2 [ {2}? b. How many elements are in the set {2, 2, 2, 2}? c. How many elements are in the set {0, {0}}? d. Is {0} [ {{0}, {1}}? e. Is 0 [ {{0}, {1}}?   5. Which of the following sets are equal? A 5 {0, 1, 2}  B 5 {x [ R u 21 # x , 3} C 5 {x [ R u 21 , x , 3} D 5 {x [ Z u 21 , x , 3} E 5 {x [ Z1 u 21 , x , 3}   6. For each integer n, let Tn 5 {n, n 2}. How many    elements are in each of T2, T23, T1, and T0? Justify  your answers.   7. Use the set-roster notation to indicate the elements  in each of the following sets. a. S 5 {n [ Z u n 5 (21)k, for some integer k}. b. T 5 {m [ Z u m 5 11 (21)i, for some integer i}.  c. U 5 {r [ Z u 2 # r # 22} d. V 5 {s [ Z u s . 2 or s , 3} e. W 5 {t [ Z u 1 , t , 23} f. X 5 {u [ Z u u # 4 or u $ 1}   8. Let A 5 {c, d, f, g}, B 5 { f, j}, and C 5 {d, g}.  Answer each of the following questions. Give  reasons for your answers.  a. Is B # A? b. Is C # A? c. Is C # C? d. Is C a proper subset of A?   9. a. Is 3 [ {1, 2, 3}? b. Is 1 # {1}? c. Is {2} [ {1, 2}? d. Is {3} [ {1, {2}, {3}}? e. Is 1 [ {1}? f. Is {2} # {1, {2}, {3}}? g. Is {1} # {1, 2}? h. Is 1 [ {{1}, 2}? i. Is {1} # {1, {2}}? j. Is {1} # {1}?   10. a. Is ((22)2, 222) 5 (222, (22)2)? b. Is (5, 25) 5 (25, 5)? c. Is (8 2 9,Ï3 21) 5 (21, 21)? d. Is _ 2224, (22)  3+ 5 _  36, 28+?   11. Let A 5 {w, x, y, z} and B 5 {a, b}. Use the set- roster notation to write each of the following sets, and  indicate the number of elements that are in each set. a. A 3 B b. B 3 A c. A 3 A d. B 3 B  H  H  1. When the elements of a set are given using the  set-roster notation, the order in which they are  listed .  2. The symbol R denotes .  3. The symbol Z denotes .  4. The symbol Q denotes .  5. The notation {x k P(x)} is read .  6. For a set A to be a subset of a set B means that  .  7. Given sets A and B, the Cartesian product A 3 B is .  8. Given sets A, B, and C, the Cartesian product  A 3 B 3 C is .  9. A string of length n over a set S is an ordered n-tuple  of elements of S, written without  or .  TEST YoUrSELf    ExErCISE SET 1.2   94193_ch01_ptg01.indd   14 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.3 THE LANGuAGE of rELATIoNS ANd fuNCTIoNS  15   12. Let S 5 {2, 4, 6} and T 5 {1, 3, 5}. Use the set- roster notation to write each of the following sets, and  indicate the number of elements that are in each set. a. S 3 T b. T 3 S c. S 3 S d. T 3 T   13. Let A 5 {1, 2, 3}, B 5 {u}, and C 5 {m, n}. Find  each of the following sets. a. A 3 (B 3 C) b. (A 3 B) 3 C c. A 3 B 3 C   14. Let R 5 {a}, S 5 {x, y}, and T 5 {p, q, r}. Find  each of the following sets. a. R 3 (S 3 T) b. (R 3 S) 3 T c. R 3 S 3 T   15. Let S 5 {0, 1}. List all the strings of length 4 over  S that contain three or more 0's.   16. Let T 5 {x, y}. List all the strings of length 5 over  T that have exactly one y.  1. does not matter 2. the set of all real numbers 3. the set  of all integers 4. the set of all rational numbers 5. the set  of all x such that P(x)  6. every element in A is an element   in B 7. the set of all ordered pairs (a, b) where a is in A and  b is in B 8. the set of ordered triples of the form (a, b, c)  where a [ A, b [ B, and c [ C 9. parentheses; commas  ANSWErS for TEST YoUrSELf   The Language of relations and functions Mathematics is a language. —Josiah Willard Gibbs (1839–1903)  There are many kinds of relationships in the world. For instance, we say that two people  are related by blood if they share a common ancestor and that they are related by marriage  if one shares a common ancestor with the spouse of the other. We also speak of the rela- tionship between student and teacher, between people who work for the same employer,  and between people who share a common ethnic background.  Similarly, the objects of mathematics may be related in various ways. A set A may  be said to be related to a set B if A is a subset of B, or if A is not a subset of B, or if A  and B have at least one element in common. A number x may be said to be related to a  number y if x , y, or if x is a factor of y, or if x2 1y2 5 1. Two identifiers in a computer  program may be said to be related if they have the same first eight characters, or if the  same memory location is used to store their values when the program is executed. And  the list could go on!  Let A 5 {0, 1, 2} and B 5 {1, 2, 3} and let us say that an element x in A is related to an  element y in B if, and only if, x is less than y. Let us use the notation x R y as a shorthand  for the sentence "x is related to y." Then  0 R 1 since 0 , 1,  0 R 2 since 0 , 2,  0 R 3 since 0 , 3,  1 R 2 since 1 , 2,  1 R 3 since 1 , 3, and  2 R 3 since 2 , 3.  1.3  94193_ch01_ptg01.indd   15 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    16  CHAPTEr 1 SPEAKING MATHEMATICALLY  On the other hand, if the notation x R y represents the sentence "x is not related to y," then  1 R 1 since 1 ñ 1, 2 R 1 since 2 ñ 1, and 2 R 2 since 2 ñ 2.  Recall that the Cartesian product of A and B, A 3 B, consists of all ordered pairs whose  first element is in A and whose second element is in B:  A 3 B 5 {(x, y) u x [ A and y [ B}.  In this case,  A 3 B 5  h(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)j.  The elements of some ordered pairs in A 3 B are related, whereas the elements of other  ordered pairs are not. Consider the set of all ordered pairs in A 3 B whose elements are  related  h(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)j.  Observe that knowing which ordered pairs lie in this set is equivalent to knowing which  elements are related to which. The relation itself can therefore be thought of as the totality of  ordered pairs whose elements are related by the given condition. The formal mathematical  definition of relation, based on this idea, was introduced by the American mathematician  and logician C. S. Peirce in the nineteenth century.  Definition  Let A and B be sets. A relation R from A to B is a subset of A 3 B. Given an ordered  pair (x, y) in A 3 B, x is related to y by R, written x R y, if, and only if, (x, y) is in R.  The set A is called the domain of R and the set B is called its co-domain.  The notation for a relation R may be written symbolically as follows:  x R y means that (x, y) [ R.  The notation x R y means that x is not related to y by R:  x R y means that (x, y) Ó R.  A relation as a Subset  Let A 5 {1, 2} and B 5 {1, 2, 3} and define a relation R from A to B as follows: Given any  (x, y) [ A 3 B,  (x, y) [ R  means that  x 2 y 2   is an integer.  a. State explicitly which ordered pairs are in A 3 B and which are in R.  b. Is 1 R 3? Is 2 R 3? Is 2 R 2?  c. What are the domain and co-domain of R?  Solution a. A 3 B 5 {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}. To determine explicitly the compo-  sition of R, examine each ordered pair in A 3 B to see whether its elements satisfy the  defining condition for R.  Example 1.3.1  94193_ch01_ptg01.indd   16 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.3 THE LANGuAGE of rELATIoNS ANd fuNCTIoNS  17  (1, 1) [ R because 1 2 12 5 0 2 5 0, which is an integer.  (1, 2) Ó R because 1 2 22 5 21 2 , which is not an integer.  (1, 3) [ R because 1 2 32 5 22 2 5 21, which is an integer.  (2, 1) Ó R because 2 2 12 5 1 2, which is not an integer.  (2, 2) [ R because 2 2 22 5 0 2 5 0, which is an integer.  (2, 3) Ó R because 2 2 32 5 21 2 , which is not an integer.    Thus  R 5 {(1, 1), (1, 3), (2, 2)}  b. Yes, 1 R 3 because (1, 3) [ R.   No, 2 R 3 because (2, 3) Ó R.   Yes, 2 R 2 because (2, 2) [ R.  c. The domain of R is {1, 2} and the co-domain is {1, 2, 3}. ■  The Circle relation  Define a relation C from R to R as follows: For any (x, y) [ R 3 R,  (x, y) [ C means that x2 1y2 5 1. a. Is (1, 0) [ C? Is (0, 0) [ C? Is _212,   Ï3 2+ [ C? Is 22 C 0? Is 0 C (21)? Is 1 C 1?  b. What are the domain and co-domain of C?  c. Draw a graph for C by plotting the points of C in the Cartesian plane.  Solution a. Yes, (1, 0) [ C because 12 102 5 1.   No, (0, 0) Ó C because 02 102 5 0 Þ 1.    Yes, _212,  Ï3  2+ [ C because _2 1 2+2 1 _  Ï3 2 +  2 5 1 4 1  3 4 5 1.    No, 22 C 0 because (22)2 102 5 4 Þ 1.   Yes, 0 C (21) because 02 1 (21)2 5 1.   No, 1 C 1 because 12 112 5 2 Þ 1.  b. The domain and co-domain of C are both R, the set of all real numbers.  c.    x  y  x2 + y2 = 1  1–1  Example 1.3.2  ■  94193_ch01_ptg01.indd   17 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    18  CHAPTEr 1 SPEAKING MATHEMATICALLY  Arrow Diagram of a Relation Suppose R is a relation from a set A to a set B. The arrow diagram for R is obtained as  follows:  1. Represent the elements of A as points in one region and the elements of B as points in  another region.  2. For each x in A and y in B, draw an arrow from x to y if, and only if, x is related to y by  R. Symbolically:  Draw an arrow from x to y  if, and only if, x R y  if, and only if, (x,  y) [ R.  Arrow Diagrams of relations  Let A 5 {1, 2, 3} and B 5 {1, 2, 3} and define relations S and T from A to B as follows:   For every (x, y) [ A 3 B,  (x, y) [ S means that x , y   S is a "less than" relation.  T 5 {(2, 1), (2, 5)}.  Draw arrow diagrams for S and T.  Solution  1  2  3  S 1  3  5  1  2  3  T 1  3  5  These example relations illustrate that it is possible to have several arrows coming out  of the same element of A pointing in different directions. Also, it is quite possible to have  an element of A that does not have an arrow coming out of it. ■  Functions In Section 1.2 we showed that ordered pairs can be defined in terms of sets and we defined  Cartesian products in terms of ordered pairs. In this section we introduced relations as subsets  of Cartesian products. Thus we can now define functions in a way that depends only on the  concept of set. Although this definition is not obviously related to the way we usually work  with functions in mathematics, it is satisfying from a theoretical point of view, and computer  scientists like it because it is particularly well suited for operating with functions on a computer.  Example 1.3.3  Definition  A function F from a set A to a set B is a relation with domain A and co-domain B  that satisfies the following two properties:  1. For every element x in A, there is an element y in B such that (x, y) [ F.  2. For all elements x in A and y and z in B,  if (x, y) [ F and (x, z) [ F, then y 5 z.  94193_ch01_ptg01.indd   18 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    1.3 THE LANGuAGE of rELATIoNS ANd fuNCTIoNS  19  Properties (1) and (2) can be stated less formally as follows: A relation F from A to B is  a function if, and only if:  1. Every element of A is the first element of an ordered pair of F.  2. No two distinct ordered pairs in F have the same first element.  In most mathematical situations we think of a function as sending elements from one  set, the domain, to elements of another set, the co-domain. Because of the definition of  function, each element in the domain corresponds to one and only one element of the  co-domain.  More precisely, if F is a function from a set A to a set B, then given any element x in A,  property (1) from the function definition guarantees that there is at least one element of B  that is related to x by F and property (2) guarantees that there is at most one such element.  This makes it possible to give the element that corresponds to x a special name.  function Notation  If A and B are sets and F is a function from A to B, then given any element x in A, the  unique element in B that is related to x by F is denoted F(x), which is read "F of x."  functions and relations on finite Sets  Let A 5 {2, 4, 6} and B 5 {1, 3, 5}. Which of the relations R, S, and T defined below are  functions from A to B?  a. R 5 {(2, 5), (4, 1), (4, 3), (6, 5)}  b. For every (x, y) [ A 3 B, (x, y) [ S means that y 5 x11.  c. T is defined by the arrow diagram  B  1  3  5  A  2  4  6  Solution a. R is not a function because it does not satisfy property (2). The ordered pairs (4, 1)   and (4, 3) have the same first element but different second elements. You can see this  graphically if you draw the arrow diagram for R. There are two arrows coming out of  4: One points to 1 and the other points to 3.  BR  1  3  5  A  2  4  6  b. S is not a function because it does not satisfy property (1). It is not true that every  element of A is the first element of an ordered pair in S. For example, 6 [ A but there  is no y in B such that y 5 611 5 7. You can also see this graphically by drawing the  arrow diagram for S.  Example 1.3.4  94193_ch01_ptg01.indd   19 12/11/18   3:40 pm  Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.  WCN 02-200-203    20  Chapter 1 SPEAKING MATHEMATICALLY  BS  1  3  5  A  2  4  6  c. T is a function: Each element in {2, 4, 6} is related to some element in {1, 3, 5}, and no  element in {2, 4, 6} is related to more than one element in {1, 3, 5}. When these proper- ties are stated in terms of the arrow diagram, they become (1) there is an arrow coming  out of each element of the domain, and (2) no element of the domain has more than one  arrow coming out of it. So you can write T(2) 5 5,  T(4) 5 1, and T(6) 5 1. ■  Functions and relations on Sets of Strings  Let A 5 {a, b} and let S be the set of all strings over A.  a. Define a relation L from S to Znonneg as follows: For every string s in S and for every  nonnegative integer n,  (s, n) [ L means that the length of s is n.    Observe that L is a function because every string in S has one and only one length.  Find L(abaaba) and L(bbb).  b. Define a relation C from S to S as follows: For all strings s and t in S,  (s, t) [ C means that t 5 as,    where as is the string obtained by appending a on the left of the characters in s. (C is  called concatenation by a on the left.) Observe that C is a function because every  string in S consists entirely of a's and b's and adding an additional a on the left creates  a new strong that also consists of a's and b's and thus is also in S. Find C(abaaba) and  C(bbb).  Solution a. L(abaaba) 5 6 and L(bbb) 5 3  b. C(abaaba) 5 aabaaba and C(bbb) 5 abbb ■  Function Machines Another useful way to think of a function is as a machine. Suppose f is a function from X to  Y and an input x of X is given. Imagine f to be a machine that processes x in a certain way  to produce the output f(x). This is illustrated in Figure 1.3.1.  example 1.3.5  Note In part (c),   T(4) 5 T(6). This illustrates  the fact that although no  element of the domain of a  function can be related to  more than one element of  the co-domain, several ele- ments in the domain can be  related to the same element  in the co-domain.  Figure 1.3.1  function machine  Input x  f (x) Output  94193_ch01_ptg01.indd   20 13/11/18   7:06 pm  Copyright 2020 Ce

Susanna Epp Discrete Mathematics Brief Edition 2011 Filetype Pdf

Source: https://b-ok.global/book/3707224/58a170

Posted by: arcetorepto.blogspot.com

Share this post