Table of Contents
PART 1. FUNDAMENTALS OF DISCRETE MATHEMATICS.
1. Fundamental Principles of Counting.
The Rules of Sum and Product.Permutations.Combinations: The
Binomial Theorem.Combinations with Repetition.The Catalan Numbers
(Optional).Summary and Historical Review.
2. Fundamentals of
Logic.
Basic Connectives and Truth Tables.Logical Equivalence: The Laws of
Logic.Logical Implication: Rules of Inference.The Use of
Quantifiers.Quantifiers, Definitions, and the Proofs of
Theorems.Summary and Historical Review.
3. Set Theory.
Sets and Subsets.Set Operations and the Laws of Set Theory.Counting
and Venn Diagrams.A First Word on Probability.The Axioms of
Probability (Optional).Conditional Probability: Independence
(Optional).Discrete Random Variables (Optional).Summary and
Historical Review.
4. Properties of the Integers: Mathematical
Induction.
The Well-Ordering Principle: Mathematical Induction.Recursive
Definitions.The Division Algorithm: Prime Numbers.The Greatest
Common Divisor: The Euclidean Algorithm.The Fundamental Theorem of
Arithmetic.Summary and Historical Review.
5. Relations and
Functions.
Cartesian Products and Relations.Functions: Plain and
One-to-One.Onto Functions: Stirling Numbers of the Second
Kind.Special Functions.The Pigeonhole Principle.Function
Composition and Inverse Functions.Computational Complexity.Analysis
of Algorithms.Summary and Historical Review.
6. Languages: Finite
State Machines.
Language: The Set Theory of Strings.Finite State Machines: A First
Encounter.Finite State Machines: A Second Encounter.Summary and
Historical Review.
7. Relations: The Second Time Around.
Relations Revisited: Properties of Relations.Computer Recognition:
Zero-One Matrices and Directed Graphs.Partial Orders: Hasse
Diagrams.Equivalence Relations and Partitions.Finite State
Machines: The Minimization Process.Summary and Historical Review.
PART 2. FURTHER TOPICS IN ENUMERATION.
8. The Principle of Inclusion and Exclusion.
The Principle of Inclusion and Exclusion.Generalizations of the
Principle.Derangements: Nothing Is in Its Right Place.Rook
Polynomials.Arrangements with Forbidden Positions.Summary and
Historical Review.
9. Generating Functions.
Introductory Examples.Definition and Examples: Calculational
Techniques.Partitions of Integers.The Exponential Generating
Functions.The Summation Operator.Summary and Historical
Review.
10. Recurrence Relations.
The First-Order Linear Recurrence Relation.The Second-Order Linear
Homogeneous Recurrence Relation with Constant Coefficients.The
Nonhomogeneous Recurrence Relation.The Method of Generating
Functions.A Special Kind of Nonlinear Recurrence Relation
(Optional).Divide and Conquer Algorithms.Summary and Historical
Review.
PART 3. GRAPH THEORY AND APPLICATIONS.
11. An Introduction to Graph Theory.
Definitions and Examples.Subgraphs, Complements, and Graph
Isomorphism.Vertex Degree: Euler Trails and Circuits.Planar
Graphs.Hamilton Paths and Cycles.Graph Coloring and Chromatic
Polynomials.Summary and Historical Review.
12. Trees.
Definitions, Properties, and Examples.Rooted Trees.Trees and
Sorting.Weighted Trees and Prefix Codes.Biconnected Components and
Articulation Points.Summary and Historical Review.
13.
Optimization and Matching.
Dijkstra's Shortest Path Algorithm.Minimal Spanning Trees: The
Algorithms of Kruskal and Prim.Transport Networks: The Max-Flow
Min-Cut Theorem.Matching Theory.Summary and Historical Review.
PART 4. MODERN APPLIED ALGEBRA.
14. Rings and Modular Arithmetic.
The Ring Structure: Definition and Examples.Ring Properties and
Substructures.The Integers Modulo n. Cryptology.Ring Homomorphisms
and Isomorphisms: The Chinese Remainder Theorem.Summary and
Historical Review.
15. Boolean Algebra and Switching
Functions.
Switching Functions: Disjunctive and Conjunctive Normal
Forms.Gating Networks: Minimal Sums of Products: Karnaugh
Maps.Further Applications: Don't-Care Conditions.The Structure of a
Boolean Algebra (Optional).Summary and Historical Review.
16.
Groups, Coding Theory, and Polya's Theory of Enumeration.
Definition, Examples, and Elementary Properties.Homomorphisms,
Isomorphisms, and Cyclic Groups.Cosets and Lagrange's Theorem.The
RSA Cipher (Optional).Elements of Coding Theory.The Hamming
Metric.The Parity-Check and Generator Matrices.Group Codes:
Decoding with Coset Leaders.Hamming Matrices.Counting and
Equivalence: Burnside's Theorem.The Cycle Index.The Pattern
Inventory: Polya's Method of Enumeration.Summary and Historical
Review.
17. Finite Fields and Combinatorial Designs.
Polynomial Rings.Irreducible Polynomials: Finite Fields.Latin
Squares.Finite Geometries and Affine Planes.Block Designs and
Projective Planes.Summary and Historical
Review.
Appendices.
Exponential and Logarithmic Functions.Matrices, Matrix Operations,
and Determinants.Countable and Uncountable
Sets.
Solutions.
Index.