Discrete Mathematics in Computer Science

CONTENTS
PREFACE
	Notation
0: MATHEMATICAL MODELS
	0.0: Introduction
	0.1: Principles and Models
	0.2: Mathematical Models
	0.3: Purposes of Models
1: MATHEMATICAL REASONING
	1.0: Introduction
	1.1: Propositions
	1.2: Predicates and Quantifiers
	1.3: Quantifiers and Logical Operators
	1.4: Logical Inference
	1.5: Methods of Proof
	1.6: Program Correctness
		Axioms of Assignment
2: SETS
	2.0: Introduction
	2.1: The Primitives of Set Theory
	2.2: The Paradoxes of Set Theory
	2.3: Relations Between Sets
	2.4: Operations on Sets
	2.5: Induction
		Inductive Definition of Sets
		Recursive Procedures
		Inductive Proofs
	2.6: The Natural Numbers
	2.7: Set Operations on ∑
3: BINARY RELATIONS
	3.0: Introduction
	3.1: Binary Relations and Digraphs
	3.2: Trees
		Search Trees
		Tree Traversal Algorithms
	3.3: Special Properties of Relations
	3.4: Composition of Relations
	3.5: Closure Operations on Relations
	3.6: Order Relations
		Some Additional Concepts for Posets
	3.7: Equivalence Relations and Partitions
		Sums and Products of Partitions
4: FUNCTIONS
	4.0: Introduction
	4.1: Basic Properties of Functions
		Inductively Defined Functions
		Partial Functions
	4.2: Special Classes of Functions
		Inverse Functions
		One-Sided Inverse Functions
5: COUNTING AND ALGORITHM ANALYSIS
	5.0: Introduction
	5.1: Basic Counting Techniques
		Permutations and Combinations
		Decision Trees
	5.2: Asymptotic Behavior of Functions
		Some Important Classes of Asymptotic Behavior
	5.3: Recurrence Systems
		Divide and Conquer Algorithms
	5.4: Analysis of Algorithms
		Searching Algorithms
		Sorting Algorithms
6: INFINITE SETS
	6.0: Introduction
	6.1: Finite and Infinite Sets
	6.2: Countable and Uncountable Sets
	6.3: Comparison of Cardinal Numbers
	6.4: Cardinal Arithmetic
7: ALGEBRAS
	7.0: Introduction
	7.1: The Structure of Algebras
	7.2: Some Varieties of Algebras
		Semigroups
		Monoids
		Groups
		Boolean Algebras
	7.3: Homomorphisms
	7.4: Congruence Relations
	7.5: New Algebraic Systems from Old
		Quotient Algebras
		Product Algebras
APPENDIX: THE PROGRAMMING LANGUAGE
ANSWERS TO SELECTED EXERCISES
BIBLIOGRAPHY
INDEX