Foundations of Computation is a free online theoretical computer science textbook. It was written by Carol Critchlow and David Eck, members of the Department of Mathematics and Computer Science at Hobart and William Smith Colleges.
This textbook has been used for a number of years by students at Hobart and William Smith Colleges. The first half of textbook could be used for a course in discrete mathematics. It covers logic, sets and functions. The second half could be used for an upper level course in theoretical computer science. It covers topics such as automata, formal languages and grammar.
The authors offer three versions of their textbook. One is a 6X9 inch version in PDF form with 256 pages designed for viewing on a computer screen. The second version of this theoretical computer science textbook is a downloadable PDF designed for printing all 223 pages. Or, students can purchase a soft-cover edition from Lulu.
Chapters of Foundations of Computation Online Textbook
1 Logic and Proof
1.1 Propositional Logic
1.10 Recursive Definitions
1.2 Boolean Algebra
1.3 Application: Logic Circuits
1.4 Predicates and Quantifiers
1.5 Deduction
1.6 Proof
1.7 Proof by Contradiction
1.8 Mathematical Induction
1.9 Application: Recursion and Induction
2 Sets, Functions, and Relations
2.1 Basic Concepts
2.2 The Boolean Algebra of Sets
2.3 Application: Programming with Sets
2.4 Functions
2.5 Application: Programming with Functions
2.6 Counting Past Infinity
2.7 Relations
2.8 Application: Relational Databases
3 Regular Expressions and FSA’s
3.1 Languages
3.2 Regular Expressions
3.3 Application: Using Regular Expressions
3.4 Finite-State Automata
3.5 Nondeterministic Finite-State Automata
3.6 Finite-State Automata and Regular Languages
3.7 Non-regular Languages
4 Grammars
4.1 Context-free Grammars
4.2 Application: BNF
4.3 Parsing and Parse Trees
4.4 Pushdown Automata
4.5 Non-context-free Languages
4.6 General Grammars
5 Turing Machines and Computability
5.1 Turing Machines
5.2 Computability
5.3 The Limits of Computation
View this Free Online Material at the source:
Foundations of Computation
