This text explains how to use mathematical models and methods to analyze problems that arise in computer science. The subject offers an introduction to Discrete Mathematics oriented toward Computer Science and Engineering, adnd covers: Fundamental concepts of Mathematics: definitions, proofs, sets, functions, relations; Discrete structures: graphs, state machines, modular arithmetic, counting; Discrete probability theory.
Readers will be able
- to reason mathematically about basic data types and structures used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesize elementary proofs, especially proofs by induction.
- to model and analyze computational processes using analytic and combinatorial methods.
- to apply principles of discrete probability to calculate probabilities and expectations of simple random processes.
Brief Contents
I Proofs
Introduction
1 What is a Proof?
2 The Well Ordering Principle
3 Logical Formulas
4 Mathematical Data Types
5 Induction
6 Recursive Data Types
7 Infinite Sets
8 Number Theory
II Structures
Introduction
9 Directed graphs & Partial Orders
10 Communication Networks
11 Simple Graphs
12 Planar Graphs
III Counting
Introduction
13 Sums and Asymptotics
14 Cardinality Rules
15 Generating Functions
IV Probability
Introduction
16 Events and Probability Spaces
17 Random Variables
18 Deviation from the Mean
19 Random Processes
V Recurrences
Introduction
20 Recurrences
Bibliography
Index
Glossary of Symbols
Contents
I Proofs
1 What is a Proof?
1.1 Propositions
1.2 Predicates
1.3 The Axiomatic Method
1.4 Our Axioms
1.5 Proving an Implication
1.6 Proving an “If and Only If”
1.7 Proof by Cases
1.8 Proof by Contradiction
1.9 Good Proofs in Practice
2 The Well Ordering Principle
2.1 Well Ordering Proofs
2.2 Template for Well Ordering Proofs
2.3 Factoring into Primes
2.4 Well Ordered Sets
3 Logical Formulas
3.1 Propositions from Propositions
3.2 Propositional Logic in Computer Prog
AI Reading Assistant
Whole-book reading guide from stratified index samples; jump to passages in the text
Tip the Site
Support this siteYour recognition and a small knowledge-service contribution help keep this technical work open source.Scan the WeChat Pay or Alipay code below. Logged-in and guest visitors can both tip.
WeChat Pay
Alipay
Open WeChat or Alipay and scan. No login required.
AI guide
【One-Line Pitch】
A rigorous but readable introduction to the discrete mathematics that underpins computer science—proofs, structures, counting, and probability—for students and self-learners who want to reason about algorithms and systems with real mathematical confidence.
【Book Arc】
- **Opening (~0%–15%)**: Establishes the axiomatic method and proof technique—propositions, predicates, implication, contradiction, and the Well Ordering Principle—so readers can distinguish rigorous arguments from plausible ones.
- **Early (~15%–35%)**: Builds the language of discrete structures: logical formulas, sets, relations, functions, induction, recursive data types, and infinite sets, culminating in the limits of computation and set-theoretic paradoxes.
- **Middle (~35%–55%)**: Applies these tools to number theory (gcd, modular arithmetic, inverses, unique factorization) and then to graphs—directed graphs, partial orders, communication networks, simple and planar graphs.
- **Middle–Late (~55%–75%)**: Shifts to counting and asymptotics: sums, cardinality rules, and generating functions, giving combinatorial tools for analyzing computational processes.
- **Late (~75%–90%)**: Introduces discrete probability—probability spaces, random variables, deviation from the mean, and random processes—for reasoning about randomized algorithms and expected behavior.
- **Ending (~90%–100%)**: Closes with recurrences, tying together the analytic and combinatorial threads used to model algorithm running times and recursive structures.
【Key Takeaways】
- **Proof is a craft, not a formality** (Opening): The book teaches proof by implication, equivalence, cases, contradiction, and the Well Ordering Principle, with deliberate attention to bogus proofs so readers learn to spot gaps.
- **Induction and invariants are the workhorses** (Early): Induction, structural induction over recursive data types, and the Invariant Principle for state machines recur throughout, making them essential for reasoning about loops, recursion, and system behavior.
- **Sets, relations, and functions are the vocabulary** (Early): Binary relations, injectivity/surjectivity, and set equalities are treated as provable objects, preparing readers for graphs and databases later.
- **Number theory has direct computational payoff** (Middle): Modular arithmetic, multiplicative inverses, and unique factorization connect to cryptography and secure communication, not just abstract puzzles.
- **Graphs model real systems** (Middle): Directed graphs, partial orders, communication networks, and planar graphs show how discrete structures describe scheduling, connectivity, and network design.
- **Counting needs both rules and generating functions** (Middle–Late): Cardinality rules and generating functions provide systematic ways to count configurations and analyze sums and asymptotics.
- **Probability quantifies uncertainty in computation** (Late): Probability spaces, random variables, and deviation bounds support analysis of randomized processes and expected outcomes.
- **Recurrences close the loop** (Ending): Solving recurrences links recursive definitions to asymptotic growth, a core skill for algorithm analysis.
【Reading Tips】
- Deep-read Part I (proofs and induction); skim only if you already write rigorous proofs fluently.
- Work the exercises—especially the "bogus proof" problems—since the book's value lies in practice, not passive reading.
- Treat number theory and graphs as application chapters; connect them to cryptography and network examples as you go.
- For probability and recurrences, keep a formula sheet of definitions (probability space, expectation, recurrence templates) to revisit.
- Skim the infinite sets and Russell's paradox material on a first pass; return after mastering induction and relations.
【Coverage Limits】
This guide is based on stratified excerpts covering the book's structure and early-to-middle chapters; later chapters on probability and recurrences are mapped from the table of contents and brief contents rather than detailed excerpt content.
Excerpt 1
ce 2 The Well Ordering Principle 2.1 Well Ordering Proofs 2.2 Template for Well Ordering Proofs 2.3 Factoring into Primes 2.4 Well Ordered Sets 3 Logical For...
tical Data Types Problems for Section 4.4 Practice Problems Problem 4.9. For a binary relation, R W A ! B , some properties of R can be determined from just...
f3.6/ D 0 and f3.6/ D 1, so (6.4) doesn’t define anything. Mathematicians have been wondering about this function specification for a while: 8̂<̂1; if n 1; f...
ind a linear combination of n and k equal to 1: snC tk D 1: So taking remainders of division by n of both sides of this equality, and then apply- ing Lemma 8...
ers that follows directly from this definition. Lemma 9.5.3. A relation R on a set, A, is a weak partial order iff there is a strict partial order, S , on A...
l 2 L.G/ and r 2 R.G/. For example, the graph in Figure 11.9 is degree-constrained since every node on the left is adjacent to at least two nodes on the righ...
ed, bipartite and has 6 vertices and 9 edges. But since 9 > 2 6 4,K3;3 does not satisfy the inequality (12.3) that holds in all bipartite planar graphs. 12.6...
Support this siteYour recognition and a small knowledge-service contribution help keep this technical work open source.
Scan the WeChat Pay or Alipay code below. Logged-in and guest visitors can both tip.
WeChat PayAlipay
Open WeChat or Alipay and scan. No login required.
Add Tag
Enter tag name (max 50 characters)
Share E-Book
Mathematics for Computer Science (Eric Lehman, F. Thomson Leighton etc.)(Z-Library)
Scan QR code with your phone to access
Copy the link or scan the QR code to access this e-book on your phone
Share to WeChat Moments
Mathematics for Computer Science (Eric Lehman, F. Thomson Leighton etc.)(Z-Library)
Scan the QR code with WeChat to open this book
Tap the ··· menu in the top-right corner
Choose Share to Moments
You are already in WeChat. Tap ··· in the top-right corner and choose Share to Moments.
Share E-Book via Email
Please enter email address
Donation Statistics
¥.00
Total Donations
0
Donation Count
Mathematics for Computer Science (Eric Lehman, F. Thomson Leighton etc.)(Z-Library)
Find Your Favorite Books
Only registered users can comment after logging in. Comments need to be reviewed by administrators before being displayed
Loading comments...
Reply to Comment
Edit Comment