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!).

List of Topics

1. Propositional Logic

  1. Introduction
  2. Propositions
  3. Truth and Falsehood
  4. Entailment
  5. Abbreviating WFFs
  6. English to WFFs
  7. Proof Systems
  8. Natural Deduction - Constructive Rules
  9. Natural Deduction - Classical Rules

2. Predicate Logic

  1. Predicate Logic
  2. Predicate Formulae
  3. Predicate Natural Deduction

3. Proofs

  1. Mathematical Induction
  2. Proofs for Humans
  3. Bounded Quantifiers
  4. Proving Implications
  5. Proofs with Quantifiers
  6. Asymptotic Analysis

4. Prolog

  1. Logic Programming
  2. Unification
  3. Depth-First Search
  4. Depth-First Consequences
  5. Generate and Test
  6. Prolog to English
  7. Lists in Prolog
  8. Arithmetic in Prolog
  9. Negation in Prolog

5. Logic Wrap-up

  1. Hoare Logic
  2. Countability
  3. Uncountable Sets

6. Computability

  1. Introduction to Computability
  2. String Theory
  3. State Machines
  4. Regular Languages
  5. Kleene’s Theorem
  6. Closure Properties
  7. Regular Expressions
  8. Non-Regular Languages
  9. Pumping Lemma
  10. CFLs
  11. CFGs
  12. Parsing
  13. Non-Context-Free Languages
  14. CYK Algorithm
  15. Regular Grammars
  16. Unrestricted Grammars
  17. Turing Machines
  18. Decidability and Undecidability
  19. Semidecidability
  20. Reductions
  21. Mapping Reductions