- 原书名：Discrete Mathematics and Its Applications, Seventh Edition, English Abridgement
Kenneth H.Rosen has had a long career as a Distinguished Member of the Technical Staff at AT&T Laboratories in Monmouth County, New Jersey. 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, Ann Arbor (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 Harold Stark. 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 taughtat 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 life time, and hundreds of thousands of copies throughout the rest of the world. This book has also been translatedin to Spanish, French, Greek, Chinese, Vietnamese, and Korean. He is also co-author of UNIX: The Complete Reference; UNIX System VRelease 4: An Introduction; and Best UNIX Tips Ever, all published by Osborne McGraw-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 Hand book 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.抯 MapleTM software in both the seareas. Dr. Rosen has also worked with several publishing companies on their homework delivery platforms.
At BellLaboratories 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抯 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.
The Adapter 's Words iv
About the Author xi
The Companion Website xii
To the Student xiv
List of Symbols xvii
1 The Foundations: Logic and Proofs..................................1
1.1 Propositional Logic........................................1
1.2 Applications of Propositional Logic........................................13
1.3 Propositional Equivalences........................................20
1.4 Predicates and Quantifiers........................................32
1.5 Nested Quantifiers........................................49
1.6 Rules of Inference........................................59
1.7 Introduction to Proofs........................................70
1.8 Proof Methods and Strategy........................................80
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices .........101
2.2 Set Operations........................................111
Written by Prof. Kenneth H. Rosen, the original book of Discrete Mathematics and its Applications is an excellent textbook and is widely used around the world.
The seventh edition gives a focused introduction to the primary themes of the Discrete Mathematics course and demonstrates its practicality and relevance to real-world application in a wide variety of examples. All the topics, examples, references and exercises are quite helpful to the students.
In recent years, more and more Chinese instructors and students are getting interested in this book. However, as a textbook, the thickness of over 900 original pages make Chinese students find it difficult to read. In order to introduce this book to more Chinese college students, we tried to compress the book to a concise version.
What is Compressed
Since some contents in the original are taught in some other courses, such as Algorithm, Number theory and Cryptography, Discrete Probability, Induction and Recursion, and Finite-state Machine, we remove them from the book. Those removed topics are in the original book as Chapter 3, Chapter 4, Chapter 5, Chapter 7 and Chapter 13. As a result, only Logic and Proofs, Sets, Functions, Counting and Advanced Counting Techniques, Relations, Graphs, Trees and Boolean Algebra are reserved in the compressed version.
There are over 4000 exercises in the original textbook with questions of different difficulties posed. Some of them are designed for basic skill development, some are in intermediate level and some are of more difficult and challenges. In order to keep the original feature of the book, we only removed the even-number questions of the reserved Chapters and the other questions are retained.
The historical information for the background of many topics is also removed.
Some concepts are given in the exercises, which is difficult for students to comprehend because of the simplicity of the descriptions, such as the concepts of the Normal forms for a proposition. So we added the detail descriptions in Chapter 1.
We would like to thank Kenneth H. Rosen, the author of the original book, and McGraw-Hill, the original publisher, who authorized us to compress the original book. It is their understanding and generosity that makes it possible for more Chinese students to enjoy this distinguished book.
We would also like to thank the staff at China Machine Press for their valuable work to the book, and thank the readers and colleagues who has given valuable comments to the work.
We tried to retain the essence of the original book and conform to the requirements of the syllabus of the discrete mathematics course for undergraduate students in the compressed version. We are sorry that some of our work might be inappropriate, or we might have deleted a few relevant contents from the original book, which may result in certain reading difficulties. If you have any comments and suggestions, please let us know, and you will be highly appreciated.
South China University of Technology
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 improvements 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 engineering. 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 designed 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 constructing proofs are addressed. The technique of mathematical induction is stressed through many different types of examples of such proofs and a careful explanation of why mathematical induction is a valid proof technique.
2. Combinatorial Analysis: An important problem-solving skill is the ability to count or enumerate objects. The discussion of enumeration in this book begins with the basic techniques of counting. The stress is on performing combinatorial analysis to solve counting problems and analyz ealgorithms, not on applying formulae.
3. Discrete Structures: A course in discrete mathematics should teach students how to work with discrete structures, which are the abstract mathematical structures used to represent discrete objects and relationships between these objects. These discrete structures include sets, permutations, relations, graphs, trees, and finite-state machines.
4. Algorithmic Thinking: Certain classes of problems are solved by the specification of an algorithm. After an algorithm has been described, a computer program can beconstructed implementing it. The mathematical portions of this activity, which include the specification of the algorithm, the verification that it works properly, and the analysis of the computer memory and time required to perform it, are all covered in this text. Algorithms are described using both English and an easily understood form of pseudocode.
5. Applications and Modeling: Discrete mathematics has applications to almost every conceivable area of study. There are many applications to computer science and data networking in this text, as well as applications to such diverse areas as chemistry, biology, linguistics, geography, business, and the Internet. These applications are natural and important uses of discrete mathematics and are not contrived. Modeling with discrete mathematics is an extremely important problem-solving skill, which students have the opportunity to develop by constructing their own models in some of the exercises.
Features of the Book
ACCESSIBILITY This text has proved to be easily read and understood by beginning students. There are no mathematical prerequisites beyond college algebra for almost all the content of the text. Students needing extra help will find tools on the companion website for bringing their mathematical maturity up to the level of the text. The few places in the book where calculus is referred to are explicitly noted. Most students should easily understand the pseudocode used in the text to express algorithms, regardless of whether they have formally studied programming languages. There is no formal computer science prerequisite.
Each chapter begins at an easily understood and accessible level. Once basic mathematical concepts have been carefully developed, more difficult material and applications to other areas of study are presented.
FLEXIBILITY This text has been carefully designed for flexible use. The dependence of chapters on previous material has been minimized. Each chapter is divided into sections of approximately the same length, and each section is divided into subsections that form natural blocks of material for teaching. Instructors can easily pace their lectures using these blocks.
WRITING STYLE The writing style in this book is direct and pragmatic. Precise mathe-matical language is used without excessive formalism and abstraction. Care has been taken to balance the mix of notation and words in mathematical statements.
MATHEMATICAL RIGOR AND PRECISION All definitions and theorems in this text are stated extremely carefully so that students will appreciate the precision of language and rigor needed in mathematics. Proofs are motivated and developed slowly; their steps are all carefully justified. The axioms used in proofs and the basic properties that follow from them are explicitly described in an appendix, giving students a clear idea of what they can assume in a proof. Recursive definitions are explained and used extensively.
WORKED EXAMPLES Many examples are used to illustrate concepts, relate different topics, and introduce applications. In most examples, a question is first posed, then its solution is presented with the appropriate amount of detail.
APPLICATIONS The applications included in this text demonstrate the utility of discrete mathematics in the solution of real-world problems. This text includes applications to a wide variety of areas, including computer science, data networking, psychology, chemistry, engineering, linguistics, biology, business, and the Internet.