Logic and Language Models for Computer Science

Contents
Preface
	Preface to the Second Edition
	Preface to the Third Edition
	Preface to the Fourth Edition
About the Author
1 Mathematical Preliminaries
	1.1. Sets and Sequences
	1.2. Relations and Functions
	1.3. Operators and Their Algebraic Properties
	1.4. Set Operators
	1.5. Strings and String Operators
	1.6. Expressions
	1.7. Growth Rates of Functions
	1.8. Graphs and Trees
	Exercises
Part I Logic for Computer Science
	Introduction to Part I: Logic for Computer Science
	2 Propositional Logic
		2.1. Propositions
		2.2. Boolean Expressions
		2.3. States, Operators and Semantics
		2.4. Propositions as Functions
		2.5. Laws of Propositional Logic
		2.6. Two Important Operators
		2.7. Normal Forms
		2.8. Logic Circuits
		Exercises
	3 Proofs by Deduction
		3.1. Reasons for Wanting to Prove Things
		3.2. Natural Deduction Proofs
		3.3. A Very Formal Approach
		3.4. Rules of Inference
		3.5. Proof by Rules
		3.6. Assumptions
		3.7. A Larger Set of Rules
		3.8. Examples
		3.9. Types of Theorems and Proof Strategies
		3.10. Soundness and Completeness
		Exercises
	4 Predicate Logic
		4.1. Predicates and Functions
		4.2. Predicates, English, and Sets
		4.3. Quantifiers
		4.4. Quantification and Formal Definitions
		4.5. Examples from Data Structures
		Exercises
	5 Proofs with Predicates
		5.1. Inference Rules with Predicates
		5.2. Proof Strategies with Predicates
		5.3. Applying Logic to Mathematics
		5.4. Mathematical Induction
		5.5. Examples of Mathematical Induction
		5.6. Limits of Logic
		Exercises
	6 Program Verification
		6.1. The Idea of Verification
		6.2. Definitions
		6.3. Inference Rules
		6.4. Loop Invariants
		6.5. Examples of Search
		6.6. Proofs with Procedures
		6.7. Loop Invariants and Tail Recursion
		6.8. The Debate About Formal Verification
Part II Language Models for Computer Science
	Introduction to Part II: Language Models for Computer Science
	7 Language and Models
		7.1. Programming Languages and Computer Science
		7.2. Formal Languages
		7.3. Language Operators
		7.4. Two Views of Alphabets and Language
		7.5. Questions in Formal Language Theory
		7.6. Generative Models
		7.7. Non-determinism: The General Idea
		Exercises
	8 Generating Regular Languages
		8.1. Regular Languages
		8.2. Regular Expressions
		8.3. Grammars: The General Idea
		8.4. Regular Grammars
		8.5. A Bridging Model
		8.6. Deterministic Regular Grammars
		8.7. REs and Non-determinism
		8.8. Summary
		Exercises
	9 Finite Automata
		9.1. Finite Automata: The General Idea
		9.2. Diagrams and Recognition
		9.3. Formal Notation for Finite Automata
		9.4. Relationship to Regular Languages
		9.5. Non-deterministic Finite Automata
		9.6. Properties of Regular Languages
		9.7. Limitations of Regular Languages
		9.8. Pattern Matching
		9.9. Designing Finite Automata
		9.10. Digital Logic and Automata
		Exercises
	10 Context-Free Grammars
		10.1. Introduction to Context-Free Grammars
		10.2. An Example
		10.3. Structure, Meaning and Ambiguity
		10.4. Chomsky Normal Form
		10.5. Greibach Normal Form
		10.6. Beyond Context-Free Languages
		10.7. The Role of the Empty String
		Exercises
	11 Pushdown Automata and Parsing
		11.1. Motivating PDAs
		11.2. Standard Notation for PDAs
		11.3. From CFG to NPDA
		11.4. From NPDA to CFG
		11.5. Parsing
		11.6. DPDAs and Parsing
		11.7. A Variation of the PDA Model
		11.8. Limitations on DPDAs
		11.9. More on Parsing
		11.10. Notes on Memory
		Exercises
	12 Turing Machines
		12.1. Unrestricted Grammars
		12.2. The Turing Machine Model
		12.3. Infinite Sets
		12.4. Universal Turing Machines
		12.5. Limits on Turing Machines
		12.6. Undecidability
		12.7. Church–Turing Thesis
		12.8. Computational Complexity
		Exercises
Appendix A: Logic Programming
	A.1. Prolog and its Relation to Logic
	A.2. Getting Started Using Prolog
	A.3. An Example Related to Databases
	A.4. The Form and Limitations of Prolog
	A.5. How Prolog Works
	A.6. Structures
	A.7. Lists and Recursion
	A.8. Built-In Predicates and Operators
	A.9. Finite Automata in Prolog
	A.10. Pushdown Automata in Prolog
	Exercises
Appendix B: The AWK Language
	B.1. Overview of AWK
	B.2. Writing Expressions
	B.3. Writing Regular Expressions
	B.4. Writing Patterns
	B.5. Writing Actions
	B.6. Using Arrays
	B.7. Sample Programs
	B.8. Using AWK in Unix
	B.9. An Example
Answers to Selected Problems
	Chapter 1: Mathematical Preliminaries
	Chapter 2: Propositional Logic
	Chapter 3: Proofs by Deduction
	Chapter 4: Predicate Logic
	Chapter 5: Proofs with Predicates
	Chapter 6: Program Verification
	Chapter 7: Language and Models
	Chapter 8: Generating Regular Languages
	Chapter 9: Finite Automata
	Chapter 10: Context-Free Grammars
	Chapter 11: Pushdown Automata and Parsing
	Chapter 12: Turing Machines
	Appendix A: Logic Programming
Bibliography
Index