Mathematics and Its
Applications
. EVENTH EDITION
Copyright By PowCoder代写 加微信 powcoder
Discrete Mathematics and Its Applications Seventh Edition
. 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, , 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.
1 2 3 4 5 6 7 8 9 0 DOW/DOW 1 0 9 8 7 6 5 4 3 2 1
ISBN 978-0-07-338309-5 MHID 0-07-338309-0
Vice President & Editor-in-Chief: Editorial Director:
Global Publisher: Executive Editor:
Development Editors: . Buczek/ Senior Marketing Manager:
Project Manager: . :
Design Coordinator: . Rolwes
Cover painting: , Between the Clock and the Bed, 1981. Oil on Canvas (72 × 126 1/4 inches)
Collection of the artist. Photograph by . Cover Art © /Licensed by VAGA, , NY Cover Designer: Studio Montage, St. Louis, Missouri
Lead Photo Research Coordinator: . Project Manager:
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
Discrete mathematics and its applications / . Rosen. — 7th ed.
Includes index.
ISBN 0–07–338309–0
1. Mathematics. 2. Computer science—Mathematics. I. Title. QA39.3.R67 2012
www.mhhe.com
2011011060
About the Author vi Preface vii
The Companion Website xvi To the Student xvii
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8
2.1 2.2 2.3 2.4 2.5 2.6
3.1 3.2 3.3
4.1 4.2 4.3 4.4 4.5 4.6
The Foundations: Logic and Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Applications of Propositional Logic………………………………………16 Propositional Equivalences ……………………………………………. 25 Predicates and Quantifiers …………………………………………….. 36 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Rules of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Introduction to Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Proof Methods and Strategy…………………………………………….92 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Basic Structures: Sets, Functions, Sequences, Sums, and Matrices . 115
Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 Sequences and Summations……………………………………………156 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 The Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Number Theory and Cryptography…………………………..237
Divisibility and Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Integer Representations and Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 Primes and Greatest Common Divisors …………………………………. 257 Solving Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Applications of Congruences…………………………………………..287 Cryptography ……………………………………………………… 294 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
iv Contents
5.1 5.2 5.3 5.4 5.5
6.1 6.2 6.3 6.4 6.5 6.6
7.1 7.2 7.3 7.4
8.1 8.2 8.3 8.4 8.5 8.6
9.1 9.2 9.3 9.4 9.5 9.6
Induction and Recursion …………………………………… 311
Mathematical Induction ……………………………………………… 311 StrongInductionandWell-Ordering…………………………………….333 Recursive Definitions and Structural Induction…………………………….344 RecursiveAlgorithms………………………………………………..360 ProgramCorrectness…………………………………………………372 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
Counting………………………………………………….385
TheBasicsofCounting……………………………………………….385 The Pigeonhole Principle……………………………………………..399 Permutations and Combinations………………………………………..407 Binomial Coefficients and Identities ……………………………………. 415 Generalized Permutations and Combinations …………………………….. 423 Generating Permutations and Combinations ……………………………… 434 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
DiscreteProbability………………………………………..445
An Introduction to Discrete Probability …………………………………. 445 Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 Bayes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 Expected Value and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
Advanced Counting Techniques……………………………..501
Applications of Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 Solving Linear Recurrence Relations …………………………………… 514 Divide-and-Conquer Algorithms and Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . 527 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 Inclusion–Exclusion ………………………………………………… 552 Applications of Inclusion–Exclusion…………………………………….558 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
Relations………………………………………………….573
Relations and Their Properties ………………………………………… 573 n-aryRelationsandTheirApplications…………………………………..583 Representing Relations……………………………………………….591 ClosuresofRelations ……………………………………………….. 597 EquivalenceRelations………………………………………………..607 PartialOrderings …………………………………………………… 618 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8
11.1 11.2 11.3 11.4 11.5
12.1 12.2 12.3 12.4
13.1 13.2 13.3 13.4 13.5
Contents v Graphs……………………………………………………641
GraphsandGraphModels…………………………………………….641 Graph Terminology and Special Types of Graphs…………………………..651 Representing Graphs and Graph Isomorphism ……………………………. 668 Connectivity ………………………………………………………. 678 Euler and Hamilton Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693 Shortest-Path Problems……………………………………………….707 PlanarGraphs………………………………………………………718 GraphColoring……………………………………………………..727 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735
Trees………………………………………………………745
IntroductiontoTrees…………………………………………………745 ApplicationsofTrees…………………………………………………757 TreeTraversal………………………………………………………772 SpanningTrees……………………………………………………..785 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803
BooleanAlgebra……………………………………………811
BooleanFunctions…………………………………………………..811 Representing Boolean Functions ………………………………………. 819 LogicGates………………………………………………………..822 Minimization of Circuits …………………………………………….. 828 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843
Modeling Computation ……………………………………. 847
Languages and Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847 Finite-State Machines with Output………………………………………858 Finite-State Machines with No Output ………………………………….. 865 Language Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 878 TuringMachines…………………………………………………….888 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899
Appendixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1
Axioms for the Real Numbers and the Positive Integers ………………………. 1 Exponential and Logarithmic Functions …………………………………… 7 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Suggested Readings B-1
Answers to Odd-Numbered Exercises S-1 Photo Credits C-1
Index of Biographies I-1
About the Author
. Rosen has had a long career as a Distinguished Member of the Technical Staff at AT&T Laboratories in Monmouth County, . He currently holds the position of Visiting Research Professor at Monmouth University, where he teaches graduate courses in computer science.
Dr. Rosen received his B.S. in Mathematics from the University of Michigan, (1972), and his Ph.D. in Mathematics from M.I.T. (1976), where he wrote his thesis in the area of number theory under the direction of . Before joining Bell Laboratories in 1982, he held positions at the University of Colorado, Boulder; The Ohio State University, Columbus; and the University of Maine, Orono, where he was an associate professor of mathematics. While working at AT&T Labs, he taught at Monmouth University, teaching courses in discrete mathematics, coding theory, and data security. He currently teaches courses in algorithm design and in computer security and cryptography.
Dr. Rosen has published numerous articles in professional journals in number theory and in mathematical modeling. He is the author of the widely used Elementary Number Theory and Its Applications, published by Pearson, currently in its sixth edition, which has been translated into Chinese. He is also the author of Discrete Mathematics and Its Applications, published by McGraw-Hill, currently in its seventh edition. Discrete Mathematics and Its Applications has sold more than 350,000 copies in North America during its lifetime, and hundreds of thousands of copies throughout the rest of the world. This book has also been translated into Spanish, French, Greek, Chinese, Vietnamese, and Korean. He is also co-author of UNIX: The Complete Reference; UNIX System V Release 4: An Introduction; and NIX Tips Ever, all published by Graw-Hill. These books have sold more than 150,000 copies, with translations into Chinese, German, Spanish, and Italian. Dr. Rosen is also the editor of the Handbook of Discrete and Combinatorial Mathematics, published by CRC Press, and he is the advisory editor of the CRC series of books in discrete mathematics, consisting of more than 55 volumes on different aspects of discrete mathematics, most of which are introduced in this book. Dr. Rosen serves as an Associate Editor for the journal Discrete Mathematics, where he works with submitted papers in several areas of discrete mathematics, including graph theory, enumeration, and number theory. He is also interested in integrating mathematical software into the educational and professional environments, and worked on several projects with Waterloo Maple Inc.’s MapleTM software in both these areas. Dr. Rosen has also worked with several publishing companies on their homework delivery platforms.
At Bell Laboratories and AT&T Laboratories, Dr. Rosen worked on a wide range of projects, including operations research studies, product line planning for computers and data communi- cations equipment, and technology assessment. He helped plan AT&T’s products and services in the area of multimedia, including video communications, speech recognition, speech synthesis, and image networking. He evaluated new technology for use by AT&T and did standards work in the area of image networking. He also invented many new services, and holds more than 55 patents. One of his more interesting projects involved helping evaluate technology for the AT&T attraction that was part of EPCOT Center.
In writing this book, I was guided by my long-standing experience and interest in teaching discrete mathematics. For the student, my purpose was to present material in a precise, readable manner, with the concepts and techniques of discrete mathematics clearly presented and demonstrated. My goal was to show the relevance and practicality of discrete mathematics to students, who are often skeptical. I wanted to give students studying computer science all of the mathematical foundations they need for their future studies. I wanted to give mathematics students an understanding of important mathematical concepts together with a sense of why these concepts are important for applications. And most importantly, I wanted to accomplish these goals without watering down the material.
For the instructor, my purpose was to design a flexible, comprehensive teaching tool using proven pedagogical techniques in mathematics. I wanted to provide instructors with a package of materials that they could use to teach discrete mathematics effectively and efficiently in the most appropriate manner for their particular set of students. I hope that I have achieved these goals.
I have been extremely gratified by the tremendous success of this text. The many improve- ments in the seventh edition have been made possible by the feedback and suggestions of a large number of instructors and students at many of the more than 600 North American schools, and at any many universities in parts of the world, where this book has been successfully used.
This text is designed for a one- or two-term introductory discrete mathematics course taken by students in a wide variety of majors, including mathematics, computer science, and engineer- ing. College algebra is the only explicit prerequisite, although a certain degree of mathematical maturity is needed to study discrete mathematics in a meaningful way. This book has been de- signed to meet the needs of almost all types of introductory discrete mathematics courses. It is highly flexible and extremely comprehensive. The book is designed not only to be a successful textbook, but also to serve as valuable resource students can consult throughout their studies and professional life.
Goals of a Discrete Mathematics Course
A discrete mathematics course has more than one purpose. Students should learn a particular set of mathematical facts and how to apply them; more importantly, such a course should teach students how to think logically and mathematically. To achieve these goals, this text stresses mathematical reasoning and the different ways problems are solved. Five important themes are interwoven in this text: mathematical reasoning, combinatorial analysis, discrete structures, algorithmic thinking, and applications and modeling. A successful discrete mathematics course should carefully blend and balance all five themes.
1. Mathematical Reasoning: Students must understand mathematical reasoning in order to read, comprehend, and construct mathematical arguments. This text starts with a discussion of mathematical logic, which serves as the foundation for the subsequent discussions of methods of proof. Both the science and the art of c
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com