A Basis for Theoretical Computer Science

1 Sets, Maps, and Relations.- 1.1 Sets.- 1.2 Exponents and Series.- 1.3 Maps and Relations.- 2 Induction, Strings, and Languages.- 2.1 Induction on the Natural Numbers.- 2.2 The Strings Over an Arbitrary Set.- 2.3 Languages and Automata: A First Look.- 2.4 Context-Free Grammars.- 2.5 Processing Lists.- 3 Counting, Recurrences, and Trees.- 3.1 Some Counting Principles.- 3.2 Trees and Recurrences.- 3.3 An Example of Algorithm Analysis.- 4 Switching Circuits, Proofs, and Logic.- 4.1 Truth Tables and Switching Circuits.- 4.2 Proving Theorems.- 5 Binary Relations, Lattices, and Infinity.- 5.1 Equivalence Relations and Partial Orders.- 5.2 Lattices and Boolean Algebras.- 5.3 An Introduction to Infinity.- 5.4 Another Look at Trees.- 6 Graphs, Matrices, and Machines.- 6.1 An Invitation to Graph Theory.- 6.2 Graphs and Matrices.- 6.3 Finite-State Acceptors and Their Graphs.- Author Index.- Notation Index.