Discrete mathematics is a foundational area of mathematics that focuses on structures that are fundamentally separate and distinct, rather than continuous. Unlike calculus, which studies smooth change and continuous intervals, discrete mathematics investigates objects such as sets, graphs, logical statements, and sequences.
This subject plays a central role in computer science. Concepts from discrete mathematics underpin algorithms, data structures, programming languages, cryptography, and network design. For students in mathematics or computer science, it often serves as a bridge to more rigorous reasoning and formal proof.
About the book
Discrete Mathematics: An Open Introduction (4th Edition) by Oscar Levin is a comprehensive undergraduate-level textbook designed for first- and second-year students in mathematics and computer science. It is particularly suited for those preparing to teach mathematics, as well as computer science majors who require a solid theoretical foundation.
The text emphasizes inquiry-based and problem-oriented learning. Each section begins with Investigate! questions and structured Preview Activities intended to encourage active engagement before formal exposition. The book integrates examples, practice problems, additional exercises, reading questions, and chapter reviews. An interactive online version provides immediate feedback for many exercises and includes additional tools.
No separate introduction to proofs is assumed; the book incorporates logical reasoning and proof techniques directly into the development of the subject.
What you will learn
By working through this book, readers will develop skills in formal reasoning, mathematical proof, and the analysis of discrete structures. The content covers core areas that are essential for computer science and advanced mathematics.
You will study:
- Logic and the structure of mathematical statements
- Methods of proof, including direct proof, contrapositive, contradiction, and induction
- Graph theory, including trees, planar graphs, Euler trails, coloring, and matchings
- Counting techniques, including permutations, combinations, inclusion–exclusion, and combinatorial proofs
- Applications of counting to probability
- Sequences, rates of growth, recurrence relations, and induction
- Discrete structures such as sets, functions, and relations
- Generating functions and an introduction to number theory
These topics provide the theoretical tools used in algorithm analysis, combinatorics, discrete modeling, and computational problem solving.
Table of contents
- Acknowledgements
Preface
How to Use This Book - 0 Introduction and Preliminaries
0.1 What is Discrete Mathematics?
Reading Questions
0.2 Discrete Structures
0.2.1 Introduction
0.2.2 Sets
0.2.3 Functions
0.2.4 Sequences
0.2.5 Relations
0.2.6 Graphs
0.2.7 Even More Structures
0.2.8 Reading Questions - 1 Logic and Proofs
1.1 Mathematical Statements
1.2 Implications
1.3 Rules of Logic
1.4 Proofs
1.5 Proofs about Discrete Structures
1.6 Chapter Summary
Chapter Review - 2 Graph Theory
2.1 Problems and Definitions
2.2 Trees
2.3 Planar Graphs
2.4 Euler Trails and Circuits
2.5 Coloring
2.6 Relations and Graphs
2.7 Matching in Bipartite Graphs
2.8 Chapter Summary
Chapter Review - 3 Counting
3.1 Pascal’s Arithmetical Triangle
3.2 Combining Outcomes
3.3 Non-Disjoint Outcomes
3.4 Combinations and Permutations
3.5 Counting Multisets
3.6 Combinatorial Proofs
3.7 Applications to Probability
3.8 Advanced Counting Using PIE
3.9 Chapter Summary
Chapter Review - 4 Sequences
4.1 Describing Sequences
4.2 Rate of Growth
4.3 Polynomial Sequences
4.4 Exponential Sequences
4.5 Proof by Induction
4.6 Strong Induction
4.7 Chapter Summary
Chapter Review - 5 Discrete Structures Revisited
5.1 Sets
5.2 Functions - 6 Additional Topics
6.1 Generating Functions
6.2 Introduction to Number Theory - Appendices
A Selected Hints
B Selected Solutions
C List of Symbols - Index
Book details
- Title: Discrete Mathematics: An Open Introduction, 4th Edition
- Author: Oscar Levin
- Main category: Mathematics
- Subcategory: Discrete Mathematics
- License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
More books in: Discrete Mathematics, Mathematics
Legal notice: This book is shared for educational purposes only. The content is distributed under Creative Commons licenses or with explicit permission from the author. FreeProgrammingBooks may host files that comply with their respective licenses.