- CHAPTER 1 Set Theory
- 1.1Introduction
- 1.2Sets and Elements, Subsets
- 1.3Venn Diagrams
- 1.4Set Operations
- 1.5Algebra of Sets, Duality
- 1.6Finite Sets, Counting Principle
- 1.7Classes of Sets, Power Sets, Partitions
- 1.8Mathematical Induction
- SolvedProblems
- SupplementaryProblems
- CHAPTER 2 Relations
- 2.1Introduction
- 2.2Product Sets
- 2.3Relations
- 2.4Pictorial Representatives of Relations
- 2.5Composition of Relations
- 2.6Types of Relations
- 2.7Closure Properties
- 2.8Equivalence Relations
- 2.9Partial Ordering Relations
- SolvedProblems
- SupplementaryProblems
- CHAPTER 3 Functions and Algorithms
- 3.1Introduction
- 3.2Functions
- 3.3One-to-One, Onto, and Invertible Functions
- 3.4Mathematical Functions, Exponential and Logarithmic Functions
- 3.5Sequences, Indexed Classes of Sets
- 3.6Recursively Defined Functions
- 3.7Cardinality
- 3.8Algorithms and Functions
- 3.9Complexity of Algorithms
- SolvedProblems
- SupplementaryProblems
- CHAPTER 4 Logic and Propositional Calculus viii CONTENTS
- 4.1Introduction
- 4.2Propositions and Compound Statements
- 4.3Basic Logical Operations
- 4.4Propositions and Truth Tables
- 4.5Tautologies and Contradictions
- 4.6Logical Equivalence
- 4.7Algebra of Propositions
- 4.8Conditional and Biconditional Statements
- 4.9Arguments
- 4.10Propositional Functions, Quantifiers
- 4.11Negation of Quantified Statements
- SolvedProblems
- SupplementaryProblems
- CHAPTER 5 Techniques of Counting
- 5.1Introduction
- 5.2Basic Counting Principles
- 5.3Mathematical Functions
- 5.4Permutations
- 5.5Combinations
- 5.6The Pigeonhole Principle
- 5.7The Inclusion–Exclusion Principle
- 5.8Tree Diagrams
- SolvedProblems
- SupplementaryProblems
- CHAPTER 6 Advanced Counting Techniques, Recursion
- 6.1Introduction
- 6.2Combinations with Repetitions
- 6.3Ordered and Unordered Partitions
- 6.4Inclusion–Exclusion Principle Revisited
- 6.5Pigeonhole Principle Revisited
- 6.6Recurrence Relations
- 6.7Linear Recurrence Relations with Constant Coefficients
- Relations 6.8Solving Second-Order Homogeneous Linear Recurrence
- 6.9Solving General Homogeneous Linear Recurrence Relations
- SolvedProblems
- SupplementaryProblems
- CHAPTER 7 Probability
- 7.1Introduction
- 7.2Sample Space and Events
- 7.3Finite Probability Spaces
- 7.4Conditional Probability
- 7.5Independent Events
- 7.6Independent Repeated Trials, Binomial Distribution
- 7.7Random Variables
- 7.8Chebyshev’s Inequality, Law of Large Numbers CONTENTS ix
- SolvedProblems
- SupplementaryProblems
- CHAPTER 8 Graph Theory
- 8.1Introduction, Data Structures
- 8.2Graphs and Multigraphs
- 8.3Subgraphs, Isomorphic and Homeomorphic Graphs
- 8.4Paths, Connectivity
- 8.5Traversable and Eulerian Graphs, Bridges of Königsberg
- 8.6Labeled and Weighted Graphs
- 8.7Complete, Regular, and Bipartite Graphs
- 8.8Tree Graphs
- 8.9Planar Graphs
- 8.10Graph Colorings
- 8.11Representing Graphs in Computer Memory
- 8.12Graph Algorithms
- 8.13Traveling-Salesman Problem
- SolvedProblems
- SupplementaryProblems
- CHAPTER 9 Directed Graphs
- 9.1Introduction
- 9.2Directed Graphs
- 9.3Basic Definitions
- 9.4Rooted Trees
- 9.5Sequential Representation of Directed Graphs
- 9.6Warshall’s Algorithm, Shortest Paths
- 9.7Linked Representation of Directed Graphs
- 9.8Graph Algorithms: Depth-First and Breadth-First Searches
- 9.9Directed Cycle-Free Graphs, Topological Sort
- 9.10Pruning Algorithm for Shortest Path
- SolvedProblems
- SupplementaryProblems
- CHAPTER 10 Binary Trees
- 10.1Introduction
- 10.2Binary Trees
- 10.3Complete and Extended Binary Trees
- 10.4Representing Binary Trees in Memory
- 10.5Traversing Binary Trees
- 10.6Binary Search Trees
- 10.7Priority Queues, Heaps
- 10.8Path Lengths, Huffman’s Algorithm
- 10.9General (Ordered Rooted) Trees Revisited
- SolvedProblems
- SupplementaryProblems
- CHAPTER 11 Properties of the Integers x CONTENTS
- 11.1Introduction
- 11.2Order and Inequalities, Absolute Value
- 11.3Mathematical Induction
- 11.4Division Algorithm
- 11.5Divisibility, Primes
- 11.6Greatest Common Divisor, Euclidean Algorithm
- 11.7Fundamental Theorem of Arithmetic
- 11.8Congruence Relation
- 11.9Congruence Equations
- SolvedProblems
- SupplementaryProblems
- CHAPTER 12 Languages, Automata, Grammars
- 12.1Introduction
- 12.2Alphabet, Words, Free Semigroup
- 12.3Languages
- 12.4Regular Expressions, Regular Languages
- 12.5Finite State Automata
- 12.6Grammars
- SolvedProblems
- SupplementaryProblems
- CHAPTER 13 Finite State Machines and Turing Machines
- 13.1Introduction
- 13.2Finite State Machines
- 13.3Gödel Numbers
- 13.4Turing Machines
- 13.5Computable Functions
- SolvedProblems
- SupplementaryProblems
- CHAPTER 14 Ordered Sets and Lattices
- 14.1Introduction
- 14.2Ordered Sets
- 14.3Hasse Diagrams of Partially Ordered Sets
- 14.4Consistent Enumeration
- 14.5Supremum and Infimum
- 14.6Isomorphic (Similar) Ordered Sets
- 14.7Well-Ordered Sets
- 14.8Lattices
- 14.9Bounded Lattices
- 14.10Distributive Lattices
- 14.11Complements, Complemented Lattices
- SolvedProblems
- SupplementaryProblems
- CHAPTER 15 Boolean Algebra CONTENTS xi
- 15.1Introduction
- 15.2Basic Definitions
- 15.3Duality
- 15.4Basic Theorems
- 15.5Boolean Algebras as Lattices
- 15.6Representation Theorem
- 15.7Sum-of-Products Form for Sets
- 15.8Sum-of-Products Form for Boolean Algebras
- 15.9Minimal Boolean Expressions, Prime Implicants
- 15.10Logic Gates and Circuits
- 15.11Truth Tables, Boolean Functions
- 15.12Karnaugh Maps
- SolvedProblems
- SupplementaryProblems
- APPENDIX A Vectors and Matrices
- A.1Introduction
- A.2Vectors
- A.3Matrices
- A.4Matrix Addition and Scalar Multiplication
- A.5Matrix Multiplication
- A.6Transpose
- A.7Square Matrices
- A.8Invertible (Nonsingular) Matrices, Inverses
- A.9Determinants
- A.10Elementary Row Operations, Gaussian Elimination (Optional)
- A.11Boolean (Zero-One) Matrices
- SolvedProblems
- SupplementaryProblems
- APPENDIX B Algebraic Systems
- B.1Introduction
- B.2Operations
- B.3Semigroups
- B.4Groups
- B.5Subgroups, Normal Subgroups, and Homomorphisms
- B.6Rings, Internal Domains, and Fields
- B.7Polynomials Over a Field
- SolvedProblems
- SupplementaryProblems
- Index
martin jones
(Martin Jones)
#1