Discrete Mathematics (Revised Edition)

Author: Yin Baolin He Qiangxiu Xu Guanghan
Publisher:
Publish Date: 2004-07-30
Features: Number of Chapters on Logic
Chapter 1 Propositional Logic
§1.1 Propositions and Connectives
§1.2 Formulas and Truth Assignments
§1.3 Equivalence Calculus
§1.4 Duality Theorem
§1.5 Complete Sets of Connectives
§1.6 Normal Forms
§1.7 Logical Inference
Exercises 1
Chapter 2 Predicate Logic
§2.1 Predicates and Quantifiers
§2.2 Terms and Formulas
§2.3 Interpretations and Assignments
§2.4 Tautologies
§2.5 Equivalence Calculus
§2.6 Logical Inference
Exercises 2
Chapter 3 Axiomatic Systems
§3.1 Axiomatic System for Propositional Logic
§3.2 Axiomatic System for Predicate Logic
Exercises 3
Chapter 4 Resolution Principles
§4.1 Resolution for Propositional Logic
§4.2 Precedent Normal Forms and Skolem Normal Forms
§4.3 Resolution for Predicate Logic
Exercises 4
References
Part II Set Theory
Chapter 5 Basic Concepts and Operations of Sets
§5.1 Sets and Elements
§5.2 Equality and Subset Relations Between Sets
§5.3 Power Sets
§5.4 Operations on Sets
§5.5 Counting Principles for Finite Sets
§5.6 Inductive Definition of Sets
§5.7 Ordered Pairs and Cartesian Products
Exercises 5
Chapter 6 Relations
§6.1 Relations and Their Properties
§6.2 Operations on Relations
§6.3 Partial Order Relations
§6.4 Equivalence Relations, Partitions, and Others
Exercises 6
Chapter 7 Functions
§7.1 Basic Concepts
§7.2 Composition of Functions
§7.3 Functions with Special Properties
§7.4 Characteristic Functions of Sets
Exercises 7
Chapter 8 Natural Numbers and Cardinalities
§8.1 Natural Numbers and Mathematical Induction
§8.2 Cardinalities
Exercises 8
References
Part III Graph Theory
Chapter 9 Basic Concepts
§9.1 Directed and Undirected Graphs
§9.2 Basic Structure of Graphs
§9.3 Subgraphs
§9.4 Connectivity
§9.5 Vertex Basis and Strongly Connected Components
Exercises 9
Chapter 10 Path Problems
§10.1 Short Paths
§10.2 Critical Paths
Exercises 10
Chapter 11 Matrix Representation of Graphs
§11.1 Adjacency Matrix
§11.2 Reachability Matrix for Directed Graphs
§11.3 Incidence Matrix
Exercises 11
Chapter 12 Trees
§12.1 General Definition of Trees
§12.2 Rooted Trees and Ordered Trees
§12.3 Binary Trees
§12.4 Spanning Trees
§12.5 Cuts
Exercises 12
Chapter 13 Eulerian and Hamiltonian Graphs
§13.1 Eulerian Graphs
§13.2 Hamiltonian Graphs
Exercises 13
Chapter 14 Matching Problems in Bipartite Graphs
§14.1 Basic Concepts
§14.2 Maximum Matching in Bipartite Graphs
§14.3 Matching from X to Y
Exercises 14
Chapter 15 Planar Graphs and Chromatic Numbers
§15.1 Planar Graphs
§15.2 Chromatic Numbers
Exercises 15
References
Part IV Algebraic Systems
Chapter 16 Basic Concepts
§16.1 Algebraic Systems
§16.2 Homomorphisms and Isomorphisms
§16.3 Subalgebras and Quotient Algebras
Exercises 16
Chapter 17 Semigroups and Groups
§17.1 Concept of Semigroups
§17.2 Subsemigroups and Semigroup Homomorphisms
§17.3 Quotient Semigroups and Semigroup Direct Products
§17.4 Concept of Groups
§17.5 Subgroups and Group Homomorphisms
§17.6 Transformation Groups, Permutation Groups, and Cyclic Groups
§17.7 Invariant Subgroups and Quotient Groups
Exercises 17
Chapter 18 Rings and Fields
§18.1 Concepts of Rings and Fields
§18.2 Subrings and Ring Homomorphisms
§18.3 Ideals and Quotient Rings
Exercises 18
Chapter 19 Lattices and Boolean Algebras
§19.1 Definition and Basic Properties of Lattices
§19.2 Sublattices and Lattice Homomorphisms
§19.3 Boolean Algebras
§19.4 Representation of Boolean Algebras
Exercises 19
Chapter 20 Algebraic Specifications of Abstract Data Types
§20.1 Labels, Terms, and Algebraic Specifications
§20.2 Algebras and Categories
§20.3 Initial Semantics of Algebraic Specifications
Exercises 20
References
Part V Finite Automata Theory
Chapter 21 Basic Concepts
§21.1 Alphabet, Strings, and Operations on Sets of Strings
§21.2 Definition of Finite Automata
§21.3 Equivalence of Finite Automata
§21.4 Mealy Machines and Moore Machines
Exercises 21
Chapter 22 Simplification of Finite Automata
§22.1 Definition and Properties of Minimal Finite Automata
§22.2 S-Divisions of State Sets and Lattice LM
§22.3 Minimization of Finite Automata
Exercises 22
Chapter 23 Finite Automata and Regular Expressions
§23.1 Recognition Function of Finite Automata
§23.2 Nondeterministic Finite Automata
§23.3 Regular Expressions
§23.4 Algorithms for Constructing FA from Regular Expressions
§23.5 Equivalence of Finite Automata and Regular Expressions
§23.6 Regular Sets and Their Properties
Exercises 23
Chapter 24 Synthesis and Applications of Finite Automata
§24.1 Synthesis of Finite Automata
§24.2 Applications of FA Theory in Algorithm Design
§24.3 Relationship Between FA Theory and Formal Language Theory
Exercises 24
References