Discrete Mathematics with Applications (4th 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 database theory, 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 upperlevel 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.

CONTENTS:

• Chapter 1 Speaking Mathematically
• Chapter 2 The Logic of Compound Statements
• Chapter 3 The Logic of Quantified Statements
• Chapter 4 Elementary Number Theory and Methods of Proof
• Chapter 5 Sequences, Mathematical Induction, and Recursion
• Chapter 6 Set Theory
• Chapter 7 Functions
• Chapter 8 Relations
• Chapter 9 Counting and Probability
• Chapter 10 Graphs and Trees
• Chapter 11 Analysis of Algorithm Efficiency
• Chapter 12 Regular Expressions and Finite-State Automata