Understand Mathematics, Understand Computing: Discrete Mathematics That All Computing Students Should Know

Contents
Manifesto
Preface
Chapter 1 Introduction
1.1 Why Is This Book Needed?
1.2 Why Is This Book Needed?
1.3 The Structure of This Book
1.3.1 Our Main Intellectual Targets
1.3.2 Allocating Our Targets to Chapters
1.3.2.1 Chapter 2: “Doing” Mathematics
1.3.2.2 Chapter 3: Sets and Their Algebras
1.3.2.3 Chapters 4, 8, 10: Numbers and Numerals
1.3.2.4 Chapters 5 and 6: Arithmetic and Summation
1.3.2.5 Chapter 7: The Vertigo of Infinity
1.3.2.6 Chapter 9: Recurrences
1.3.2.7 Chapter 11: The Art of Counting: Combinatorics, with Applications to Probability and Statistics
1.3.2.8 Chapters 12 and 13: Graphs and Related Topics
1.4 Using the Text in Courses
1.4.1 Resources
1.4.1.1 References
1.4.1.2 Cultural asides
1.4.1.3 Exercises
1.4.1.4 Appendices
1.4.2 Paths Through the Text for Selected Courses
Chapter 2 “Doing” Mathematics: A Toolkit for Mathematical Reasoning
2.1 Rigorous Proofs: Theory vs. Practice
2.1.1 Formalistic Proofs and Modern Proofs
2.1.1.1 Formalistic proofs, with an illustration
2.1.1.2 Modern proofs, with an illustration
2.1.1.3 Some elements of rigorous reasoning
A. Distinguishing name from object
B. Quantitative reasoning
C. The elements of empirical reasoning
2.2 Overview of Some Major Proof Techniques
2.2.1 Proof by (Finite) Induction
2.2.1.1 Two more sample proofs by induction
2.2.1.2 A A false “proof” by induction: The critical base case
2.2.1.3 The Method of Undetermined Coefficients
2.2.2 Proof by Contradiction
2.2.2.1 The proof technique
2.2.2.2 Another sample proof: There are infinitely many prime numbers
2.2.3 Proofs via the Pigeonhole Principle
2.2.3.1 The proof technique
2.2.3.2 Sample applications/proofs
2.3 Nontraditional Proof Strategies
2.3.1 Pictorial Reasoning
2.3.1.1 The virtuous side of the method
2.3.1.2 Handle pictorial arguments with care
2.3.2 Combinatorial Intuition and Argumentation
2.3.2.1 Summation as a selection problem
2.3.2.2 Summation as a rearrangement problem
2.3.3 The Computer as Mathematician’s Assistant
2.4 Exercises: Chapter 2
Chapter 3 Sets and Their Algebras: The Stem Cells of
Mathematics
3.1 Introduction
3.2 Sets
3.2.1 Fundamental Set-Related Concepts
3.2.2 Operations on Sets
3.3 Structured Sets
3.3.1 Binary Relations: Sets of Ordered Pairs
3.3.2 Order Relations
3.3.3 Equivalence Relations
3.3.4 Functions
3.3.4.1 The basics: definitions and generic properties
3.3.4.2 ⊕ The Schröder-Bernstein Theorem
3.3.5 Sets, Strings, Functions: Important Connections
3.4 Boolean Algebras
3.4.1 The Algebra of Propositional Logic
3.4.1.1 Logic as an algebra
A. Propositions: the objects of the algebra
B. Logical connectives: the algebra’s operations
C. The goal of the game: Theorems
3.4.1.2 Semantic completeness: Logic via Truth Tables
A. Truth, theoremhood, and completeness
B. The completeness of Propositional Logic
C. The laws of Propositional Logic as theorems
3.4.2 ⊕ A Purely Algebraic Setting for Completeness
3.4.3 Satisfiability Problems and NP-Completeness
3.5 Exercises: Chapter 3
Chapter 4 Numbers I: The Basics of Our Number System
4.1 Introducing the Three Chapters on Numbers
4.2 A Brief Biography of Our Number System
4.3 Integers: The “Whole” Numbers
4.3.1 The Basics of the Integers: The Number Line
4.3.1.1 Natural orderings of the integers
4.3.1.2 The order-related laws of the integers
4.3.2 Divisibility: Quotients, Remainders, Divisors
4.3.2.1 Euclidean division
4.3.2.2 Divisibility, divisors, GCDs
4.4 The Rational Numbers
4.4.1 The Rationals: Special Ordered Pairs of Integers
4.4.2 Comparing the Rational and Integer Number Lines
4.4.2.1Comparing Z and Q via their number-line laws
4.4.2.2 Comparing Z and Q via their cardinalities
4.5 The Real Numbers
4.5.1 Inventing the Real Numbers
4.5.2 Defining the Real Numbers via Their Representations
4.5.3 Not All Real Numbers Are Rational
4.5.3.1 A number-based proof that √2 is not rational: √2 Q
4.5.3.2 A geometric proof that √2 is not rational: √2 Q
4.6 The Basics of the Complex Numbers
4.7 Exercises: Chapter 4
Chapter 5 Arithmetic: Putting Numbers to Work
5.1 The Basic Arithmetic Operations
5.1.1 Unary (Single-Argument) Operations
5.1.1.1 Negating and reciprocating numbers
5.1.1.2 Floors, ceilings, magnitudes
5.1.1.3 Factorials (of a nonnegative integer)
5.1.2 Binary (Two-Argument) Operations
5.1.2.1 Addition and subtraction
5.1.2.2 Multiplication and division
5.1.2.3 Exponentiation and taking logarithms
5.1.2.4 Binomial coefficients and Pascal’s triangle
5.1.3 Rational Arithmetic: A Computational Exercise
5.2 The Laws of Arithmetic, with Applications
5.2.1 The Commutative, Associative, and Distributive Laws
5.3 Polynomials and Their Roots
5.3.1 Univariate Polynomials and Their Roots
5.3.1.1 The d roots of a degree-d polynomial
5.3.1.2 Solving polynomials by radicals
A. Solving quadratic polynomials by radicals
B. Solving cubic polynomials by radicals
5.3.2 Bivariate Polynomials: The Binomial Theorem
5.3.3 ⊕ Integer Roots of Polynomials: Hilbert’s Tenth Problem
5.4 Exponential and Logarithmic Functions
5.4.1 Basic Definitions
5.4.2 Learning from Logarithms (and Exponentials)
5.5 ⊕ Pointers to Specialized Topics
5.5.1 Norms and Metrics for Tuple-Spaces
5.5.2 Edit-Distance: Measuring Closeness in String Spaces
5.6 Exercises: Chapter 5
Chapter 6 Summation: A Complex Whole from Simple Parts
6.1 The Many Facets of Summation
6.2 Summing Structured Series
6.2.1 Arithmetic Summations and Series
6.2.1.1 General development
6.2.1.2 Example #1: Summing the first
6.2.1.3 Example #2: Squares as sums of odd integers
6.2.2 Geometric Sums and Series
6.2.2.1 Overview and main results
6.2.2.2 Techniques for summing geometric series
6.2.2.3 Extended geometric series and their sums
6.3 On Summing “Smooth” Series
6.3.1 Approximate Sums via Integration
6.3.2 Sums of Fixed Powers of Consecutive Integers: Σic
6.3.2.1 Sc(n) for general nonnegative real cth powers
6.3.2.2 Nonnegative integer cth powers
A. A better bound via the Binomial Theorem
B. Using undetermined coefficients to refine sums
C. A pictorial solution for c = 2
D. ⊕ Semi-pictorial solutions for c = 3
6.3.2.3 Sc(n) for general negative cth powers
A. Negative powers -1 < c < 0
B. Negative powers c < -1
C. Negative powers c = -1: the harmonic series
6.4 Exercises: Chapter 6
Chapter 7 The Vertigo of Infinity: Handling the Very Large and the Infinite
7.1 Asymptotics
7.1.1 The Language of Asymptotics
7.1.2 The “Uncertainties” in Asymptotic Relationships
7.1.3 Inescapable Complications
7.2 Reasoning About Infinity
7.2.1 Coping with infinity
7.2.2 The “Point at Infinity”
7.2.2.1 Underspecified problems
A. Summing ambiguous infinite summations
B. The Ross-Littlewood paradox
C. Zeno’s paradox: Achilles and the tortoise
D. Hilbert’s hotel paradox
7.2.2.2 Foundational paradoxes
A. G¨odel’s paradox: Self-reference in language
B. Russell’s paradox: The “anti-universal” set
7.3 Exercises: Chapter 7
Chapter 8 Numbers II: Building the Integers and Building
with the Integers
8.1 Prime Numbers: Building Blocks of the Integers
8.1.1 The Fundamental Theorem of Arithmetic
8.1.1.1 Statement and proof
8.1.1.2 A “prime” corollary: There are infinitely many primes
8.1.1.3 Number sieves: Eratosthenes and Euler
8.1.1.4 Applying the Fundamental Theorem in encryption
8.1.1.5 ⊕⊕ The “density” of the prime numbers
8.1.2 Fermat’s Little Theorem: ap ≡ a mod p
8.1.2.1 A proof that uses “necklaces”
8.1.2.2 A proof that uses the Binomial Theorem
8.1.3 ⊕ Perfect Numbers and Mersenne Primes
8.1.3.1 Definitions
8.1.3.2 Using Mersenne primes to generate perfect numbers
8.2 Pairing Functions: Bringing Linear Order to Tuple Spaces
8.2.1 Encoding Complex Structures via Ordered Pairs
8.2.2 The Diagonal Pairing Function: Encoding N+N+ as N+
8.2.3 N X N Is Not “Larger Than” N
8.2.3.1 Comparing infinite sets via cardinalities
8.2.3.2 Comparing N and N X N via cardinalities
8.3 Finite Number Systems
8.3.1 Congruences on Nonnegative Integers
8.3.2 Finite Number Systems via Modular Arithmetic
8.3.2.1 Sums, differences, and products exist within Nq
8.3.2.2 Quotients exist within Np for every prime p
8.4 Exercises: Chapter 8
Chapter 9 Recurrences: Rendering Complex Structure
Manageable
9.1 Linear Recurrences
9.1.1 The Master Theorem for Simple Linear Recurrences
9.1.2 The Master Theorem for General Linear Recurrences
9.1.3 An Application: The Elements of Information Theory
9.2 Bilinear Recurrences
9.2.1 Binomial Coefficients and Pascal’s Triangle
9.2.1.1 The formation rule for Pascal’s Triangle
9.2.1.2 Summing complete rows of Pascal’s Triangle
9.2.2 The Fibonacci Number Sequence
9.2.2.1 The story of the Fibonacci numbers
9.2.2.2 Fibonacci numbers and binomial coefficients
9.2.2.3 Alternative origins for the Fibonacci sequence
A. Two multilinear generating recurrences
B. A family of binary generating recurrences
C. A combinatorial setting for the sequence
9.2.2.4 ⊕ A closed form for the nth Fibonacci number
9.3 ⊕ Recurrences “in Action”: The Token Game
9.3.1 Rules of the Game
9.3.2 An Optimal Strategy for Playing the Game
9.3.3 ⊕ Analyzing the Recursive Strategy
9.4 Exercises: Chapter 9
Chapter 10 Numbers III: Operational Representations and
Their Consequences
10.1 Historical and Conceptual Introduction
10.2 Positional Number Systems
10.2.1 b-ary Number Systems
10.2.2 A Bijective Number System
10.3 Recognizing Integers and Rationals from Their Numerals
10.3.1 Positional Numerals for Integers
10.3.1.1 Horner’s Rule and fast numeral evaluation
10.3.1.2 Horner’s Rule and fast exponentiation
10.3.2 Positional Numerals for Rationals
10.4 Sets That Are Uncountable, Hence, “Bigger than” Z and Q
10.4.1 The Set of Binary Functions F Is Uncountable
10.4.1.1 Plotting a strategy to prove uncountability
A. Seeking a bijection g : N F
B. Every bijection “misses” some function from F
10.4.1.2 The denouement: There is no bijection h : N ↔ F
10.4.2 ⊕ R Is Uncountable
10.5 Scientific Notation
10.6 Exercises: Chapter 10
Chapter 11 The Art of Counting: Combinatorics, with
Applications to Probability and Statistics
11.1 The Elements of Combinatorics
11.1.1 Counting Binary Strings and Power Sets
11.1.2 Counting Based on Set Algebra
11.1.3 Counting Based on Set Arrangement and Selection
11.2 Introducing Combinatorial Probability via Examples
11.2.1 The Game of Poker: Counting Joint Events
11.2.2 The Monty Hall Puzzle: Conditional Probabilities
11.2.3 The Birthday Puzzle: Complementary Counting
11.2.4 Sum-of-Spots Dice Games: Counting with Complex Events
11.3 Probability Functions: Frequencies and Moments
11.3.1 Probability Frequency Functions
11.3.2 The (Arithmetic) Mean: Expectations
11.3.3 Additional Single-Number “Summarizations”
11.3.4 Higher Statistical Moments
11.4 The Elements of Empirical/Statistical Reasoning
11.4.1 Probability Distributions
11.4.1.1 The binomial distribution
11.4.1.2 Normal distributions; the Central Limit Theorem
11.4.1.3 Exponential distributions
11.4.2 A Historically Important Observational Experiment
11.4.3 The Law of Large Numbers
11.5 Exercises: Chapter 11
Chapter 12 Graphs I: Representing Relationships Mathematically
12.1 Generic Graphs: Directed and Undirected
12.1.1 The Basics of the World of Graphs
12.1.1.1 Locality-related concepts
12.1.1.2 Distance-related concepts
12.1.1.3 Connectivity-related concepts
12.1.2 Graphs as a Modeling Tool: The 2SAT Problem
12.1.3 Matchings in Graphs
12.2 Trees and Spanning Trees
12.3 Computationally Significant “Named” Graphs
12.3.1 The The Cycle-graphC n
12.3.2 The Complete graph (Clique) Kn
12.3.3 Sibling Networks: the Mesh (Mm;n); the Torus (fMm;n)
12.3.4 The (Boolean) Hypercube Qn
12.3.5 TheThe de Bruijn Network Dn
12.4 Exercises: Chapter 12
Chapter 13 Graphs II: Graphs for Computing and Communicating
13.1 Graph Coloring and Chromatic Number
13.1.2 Planar and Outerplanar Graphs
13.1.1 Graphs with Chromatic Number 2
13.1.2.2 On vertex-coloring planar graphs
A. On the Four-Color Theorem for planar graphs
B. The Six-Color Theorem for planar graphs
C.  The Five-Color Theorem for planar graphs
13.1.2.3 Two validations of Euler’s Formula
13.2 Pathand Cycle-Discovery Problems in Graphs
13.2.1 Eulerian Cycles and Paths
13.2.2 Hamiltonian Paths and Cycles/Tours
13.2.2.1 More inclusive notions of Hamiltonicity
13.2.2.2 Hamiltonicity in “named” graphs
13.2.2.3 Testing general graphs for Hamiltonicity
13.3 Exercises: Chapter 13
Appendix A A Cascade of Summations
A.1 Revisiting the Triangular Numbers Δn
A.2 Tetrahedral Numbers
A.2.1 An Algebraic Evaluation of b Θn
A.2.2 A Pictorial Evaluation of Θn
A.3 ⊕ Pentahedral Numbers
A.3.1 Can We Go Further?
Appendix B ⊕⊕ Pairing Functions: Encoding N+ X N+ as N+
B.1 A Shell-Based Methodology for Crafting Pairing Functions
B.2 The Square-Shell Pairing Function
B.3 ⊕ The Hyperbolic-Shell Pairing Function H
B.4 A Bijective Pairing Using Disjoint Arithmetic Progressions
Appendix C A Deeper Look at the Fibonacci Numbers
C.1 Elementary Computations on Fibonacci Numbers
C.1.1 Greatest Common Divisors of Fibonacci Numbers
C.1.2 Products of Consecutive Fibonacci Numbers
C.1.3 Cassini’s Identity
C.2 ⊕ Computing Fibonacci Numbers Fast
C.3 ⊕⊕ A Number System Based on the Fibonacci Sequence
C.3.1 The Foundations of the Number System
C.3.1.1 Zeckendorf’s Theorem
C.3.1.2 Proving Zeckendorf’s Theorem
C.3.2 Using Zeckendorf Numerals as a Number System
C.3.2.1 The system’s numerals
C.3.2.2 Observations about the system’s numerals
C.3.2.3 On incrementing Fibonacci numerals
Appendix D ⊕⊕ Lucas Numbers: Another
Recurrence-Defined Family
D.1 Definition
D.2 Relating the Lucas and Fibonacci Numbers
Appendix E ⊕⊕ Signed-Digit Numerals: Carry-Free
Addition
Appendix F ⊕⊕ The Diverse Delights of de Bruijn Networks
F.1 Cycles in de Bruijn Networks
F.2 de Bruijn Networks as “Escherian” Trees
Appendix G ⊕ Pointers to Applied Studies of Graphs
G.1 Graph Decomposition
G.2 Graphs Having Evolving Structure
G.3 Hypergraphs
G.4 Multigraphs and the Chinese Postman Problem
Appendix H Solution Sketches for ⊕⊕ Exercises
Appendix I
Lists of Symbols
Symbols Related to Sets and Their Algebras
Symbols Related to Logic
Symbols Related to Numbers and Arithmetic
Symbols Related to Combinatorics and Probability
References
Index