Kenneth H. Rosen
SEVENTH EDITION
Discrete
Mathematics
and Its
Applications
Discrete
Mathematics
and Its
Applications
Seventh Edition
Kenneth H. Rosen
Monmouth University
(and formerly AT&T Laboratories)
DISCRETE MATHEMATICS AND ITS APPLICATIONS, SEVENTH EDITION
Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the
Americas, NewYork, NY 10020. Copyright © 2012 by The McGraw-Hill Companies, Inc. All rights reserved.
Previous editions © 2007, 2003, and 1999. No part of this publication may be reproduced or distributed
in any form or by any means, or stored in a database or retrieval system, without the prior written consent of
The McGraw-Hill Companies, Inc., including, but not limited to, in any network or other electronic storage
or transmission, or broadcast for distance learning.
Some ancillaries, including electronic and print components, may not be available to customers outside the
United States.
This book is printed on acid-free paper.
1234567890DOW/DOW10987654321
ISBN 978-0-07-338309-5
MHID 0-07-338309-0
Vice President & Editor-in-Chief: Marty Lange
Editorial Director: Michael Lange
Global Publisher: Raghothaman Srinivasan
Executive Editor: Bill Stenquist
Development Editors: Lorraine K. Buczek/Rose Kernan
Senior Marketing Manager: Curt Reynolds
Project Manager: Robin A. Reed
Buyer: Sandy Ludovissy
Design Coordinator: Brenda A. Rolwes
Cover painting: Jasper Johns, Between the Clock and the Bed, 1981. Oil on Canvas (72 × 126 1/4 inches)
Collection of the artist. Photograph by Glenn Stiegelman. Cover Art © Jasper Johns/Licensed by VAGA, NewYork, NY
Cover Designer: Studio Montage, St. Louis, Missouri
Lead Photo Research Coordinator: Carrie K. Burger
Media Project Manager: Tammy Juran
Production Services/Compositor: RPK Editorial Services/PreTeX, Inc.
Typeface: 10.5/12 Times Roman
Printer: R.R. Donnelley
All credits appearing on this page or at the end of the book are considered to be an extension of the copyright page.
Library of Congress Cataloging-in-Publication Data
Rosen, Kenneth H.
Discrete mathematics and its applications / Kenneth H. Rosen. — 7th ed.
p. cm.
Includes index.
ISBN 0–07–338309–0
1. Mathematics. 2. Computer science—Mathematics. I. Title.
QA39.3.R67 2012
511–dc22
2011011060
www.mhhe.com
Contents
About the Author vi
Preface vii
The Companion Website xvi
To the Student xvii
1 The Foundations: Logic and Proofs ..................................1
1.1 Propositional Logic ............................................................1
1.2 Applications of Propositional Logic.............................................16
1.3 Propositional Equivalences ....................................................25
1.4 Predicates and Quantifiers .....................................................36
1.5 Nested Quantifiers ............................................................57
1.6 Rules of Inference ............................................................69
1.7 Introduction to Proofs .........................................................80
1.8 Proof Methods and Strategy....................................................92
End-of-Chapter Material .....................................................109
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices .115
2.1 Sets ........................................................................115
2.2 Set Operations...............................................................127
2.3 Functions ...................................................................138
2.4 Sequences and Summations...................................................156
2.5 Cardinality of Sets ...........................................................170
2.6 Matrices ....................................................................177
End-of-Chapter Material .....................................................185
3 Algorithms ........................................................191
3.1 Algorithms ..................................................................191
3.2 The Growth of Functions .....................................................204
3.3 Complexity of Algorithms ....................................................218
End-of-Chapter Material .....................................................232
4 Number Theory and Cryptography ................................237
4.1 Divisibility and Modular Arithmetic ...........................................237
4.2 Integer Representations and Algorithms ........................................245
4.3 Primes and Greatest Common Divisors ........................................257
4.4 Solving Congruences.........................................................274
4.5 Applications of Congruences..................................................287
4.6 Cryptography ...............................................................294
End-of-Chapter Material .....................................................306
iii
iv Contents
5 Induction and Recursion ..........................................311
5.1 Mathematical Induction ......................................................311
5.2 Strong Induction and Well-Ordering ...........................................333
5.3 Recursive Definitions and Structural Induction..................................344
5.4 Recursive Algorithms ........................................................360
5.5 Program Correctness .........................................................372
End-of-Chapter Material .....................................................377
6 Counting ..........................................................385
6.1 The Basics of Counting.......................................................385
6.2 The Pigeonhole Principle .....................................................399
6.3 Permutations and Combinations ...............................................407
6.4 Binomial Coefficients and Identities ...........................................415
6.5 Generalized Permutations and Combinations ...................................423
6.6 Generating Permutations and Combinations ....................................434
End-of-Chapter Material .....................................................439
7 Discrete Probability ...............................................445
7.1 An Introduction to Discrete Probability ........................................445
7.2 Probability Theory...........................................................452
7.3 Bayes’Theorem .............................................................468
7.4 Expected Value and Variance..................................................477
End-of-Chapter Material .....................................................494
8 Advanced Counting Techniques ...................................501
8.1 Applications of Recurrence Relations ..........................................501
8.2 Solving Linear Recurrence Relations ..........................................514
8.3 Divide-and-Conquer Algorithms and Recurrence Relations.......................527
8.4 Generating Functions ........................................................537
8.5 Inclusion–Exclusion .........................................................552
8.6 Applications of Inclusion–Exclusion ...........................................558
End-of-Chapter Material .....................................................565
9 Relations ..........................................................573
9.1 Relations and Their Properties ................................................573
9.2 n-ary Relations and Their Applications.........................................583
9.3 Representing Relations .......................................................591
9.4 Closures of Relations ........................................................597
9.5 Equivalence Relations........................................................607
9.6 Partial Orderings ............................................................618
End-of-Chapter Material .....................................................633
