PART 1 Fundamentals of Discrete Mathematics
1 Fundamental Principles of Counting
1.1 The Rules of Sum and Product
1.2 Permutations
1.3 Combinations: The BinomialTheorem
1.4 Combinations with Repetition
1.5 The Catalan Numbers (Optional)
1.6 Summary and HistoricalReview
2 Fundamentals of Logic
2.1 Basic Connectives and Truth Tables
2.2 LogicalEquivalence:The Laws ofLogic
2.3 Logicallmplication: Rules oflnference
2.4 The Use ofQuantifiers
2.5 Quantifiers, Definitions, and the Proofs of Theorems
2.6 Summary and HistoricalReview
3 SetTheory
3.1 Sets and Subsets
3.2 Set Operations and the Laws of Set Theory
3.3 Counting andVenn Diagrams
3.4 A First Word on Probability
3.5 TheAxioms ofProbability (Optional)
3.6 Conditional Probability: Independence (Optional)
3.7 Discrete Random Variables (Optional)
3.8 Summary and HistoricalReview
4 Properties of the Integers: Mathematicallnduction
4.1 The Well-Ordering Principle: Mathematicallnduction
4.2 RecursiveDefinions
4.3 The Division Algorithm: Prime Numbers
4.4 TheGreatestCommonDivisor:TheEuclideanAlgorithm
4.5 The FundamentalTheorem ofArithmetic
4.6 Summary and HistoricalReview
5 Relations and FunCtions
5.1 Cartesian Ptoducts and Relations
5.2 Functions: Plain and One-to-One
5.3 Onto Functions: Stirling Numbers ofthe Second Kind
5.4 SpecialFunctions
5.5 The Pigeonhole Principle
5.6 Function Composition andlnverse Functions
5.7 ComputationalComplexity
5.8 AnalysisofAlgorithms
5.9 Summary and HistoricalReview
6 Languages: Finite State Machines
6.1 Language:TheSetTheoryofStrings
6.2 Finite State Machines: A First Encounter
6.3 Firute State Machines: A Second Encounter
6.4 Summary and HistoricalReview
7 Relations:The Second Time Around
7.1 Relations Revisited: Properties ofRelations
7.2 Computer Recognition: Zero-One Matrices and Directed Graphs
7.3 artialOrders: Hasse Diagrams
7.4 Equivalence Relations and Partitions
7.5 Finite State Machines: The Minimization Process
7.6 Summary and HistoricaIReview
PART 2 Further Topics in Enumeration
8 The Prinaple of Inclusion and Exclusion
8.1 The Principle oflnclusion and Exclusion
8.2 Generalizations ofthe Principle
8.3 Derangements:NothingIsinltsRightPlace
8.4 RookPolynomials
8.5 Arrangements with Forbidden Positions
8.6 Summary and HistoricaIReview
……
PART 3 Graph Theory and Applications
PART 4 Modern Applied Algebra
Appendixl ExponentialandLogarithmicFunctions A-1
Appendix2 Matrices,MatrixOperations,andDeterminants A-11
Appendix 3 Countable and Uncountable Sets A-23
Solutions S-1