Discrete Mathematics with Applications 5th Edition

Book 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, mathematics education, and engineering. The goal of the book is to lay the mathematical foundation for computer science courses such as data structures, algorithms, relational databasetheory, automata theory and formal languages, compiler design, and cryptography, 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 applications 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 America, 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 computer 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 understood 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 continuing 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 fashion. 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 technology 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 mathematics 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 arguments 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 recursively 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 mathematical 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 counting and arranging objects, and probability is the study of laws concerning the measurement 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 combinatorics 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 middle 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 algorithm, 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 algorithm will need in order to compare it to other algorithms that produce the same output requires knowledge of combinatorics, recurrence relations, functions, and O-, V-, and Q-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.