MATHEMATICAL STRUCTURES FOR COMPUTER SCIENCE: A MODERN APPROACH TO DISCRETE MATHEMATICS 6/E

Computing Curricula 2001 (CC2001), a joint undertaking of the Institute for Electrical and Electronic Engineers/Computer Society (IEEE/CS) and the Association for Computing Machinery (ACM), identifies the essential material for an undergraduate degree in computer science. This Sixth Edition of Mathematical Structures for Computer Science covers all the topics in the CC2001 suggested for a one-semester intensive discrete structures course, and virtually everything suggested for a two-semester version of a discrete structures course. Gersting's text binds together what otherwise appears to be a collection of disjointed topics by emphasizing the following themes: 1.Importance of logical thinking2.Power of mathematical notation3.Usefulness of abstractions

Preface
Note to the Student

1. Formal Logic
1.1 Statements, Symbolic Representation, and Tautologies
1.2 Propositional Logic
1.3 Quantifiers, Predicates, and Validity
1.4 Predicate Logic
1.5 Logic Programming
1.6 Proof of Correctness

2. Proofs, Recursion, and Analysis of Algorithms
2.1 Proof Techniques
2.2 Induction
2.3 More on Proof of Correctness
2.4 Recursive Definitions
2.5 Recurrence Relations
2.6 Analysis of Algorithms

3. Sets, Combinatorics, Probability, and Number Theory
3.1 Sets
3.2 Counting
3.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
3.4 Permutations and Combinations
3.5 Probability
3.6 Binomial Theorem
3.7 Number Theory

4. Relations, Functions, and Matrices
4.1 Relations
4.2 Topological Sorting
4.3 Relations and Databases
4.4 Functions
4.5 The Mighty Mod Function
4.6 Matrices

5. Graphs and Trees
5.1 Graphs and their Representations
5.2 Trees and their Representations
5.3 Decision Trees
5.4 Huffman Codes

6. Graph Algorithms
6.1 Directed Graphs and Binary Relations; Warshall's Algorithm
6.2 Euler Path and Hamiltonian Circuit
6.3 Shortest Path and Minimal Spanning Tree
6.4 Traversal Algorithms
6.5 Articulation Points and Computer Networks

7. Boolean Algebra and Computer Logic
7.1 Boolean Algebra Structure
7.2 Logic Networks
7.3 Minimization

8. Modeling Arithmetic, Computation, and Languages
8.1 Algebraic Structures
8.2 Finite-State Machines
8.3 Turing Machines
8.4 Formal Languages

Appendixes
Appendix A Derivation Rules for Propositional and Predicate Logic
Appendix B Summation Notation
Appendix C The Logarithm Function
Answers to Practice Problems
Answers to Selected Exercises
Answers to Self-Tests
Index