Discreat Functions
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
S 50 R 51
1st Pass Pages
1019763_FM_VOL-I.qxp 9/17/07 4:22 PM Page viii
List of Symbols
Subject Symbol Meaning Page
Logic ∼p not p 25 p ∧ q p and q 25 p ∨ q p or q 25 p ⊕ q or p XOR q p or q but not both p and q 28 P ≡ Q P is logically equivalent to Q 30 p→ q if p then q 40 p↔ q p if and only if q 45 ∴ therefore 51 P(x) predicate in x 97
P(x)⇒ Q(x) every element in the truth set for P(x) is in 104 the truth set for Q(x)
P(x)⇔ Q(x) P(x) and Q(x) have identical truth sets 104 ∀ for all 101 ∃ there exists 103
Applications of Logic NOT NOT-gate 67
AND AND-gate 67
OR OR-gate 67
NAND NAND-gate 75
NOR NOR-gate 75
| Sheffer stroke 74
↓ Peirce arrow 74 n2 number written in binary notation 78
n10 number written in decimal notation 78
n16 number written in hexadecimal notation 91
Number Theory and Applications
d | n d divides n 170 d |/ n d does not divide n 172 n div d the integer quotient of n divided by d 181
n mod d the integer remainder of n divided by d 181
�x� the floor of x 191 �x� the ceiling of x 191 |x | the absolute value of x 187 gcd(a, b) the greatest common divisor of a and b 220
x := e x is assigned the value e 214
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Subject Symbol Meaning Page
Sequences . . . and so forth 227 n∑
k=m ak the summation from k equals m to n of ak 230
n∏ k=m
ak the product from k equals m to n of ak 223
n! n factorial 237 Set a ∈ A a is an element of A 7 Theory a /∈ A a is not an element of A 7
{a1, a2, . . . , an} the set with elements a1, a2, . . . , an 7 {x ∈ D | P(x)} the set of all x in D for which P(x) is true 8 R,R−,R+,Rnonneg the sets of all real numbers, negative real 7, 8
numbers, positive real numbers, and nonnegative real numbers
Z,Z−,Z+,Znonneg the sets of all integers, negative integers, 7, 8 positive integers, and nonnegative integers
Q,Q−,Q+,Qnonneg the sets of all rational numbers, negative 7, 8 rational numbers, positive rational numbers, and nonnegative rational numbers
N the set of natural numbers 8
A ⊆ B A is a subset of B 9 A �⊆ B A is not a subset of B 9 A = B A equals B 339 A ∪ B A union B 341 A ∩ B A intersect B 341 B − A the difference of B minus A 341 Ac the complement of A 341
(x, y) ordered pair 11
(x1, x2, . . . , xn) ordered n-tuple 346
A × B the Cartesian product of A and B 12 A1 × A2 × · · · × An the Cartesian product of A1, A2, . . . , An 347 ∅ the empty set 361 P(A) the power set of A 346
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
List of Symbols
Subject Symbol Meaning Page
Counting and N (A) the number of elements in set A 518 Probability P(A) the probability of a set A 518
P(n, r) the number of r -permutations of a set of 553 n elements(n
r
) n choose r , the number of r -combinations 566 of a set of n elements, the number of r -element subsets of a set of n elements
[xi1 , xi2 , . . . , xir ] multiset of size r 584 P(A | B) the probability of A given B 612
Functions f : X → Y f is a function from X to Y 384 f (x) the value of f at x 384
x f→y f sends x to y 384
f (A) the image of A 397
f −1(C) the inverse image of C 397
Ix the identity function on X 387
bx b raised to the power x 405, 406
expb(x) b raised to the power x 405, 406
logb(x) logarithm with base b of x 388
F−1 the inverse function of F 411
f ◦ g the composition of g and f 417 Algorithm x ∼= y x is approximately equal to y 237 Efficiency O( f (x)) big-O of f of x 727
�( f (x)) big-Omega of f of x 727
�( f (x)) big-Theta of f of x 727
Relations x R y x is related to y by R 14
R−1 the inverse relation of R 444
m ≡ n (mod d) m is congruent to n modulo d 473 [a] the equivalence class of a 465 x � y x is related to y by a partial order relation � 502
Continued on first page of back endpapers.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
DISCRETE MATHEMATICS
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
DISCRETE MATHEMATICS WITH APPLICATIONS
FOURTH EDITION
SUSANNA S. EPP DePaul University
Australia · Brazil · Japan · Korea ·Mexico · Singapore · Spain · United Kingdom · United States
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
S 50 R 51
1st Pass Pages
1019763_FM_VOL-I.qxp 9/17/07 4:22 PM Page viii
52609_00_fm_pi-pxxvi.indd ii52609_00_fm_pi-pxxvi.indd ii 2/1/10 11:37:43 PM2/1/10 11:37:43 PM
This is an electronic version of the print textbook. Due to electronic rights
restrictions, some third party content may be suppressed. Editorial review has deemed that any suppres ed content does not materially
affect the overall learning experience. The publisher reserves the right to remove content from this title at any time if subsequent rights restrictions require it. For valuable information on pricing, previous editions, changes to current editions, and alternate formats, please visit www.cengage.com/highered to search by ISBN#, author, title, or keyword for materials in your areas of interest.
s
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
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!
DiscreteMathematics with Applications, Fourth Edition Susanna S. Epp
Publisher: Richard Stratton
Senior Sponsoring Editor: Molly Taylor
Associate Editor: Daniel Seibert
Editorial Assistant: Shaylin Walsh
Associate Media Editor: Andrew Coppola
Senior Marketing Manager: Jennifer Pursley Jones
Marketing Communications Manager: Mary Anne Payumo
Marketing Coordinator: Erica O’Connell
Content Project Manager: Alison Eigel Zade
Senior Art Director: Jill Ort
Senior Print Buyer: Diane Gibbons
Right Acquisition Specialists: Timothy Sisler and Don Schlotman
Production Service: Elm Street Publishing Services
Photo Manager: Chris Althof, Bill Smith Group
Cover Designer: Hanh Luu
Cover Image: GettyImages.com (Collection: OJO Images, Photographer: Martin Barraud)
Compositor: Integra Software Services Pvt. Ltd.
c© 2011, 2004, 1995 Brooks/Cole Cengage Learning ALL RIGHTS RESERVED. No part of this work covered by the copyright herein may be reproduced, transmitted, stored, or used in any form or by any means graphic, electronic, or mechanical, including but not limited to photocopying, recording, scanning, digitizing, taping, Web distribution, information networks, or information storage and retrieval systems, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the publisher.
For product information and technology assistance, contact us at Cengage Learning Customer & Sales Support, 1-800-354-9706.
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: 2010927831
Student Edition: ISBN-13: 978-0-495-39132-6 ISBN-10: 0-495-39132-8
Brooks/Cole 20 Channel Center Street Boston, MA 02210 USA
Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil, and Japan. Locate your local office at: international.cengage.com/region.
Cengage Learning products are represented in Canada by Nelson Education, Ltd.
For your course and learning solutions, visit www.cengage.com
Purchase any of our products at your local college store or at our preferred online store www.cengagebrain.com.
Printed in Canada 1 2 3 4 5 6 7 14 13 12 11 10
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
To Jayne and Ernest
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
vi
CONTENTS
Chapter 1 Speaking Mathematically 1
1.1 Variables 1 Using Variables in Mathematical Discourse; Introduction to Universal, Existential, and Conditional Statements
1.2 The Language of Sets 6 The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products
1.3 The Language of Relations and Functions 13 Definition of a Relation from One Set to Another; Arrow Diagram of a Relation; Definition of Function; Function Machines; Equality of Functions
Chapter 2 The Logic of Compound Statements 23
2.1 Logical Form and Logical Equivalence 23 Statements; Compound Statements; Truth Values; Evaluating the Truth of More Gen- eral Compound Statements; Logical Equivalence; Tautologies and Contradictions; Summary of Logical Equivalences
2.2 Conditional Statements 39 Logical Equivalences Involving →; Representation of If-Then As Or; The Nega- tion of a Conditional Statement; The Contrapositive of a Conditional Statement; The Converse and Inverse of a Conditional Statement; Only If and the Biconditional; Necessary and Sufficient Conditions; Remarks
2.3 Valid and Invalid Arguments 51 Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of Inference
2.4 Application: Digital Logic Circuits 64 Black Boxes and Gates; The Input/Output Table for a Circuit; The Boolean Expres- sion Corresponding to a Circuit; The Circuit Corresponding to a Boolean Expres- sion; Finding a Circuit That Corresponds to a Given Input/Output Table; Simplifying Combinational Circuits; NAND and NOR Gates
2.5 Application: Number Systems and Circuits for Addition 78 Binary Representation of Numbers; Binary Addition and Subtraction; Circuits for Computer Addition; Two’s Complements and the Computer Representation of
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Contents vii
Negative Integers; 8-Bit Representation of a Number; Computer Addition with Negative Integers; Hexadecimal Notation
Chapter 3 The Logic of Quantified Statements 96
3.1 Predicates and Quantified Statements I 96 The Universal Quantifier: ∀; The Existential Quantifier: ∃; Formal Versus Informal Language; Universal Conditional Statements; Equivalent Forms of Universal and Existential Statements; Implicit Quantification; Tarski’s World
3.2 Predicates and Quantified Statements II 108 Negations of Quantified Statements; Negations of Universal Conditional Statements; The Relation among ∀, ∃, ∧, and ∨; Vacuous Truth of Universal Statements; Variants of Universal Conditional Statements; Necessary and Sufficient Conditions, Only If
3.3 Statements with Multiple Quantifiers 117 Translating from Informal to Formal Language; Ambiguous Language; Negations of Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation; Prolog
3.4 Arguments with Quantified Statements 132 Universal Modus Ponens; Use of Universal Modus Ponens in a Proof; Universal Modus Tollens; Proving Validity of Arguments with Quantified Statements; Using Diagrams to Test for Validity; Creating Additional Forms of Argument; Remark on the Converse and Inverse Errors
Chapter 4 Elementary Number Theory and Methods of Proof 145
4.1 Direct Proof and Counterexample I: Introduction 146 Definitions; Proving Existential Statements; Disproving Universal Statements by Counterexample; Proving Universal Statements; Directions for Writing Proofs of Universal Statements; Variations among Proofs; Common Mistakes; Getting Proofs Started; Showing That an Existential Statement Is False; Conjecture, Proof, and Disproof
4.2 Direct Proof and Counterexample II: Rational Numbers 163 More on Generalizing from the Generic Particular; Proving Properties of Rational Numbers; Deriving New Mathematics from Old
4.3 Direct Proof and Counterexample III: Divisibility 170 Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique Factorization of Integers Theorem
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
viii Contents
4.4 Direct Proof and Counterexample IV: Division into Cases and the Quotient-Remainder Theorem 180 Discussion of the Quotient-Remainder Theorem and Examples; div and mod; Alter- native Representations of Integers and Applications to Number Theory; Absolute Value and the Triangle Inequality
4.5 Direct Proof and Counterexample V: Floor and Ceiling 191 Definition and Basic Properties; The Floor of n/2
4.6 Indirect Argument: Contradiction and Contraposition 198 Proof by Contradiction; Argument by Contraposition; Relation between Proof by Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool
4.7 Indirect Argument: Two Classical Theorems 207 The Irrationality of
√ 2; Are There Infinitely Many Prime Numbers?; When to Use
Indirect Proof; Open Questions in Number Theory
4.8 Application: Algorithms 214 An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division Algorithm; The Euclidean Algorithm
Chapter 5 Sequences, Mathematical Induction, and Recursion 227
5.1 Sequences 227 Explicit Formulas for Sequences; Summation Notation; Product Notation; Properties of Summations and Products; Change of Variable; Factorial and n Choose r Notation; Sequences in Computer Programming; Application: Algorithm to Convert from Base 10 to Base 2 Using Repeated Division by 2
5.2 Mathematical Induction I 244 Principle of Mathematical Induction; Sum of the First n Integers; Proving an Equal- ity; Deducing Additional Formulas; Sum of a Geometric Sequence
5.3 Mathematical Induction II 258 Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibil- ity Properties; Proving Inequalities; A Problem with Trominoes
5.4 Strong Mathematical Induction and the Well-Ordering Principle for the Integers 268 StrongMathematical Induction;Binary Representation of Integers;TheWell-Ordering Principle for the Integers
5.5 Application: Correctness of Algorithms 279 Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of the Euclidean Theorem
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Contents ix
5.6 Defining Sequences Recursively 290 Definition of Recurrence Relation; Examples of Recursively Defined Sequences; Recursive Definitions of Sum and Product
5.7 Solving Recurrence Relations by Iteration 304 The Method of Iteration; Using Formulas to Simplify Solutions Obtained by Itera- tion; Checking the Correctness of a Formula byMathematical Induction; Discovering That an Explicit Formula Is Incorrect
5.8 Second-Order Linear Homogenous Recurrence Relations with Constant Coefficients 317 Derivation of a Technique for Solving These Relations; The Distinct-Roots Case; The Single-Root Case
5.9 General Recursive Definitions and Structural Induction 328 Recursively Defined Sets; Using Structural Induction to Prove Properties about Recursively Defined Sets; Recursive Functions
Chapter 6 Set Theory 336
6.1 Set Theory: Definitions and the Element Method of Proof 336 Subsets; Proof and Disproof; Set Equality; Venn Diagrams; Operations on Sets; The Empty Set; Partitions of Sets; Power Sets; Cartesian Products; An Algorithm to Check Whether One Set Is a Subset of Another (Optional)
6.2 Properties of Sets 352 Set Identities; Proving Set Identities; Proving That a Set Is the Empty Set
6.3 Disproofs, Algebraic Proofs, and Boolean Algebras 367 Disproving an Alleged Set Property; Problem-Solving Strategy; The Number of Sub- sets of a Set; “Algebraic” Proofs of Set Identities
6.4 Boolean Algebras, Russell’s Paradox, and the Halting Problem 374 Boolean Algebras; Description of Russell’s Paradox; The Halting Problem
Chapter 7 Functions 383
7.1 Functions Defined on General Sets 383 Additional Function Terminology; More Examples of Functions; Boolean Functions; Checking Whether a Function Is Well Defined; Functions Acting on Sets
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
x Contents
7.2 One-to-One and Onto, Inverse Functions 397 One-to-One Functions; One-to-One Functions on Infinite Sets; Application: Hash Functions; Onto Functions; Onto Functions on Infinite Sets; Relations between Expo- nential and Logarithmic Functions; One-to-One Correspondences; Inverse Functions
7.3 Composition of Functions 416 Definition and Examples; Composition of One-to-One Functions; Composition of Onto Functions
7.4 Cardinality with Applications to Computability 428 Definition of Cardinal Equivalence; Countable Sets; The Search for Larger Infinities: The Cantor Diagonalization Process; Application: Cardinality and Computability
Chapter 8 Relations 442
8.1 Relations on Sets 442 Additional Examples of Relations; The Inverse of a Relation; Directed Graph of a Relation; N -ary Relations and Relational Databases
8.2 Reflexivity, Symmetry, and Transitivity 449 Reflexive, Symmetric, and Transitive Properties; Properties of Relations on Infinite Sets; The Transitive Closure of a Relation
8.3 Equivalence Relations 459 The Relation Induced by a Partition; Definition of an Equivalence Relation; Equiva- lence Classes of an Equivalence Relation
8.4 Modular Arithmetic with Applications to Cryptography 478 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?; Additional Remarks on Number Theory and Cryptography
8.5 Partial Order Relations 498 Antisymmetry; Partial Order Relations; Lexicographic Order; Hasse Diagrams; Partially and Totally Ordered Sets; Topological Sorting; An Application; PERT and CPM
Chapter 9 Counting and Probability 516
9.1 Introduction 517 Definition of Sample Space and Event; Probability in the Equally Likely Case; Count- ing the Elements of Lists, Sublists, and One-Dimensional Arrays
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Contents xi
9.2 Possibility Trees and the Multiplication Rule 525 Possibility Trees; The Multiplication Rule; When the Multiplication Rule Is Difficult or Impossible to Apply; Permutations; Permutations of Selected Elements
9.3 Counting Elements of Disjoint Sets: The Addition Rule 540 The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule
9.4 The Pigeonhole Principle 554 Statement and Discussion of the Principle; Applications; Decimal Expansions of Fractions; Generalized Pigeonhole Principle; Proof of the Pigeonhole Principle
9.5 Counting Subsets of a Set: Combinations 565 r -Combinations; Ordered and Unordered Selections; Relation between Permutations and Combinations; Permutation of a Set with Repeated Elements; Some Advice about Counting; The Number of Partitions of a Set into r Subsets
9.6 r-Combinations with Repetition Allowed 584 Multisets and How to Count Them; Which Formula to Use?
9.7 Pascal’s Formula and the Binomial Theorem 592 Combinatorial Formulas; Pascal’s Triangle; Algebraic and Combinatorial Proofs of Pascal’s Formula; The Binomial Theorem and Algebraic and Combinatorial Proofs for It; Applications
9.8 Probability Axioms and Expected Value 605 Probability Axioms; Deriving Additional Probability Formulas; Expected Value
9.9 Conditional Probability, Bayes’ Formula, and Independent Events 611 Conditional Probability; Bayes’ Theorem; Independent Events
Chapter 10 Graphs and Trees 625
10.1 Graphs: Definitions and Basic Properties 625 Basic Terminology and Examples of Graphs; Special Graphs; The Concept of Degree
10.2 Trails, Paths, and Circuits 642 Definitions; Connectedness; Euler Circuits; Hamiltonian Circuits
10.3 Matrix Representations of Graphs 661 Matrices; Matrices and Directed Graphs; Matrices and Undirected Graphs; Matrices and Connected Components; Matrix Multiplication; Counting Walks of Length N
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
xii Contents
10.4 Isomorphisms of Graphs 675 Definition of Graph Isomorphism and Examples; Isomorphic Invariants; Graph Isomorphism for Simple Graphs
10.5 Trees 683 Definition and Examples of Trees; Characterizing Trees
10.6 Rooted Trees 694 Definition and Examples of Rooted Trees; Binary Trees and Their Properties
10.7 Spanning Trees and Shortest Paths 701 Definition of a Spanning Tree; Minimum Spanning Trees; Kruskal’s Algorithm; Prim’s Algorithm; Dijkstra’s Shortest Path Algorithm
Chapter 11 Analysis of Algorithm Efficiency 717
11.1 Real-Valued Functions of a Real Variable and Their Graphs 717 Graph of a Function; Power Functions; The Floor Function; Graphing Functions Defined on Sets of Integers; Graph of a Multiple of a Function; Increasing and Decreasing Functions
11.2 O-, �-, and �-Notations 725 Definition and General Properties of O-, �-, and �-Notations; Orders of Power Functions; Orders of Polynomial Functions; Orders for Functions of Integer Vari- ables; Extension to Functions Composed of Rational Power Functions
11.3 Application: Analysis of Algorithm Efficiency I 739 Computing Orders of Simple Algorithms; The Sequential Search Algorithm; The Insertion Sort Algorithm; Time Efficiency of an Algorithm
11.4 Exponential and Logarithmic Functions: Graphs and Orders 751 Graphs of Exponential and Logarithmic Functions; Application: Number of Bits Needed to Represent an Integer in Binary Notation; Application: Using Logarithms to Solve Recurrence Relations; Exponential and Logarithmic Orders
11.5 Application: Analysis of Algorithm Efficiency II 764 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
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Contents xiii
Chapter 12 Regular Expressions and Finite-State Automata 779
12.1 Formal Languages and Regular Expressions 780 Definitions and Examples of Formal Languages and Regular Expressions; The Lan- guage Defined by a Regular Expression; Practical Uses of Regular Expressions
12.2 Finite-State Automata 791 Definition of a Finite-State Automaton; The Language Accepted by an Automa- ton; The Eventual-State Function; Designing a Finite-State Automaton; Simulating a Finite-State Automaton Using Software; Finite-State Automata and Regular Expres- sions; Regular Languages
12.3 Simplifying Finite-State Automata 808
*-Equivalence of States; k-Equivalence of States; Finding the *-Equivalence Classes; TheQuotientAutomaton;Constructing theQuotientAutomaton; EquivalentAutomata
Appendix A Properties of the Real Numbers A-1
Appendix B Solutions and Hints to Selected Exercises A-4
Index I-1
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
xiv
PREFACE
My purpose in writing this book was to provide a clear, accessible treatment of discrete mathematics for students majoring or minoring in computer science, mathematics, math- ematics education, and engineering. The goal of the book is to lay the mathematical foundation for computer science courses such as data structures, algorithms, relational database theory, automata theory and formal languages, compiler design, and cryptog- raphy, 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 applica- tions 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 students 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 Amer- ica, 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 under- stood 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 con- tinuing 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.
Logic and Proof Probably the most important goal of a first course in discrete math- ematics 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
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Preface xv
argument 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 recur- sively 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 problem. 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 mathematical induction.
Discrete Structures Discrete mathematical structures are the abstract structures that describe, categorize, and reveal the underlying relationships among discrete mathemat- ical 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 mid- dle 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 algo- rithm 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. Determining whether or not an algorithm is correct requires a sophisticated use of mathematical induction. Calculating the amount of time or memory space the algo- rithm will need in order to compare it to other algorithms that produce the same output requires knowledge of combinatorics, recurrence relations, functions, and O-, �-, and �-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 discrete mathematics texts is that it teaches—explicitly but in a way that is accessible to first- and second-year college and university students—the unspoken logic and reasoning 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
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
xvi Preface
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 Section 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 mathematical 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 immediately 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 a large number of complete solutions to exercises. Students are strongly urged not to consult solutions until they have tried their best to answer the questions on their own. Once they have done so, however, comparing their answers with those given can lead to significantly improved understanding. In addition, many problems, including some of the most challenging, have partial solutions or hints so that students can determine whether they are on the right track and make adjustments if necessary.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Preface xvii
There are also plenty of exercises without solutions to help students learn to grapple with mathematical problems in a realistic environment.
Reference Features Many students have written me to say that the book helped them succeed in their advanced 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 theorems, 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 instructors 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 additional 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 multi- ple of three. There are exercises of every type that are represented in this book that have no answer in either location to enable instructors to 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 assign- ments 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 counterexample in problem solving.
Flexible Sections Most sections are divided into subsections so that an instructor who is pressed for time can choose to cover certain subsections only and either omit the rest or leave them for the 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 then one day on them.
Presentation of Proof Methods It is inevitable that 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.
Instructor Solutions Complete instructor solutions to all exercises are available to anyone teaching a course from this book via Cengage’s Solution Builder service. Instructors can sign up for access at www.cengage.com/solutionbuilder.
Highlights of the Fourth 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.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
xviii Preface
Reorganization A new Chapter 1 introduces students to some of the precise language that is a foun- dation for much mathematical thought: the language of variables, sets, relations, and functions. In response to requests from some instructors, core material is now placed together in Chapter 1–8, with the chapter on recursion now joined to the chapter on induction. Chapters 9–12 were placed together at the end because, although many instructors cover one or more of them, there is considerable diversity in their choices, with some of the topics from these chapters being included in other courses.
Improved Pedagogy
• The number of exercises has been increased to almost 2600. Approximately 300 new exercises have been added.
• Exercises have been added for topics where students seemed to need additional practice, and they have been modified, as needed, to address student difficulties.
• Additional full answers have been incorporated into Appendix B to give students more help for difficult topics.
• The exposition has been reexamined throughout and revised where needed. • Discussion of historical background and recent results has been expanded and the number of photographs of mathematicians and computer scientists whose contribu- tions are discussed in the book has been increased.
Logic and Set theory
• The definition of sound argument is now included, and there is additional clarifica- tion of the difference between a valid argument and a true conclusion.
• Examples and exercises about trailing quantifiers have been added. • Definitions for infinite unions and intersections have been incorporated. Introduction to Proof
• The directions for writing proofs and the discussion of common mistakes have been expanded.
• The descriptions of methods of proof have been made clearer. • Exercises have been revised and/or relocated to promote the development of student understanding.
Induction and Recursion
• The format for outlining proofs by mathematical induction has been improved. • The subsections in the section on sequences have been reorganized. • The sets of exercises for the sections on strong mathematical induction and the well-ordering principle and on recursive definitions have been expanded.
• Increased attention has been given to structural induction. Number Theory
• A subsection on open problems in number theory has been expanded and includes additional discussion of recent mathematical discoveries in number theory.
• The presentation in the section on modular arithmetic and cryptography has been streamlined.
• The discussion of testing for primality has been clarified.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Preface xix
Combinatorics and Discrete Probability
• The discussion of the pigeonhole principle has been moved to this chapter. Functions
• There is increased coverage of functions of more than one variable and of functions acting on sets.
Graph Theory
• The terminology about traveling in a graph has been updated. • Dijkstra’s shortest path algorithm is now included. • Exercises were added to introduce students to graph coloring.
Companion Website www.cengage.com/math/epp
A website has been developed for this book that contains information and materials for both students and instructors. It includes:
• descriptions and links to many sites on the Internet with accessible information about discrete mathematical topics,
• links to applets that illustrate or provide practice in the concepts of discrete mathe- matics,
• additional examples and exercises with solutions, • review guides for the chapters of the book. A special section for instructors contains:
• suggestions about how to approach the material of each chapter, • solutions for all exercises not fully solved in Appendix B, • ideas for projects and writing assignments, • PowerPoint slides, • review sheets and additional exercises for quizzes and exams.
Student Solutions Manual and Study Guide (ISBN-10: 0-495-82613-8; ISBN-13: 978-0-495-82613-2)
In writing this book, I strove to give sufficient help to students through the exposition in the text, the worked examples, and the exercise solutions, so that the book itself would provide all that a student would need to successfully master the material of the course. I believe that students who finish the study of this book with the ability to solve, on their own, all the exercises with full solutions in Appendix B will have developed an excellent command of the subject. Nonetheless, I became aware that some students wanted the opportunity to obtain additional helpful materials. In response, I developed a Student Solutions Manual and Study Guide, available separately from this book, which contains complete solutions to every exercise that is not completely answered in Appendix B and whose number is divisible by 3. The guide also includes alternative explanations for some of the concepts and review questions for each chapter.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
xx Preface
Organization This book may be used effectively for a one- or two-semester course. Chapters contain core sections, sections covering optional mathematical material, and sections covering optional applications. Instructors have the flexibility to choose whatever mixture will best serve the needs of their students. The following table shows a division of the sections into categories.
Sections Containing Optional Sections Containing Optional Chapter Core Sections Mathematical Material Computer Science Applications
1 1.1–1.3
2 2.1–2.3 2.5 2.4, 2.5
3 3.1–3.4 3.3 3.3
4 4.1–4.4, 4.6 4.5, 4.7 4.8
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.5 10.2–10.4, 10.6 10.1, 10.2, 10.5–10.7
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 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.
34
1
2
33
5
10 12*
6
8
11
7 9
∗Section 8.3 is needed for Section 12.3 but not for Sections 12.1 and 12.2.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Preface xxi
Acknowledgments I owe a debt of gratitude to many people at DePaul University for their support and encouragement throughout the years I worked on editions of this book. A number of my colleagues 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 book’s form. 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 my dean, Charles Suchar, and my former deans, Michael Mezey and Richard Meister, a special word of thanks for considering the writing of this book a worthwhile scholarly endeavor.
My thanks to the reviewers for their valuable suggestions for this edition of the book: David Addis, Texas Christian University; Rachel Esselstein, California State University- Monterrey Bay; William Marion, Valparaiso University; Michael McClendon, Univer- sity of Central Oklahoma; and Steven Miller, Brown University. For their help with previous editions of the book, I am grateful to 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 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 Technological 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 Polytechnic 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 University; 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 Rud- nicki, University of Alberta; Anwar Shiek, Diné College; Norton Starr, Amherst College; and Eng Wee, National University of Singapore. 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 especially grateful for the many excellent suggestions for improvement made by Tom Jenkyns, Brock University, whose assistance throughout the production process was invaluable.
I owe many thanks to the Brooks/Cole staff, especially my editor, Dan Seibert, for his thoughtful advice and reassuringly calm direction of the production process, and my
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
xxii Preface
previous editors, 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 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 late father, whose devotion to the written word has been a constant source of inspiration. I thank my children and grandchildren for their affection and cheerful acceptance of the demands this book has placed on my life. And, most of all, I am grateful to my husband, who for many years has encouraged me with his faith in the value of this project and supported me with his love and his wise advice.
Susanna Epp
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
1
CHAPTER 1
SPEAKING MATHEMATICALLY
Therefore O students study mathematics and do not build without foundations. —Leonardo da Vinci (1452–1519)
The aim of this book is to introduce you to a mathematical way of thinking that can serve you in a wide variety of situations. Often when you start work on a mathematical problem, you may have only a vague sense of how to proceed. You may begin by looking at examples, drawing pictures, playing around with notation, rereading the problem to focus on more of its details, and so forth. The closer you get to a solution, however, the more your thinking has to crystallize. And the more you need to understand, the more you need language that expresses mathematical ideas clearly, precisely, and unambiguously.
This chapter will introduce you to some of the special language that is a foundation for much mathematical thought, the language of variables, sets, relations, and functions. Think of the chapter like the exercises you would do before an important sporting event. Its goal is to warm up your mental muscles so that you can do your best.
1.1 Variables A variable is sometimes thought of as a mathematical “John Doe” because you can use it as a placeholder when you want to talk about something but either (1) you imagine that it has one or more values but you don’t know what they are, or (2) you want whatever you say about it to be equally true for all elements in a given set, and so you don’t want to be restricted to considering only a particular, concrete value for it. To illustrate the first use, consider asking
Is there a number with the following property: doubling it and adding 3 gives the same result as squaring it?
In this sentence you can introduce a variable to replace the potentially ambiguous word “it”:
Is there a number x with the property that 2x + 3 = 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 � with the property that 2 ·�+ 3 = �2? The emptiness of the box can help you imagine filling it in with a variety of different values, some of which might make the two sides equal and others of which might not.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
2 Chapter 1 Speaking Mathematically
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 instances 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.
Example 1.1.1 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 + b2 = (a + b)2? Or: Are there numbers a and b such that a2 + b2 = (a + b)2? Or: Do there exist any numbers a and b such that a2 + b2 = (a + b)2?
Note In part (a) the answer is yes. For instance, a = 1 and b = 0 would work. Can you think of other numbers that would also work?
b. Given any real number r, r2 is nonnegative. Or: For any real number r, r2 ≥ 0. Or: For all real numbers 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:
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.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
1.1 Variables 3
Universal Conditional Statements Universal statements contain some variation of the words “for all” and conditional state- ments 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 all animals 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 all dogs 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.
Example 1.1.2 Rewriting a Universal Conditional Statement
Fill in the blanks to rewrite the following statement:
For all real numbers x , if x is nonzero then x2 is positive.
a. If a real number is nonzero, then its square .
Note If you introduce x in the first part of the sentence, be sure to include it in the second part of the sentence.
b. For all nonzero real numbers 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:Note For a number b to
be an additive inverse for a number a means that a + b = 0. Every real number has an additive inverse.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
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 all real numbers r , there is an additive inverse for r . Or : For all real numbers 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 instance, 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 argument, while not restricting you to consider only specific values for them.
Example 1.1.3 Rewriting a Universal Existential Statement
Fill in the blanks to rewrite the following statement: Every pot has a lid.
a. All pots .
b. For all pots P , there is .
c. For all pots 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 all positive integers