Discrete Mathematics

chapter i Sets and Statements i
*1-1 Statements 2
The Idea of a Statement ■ Symbolic Statements and Their
Compounds ■ Truth Sets and Equivalence
vl-2 Sets 14
Venn Diagrams and Set Operations ■ Set Operations and Logical
Connectives ■ Subsets
*-4-3 Determining the Truth of Symbolic Statements 27
Truth Tables ■ Circuits to Test the Truth of Statements
<4-4 The Conditional Connectives 37
Conditional Statements ■ Expressing Conditional Connectives in
Terms of Other Connectives
Vl-5 Boolean Algebra 46
Boolean Algebra for Sets ■ Boolean Algebra for Statements
chapter 2 Symbolic Logic 57
Truth and Equivalence ■ Implication
i/2-2 What Is a Proof? 67
Direct Proofs and Counter-Examples ■ Indirect Proofs
y 2-3 Predicate Logic 78
Quantifiers ■ Truth and Equivalence of Quantified Statements
chapter 3 Relations 93
*'3-1 Relations and Digraphs 94
Relations ■ Digraphs ■ Reachability ■ Transitivity
/3-2 Symmetric Relations jgg
Symmetric Relations and Graphs ■ Equivalence Relations
/ 3-3 Equivalence Classes and Congruence Classes J20
Equivalence Classes ■ Arithmetic Modulo m
3- 4 Partial Orderings ^29
Order Relations ■ Diagrams of Partial Orderings
CHAPTER 4 Functions 143
^/4-l Functions and Sequences 244
Functions ■ Properties of Functions ■ Sequences, n-tuples,
and Sums
t/4-2 Graphs and Operations on Functions 258
Cartesian Graphs ■ Composition and Inverses
4- 3 Growth Rates of Functions 275
Polynomial Time Algorithms ■ Order of Growth of Functions
chapter 5 The Principle of Mathematical Induction 191
t/5-l Proving Algebraic Statements by Induction 192
Mathematical Induction and Sum Formulas ■ Proving Inequalities
by Induction
G5-2 Other Applications of Induction 203
Strong Induction ■ Recursive Definition
5- 3 Applications of Induction in Computer Science 214
Recursive Algorithms in Computing ■ Using BNF Notation for
Recursive Definitions of Sets
chapter 6 Basic Counting Techniques 229
/6-1 Elementary Counting Techniques 230
Counting Principles ■ Counting Permutations and Functions
t/6-2 Applications of the Basic Counting Principles 240
Subsets ■ Decomposing Counting Problems
6- 3 Counting Equivalence Classes 253
Arrangements as Equivalence Classes ■ Ordered Distributions and
Multisets
6-4 The Binomial Theorem and Pascals Triangle 265
The Binomial Theorem ■ Pascal’s Triangle
6-5 The Principle of Inclusion and Exclusion 275
Inclusion-Exclusion Formulas and Venn Diagrams ■ The Principle of
Inclusion and Exclusion
CHAPTER 7
Recurrence Equations
291
7-1 First-Order Recurrences and Exponential Functions
Recurrence Equations ■ First-Order Linear Homogeneous
Recurrence Equations ■ Exponential Functions and Logarithms
292
7-2 First-Order Linear Recurrences
The Solution of First-Order Linear Recurrences ■ Recurrences from
Divide-and-Conquer Algorithms ■ Growth Rates of Solutions
308
7-3 Second-Order Linear Recurrences
Examples of Second-Order Recurrences ■ Second-Order Linear
Homogeneous Recurrences
323
CHAPTER 8
Trees and Spanning Trees
339
•'8-1 Trees and Spanning Trees
Trees ■ Spanning Trees
340
/ 8-2 Rooted Trees
The Concept of a Rooted Tree ■ Binary Trees
350
^8-3 Using Rooted Trees in Computing
Traversing Trees ■ Two-Three Trees
362
8-4 Minimizing Total Cost and Path Length in Spanning Trees
Minimum Total Weight Spanning Trees ■ Minimum Path Length
Spanning Trees
377
CHAPTER 9
Graphs
391
i/9-l Basic Concepts of Graph Theory
Graphs and Multigraphs ■ Isomorphism
392
9-2 Tours in Graphs
Eulerian Walks ■ Edge Tours ■ Vertex Tours
405
9-3 Coloring and Planarity
Intersection Graphs and Graph Coloring ■ Planarity
421
9-4 Digraphs and Machines
Machine Digraphs ■ Machines, Grammars, and Languages
432
CHAPTER 10
Matrix Algebra
453
10-1 Matrix Arithmetic
Sums and Numerical Products ■ Matrix Products
454
10-2 Matrices and Graphs 4QQ
Powers of Adjacency Matrices ■ Transitive Closure and Distances
10-3 Matrices and Systems of Linear Equations 479
Matrix Representations of Systems of Equations ® Row Reduced
Matrices ■ Solving Systems of Equations
10-4 Inverse and Elementary Matrices 495
Elementary Matrices ■ Inverse Matrices
10-5 The Definition of Determinants 507
The Determinant Axioms ■ Using the Rules to Compute
Determinants
10- 6 Properties of Determinants 519
Products and Transposes ■ The Additive Property ■ Row and
Column Expansions
chapter 11 The Elements of Probability 537
11- 1 The Basic Concepts 538
The Definition of Probability ■ The Uniform Measure ■
Properties of a Probability Measure
11-2 Conditional Probability and Independence 554
Conditional Probability ■ Independence
11-3 Random Variables 567
Random Variables ■ Expected Value ■ Independent Trials with
Two Outcomes
11-4 Measuring Differences from the Expected Value 586
Variance ■ Standard Deviation
11- 5 Markov Chains 597
Probability Graphs and Transition Matrices ■ Absorbing Chains
chapter 12 Abstract Algebra 613
12- 1 Groups 614
The Group Properties ■ Subgroups and Homomorphisms ■
Cosets
12-2 Rings 632
The Ring Properties ■ The Ring of Integers
12-3 Finite Fields and Error Correcting Codes 644
Parity Check Matrices ■ Hamming Codes
APPENDIX A An Accelerated Review of Sets, Functions, and Relations A1
APPENDIX B The Theory of Generating Functions A19
Suggested Reading A41
Answers A49
Index
A165
V