683 422 in expanded form

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

This page was intentionally left blank
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

This page was intentionally left blank
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 Strong Mathematical Induction;Binary Representation of Integers;The Well-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 by Mathematical 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; The Quotient Automaton; Constructing the Quotient Automaton; Equivalent Automata

Appendix A Properties of the Real Numbers A-1

Appendix B Solutions and Hints to Selected Exercises A-4

Index I-1

Copyright 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.