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