CS81 Topic Summaries

As an alternative source of information, this site provides summaries of many of the topics covered in lecture in a form more compact than the slides. The content will not be identical; sometimes it is easier to discuss something in a lecture than write it as a stand-alone piece, and sometimes the summaries may contain an alternative example or presentation to help give another perspective on a topic. Hopefully you will find both sources useful resources.

These summaries were originally developed and written by Prof. Stone when he taught CS81. Later, they were adapted by Prof. Wloka, Prof. Vidushi, and Prof. Bang, but Prof. Stone should receive primary credit for them (so if you like them, be sure to tell him how great they are when you see him! If you don't like them, you can blame it all on Prof. Bang!).

Use the navigation on the left (or the search bar above) to find a topic. The material is organized into seven parts:

1. Propositional Logic — propositions, truth tables, entailment, and natural deduction.
2. Predicate Logic — quantifiers and predicate-logic natural deduction.
3. Proofs — induction, quantified proofs, and asymptotic analysis.
4. Prolog — logic programming, unification, and search.
5. Logic Wrap-up — Hoare logic and countability.
6. Computability — automata, grammars, and Turing machines.
7. Computational Histories — encoding TM computations as strings.

An appendix covers the Post Correspondence Problem and a standalone Prolog demo file used in lecture.