CS 81: Computability and Logic
Fall 2011

Course Staff

• Prof. Chris Stone,
• Joseph Dearden
• Sam Gray
• Sean Laguna
• Matt Johnson
• Bea Mititiri
• Matthew Toal

• Introduction; Structural Induction
• Propositional Logic, Natural Deduction
• Semantics of Propositional Logic
• Worksheet: Predicate Calculus Proofs (my version, with several of the proofs filled in!)
• Worksheet: Models of Predicate Calculus
• Worksheet: Tableau Proofs
• Worksheet: Sequent Calculus
• Prof. Keller's Slides on Resolution Theorem Proving
• Hoare Logic
• Worksheet: Cardinality
• Introduction to Computability
• Regular Languages
• More Regular Languages; Regular Expressions
• Closure Properties, Maze Theory, Non-regular Languages
• Context-Free Languages
• PDAs and Parsing
• Turing Machines
• Undecidability and Reductions
• Computability in Review
• TM Histories; Post Correspondence Problem

Handouts

• Syllabus

Homework Assignments

• Assignment 12: (Un)decidability
  • Due December 7
  • My LaTeX source
  • Sample solution on Sakai (after the due date).
  
  
• Assignment 11: Grammars and Turing Machines
  • Due November 23
  • My LaTeX source
  • Sample solution on Sakai.
  
  
• Assignment 10: Regular, Non-Regular, and Context-Free Languages
  • Due November 16
  • My LaTeX source
  • Sample solution on Sakai.
  
  
• Assignment 9: Regular Languages
  • Due November 9
  • My LaTeX source
  • Sample solution on Sakai.
  
  There is no Assignment 8
  
  
• Assignment 7: Temporal Logic and Cardinality
  • Due in class Wednesday, November 7.
  • Sample solution on Sakai.
  
  
• Assignment 6: Proving Programs
  • Due October 12
  • Sample solution on Sakai.
  • My (particularly terrible!) LaTeX source
  
  
• Assignment 5: Beyond Natural Deduction
  • Due October 5
  • Sample solution on Sakai.
  • My LaTeX source
  
  
• Assignment 4:
  • Sample solution on Sakai.
  • My LaTeX source
  
  
• Assignment 3:
  • Sample solution on Sakai.
  • My LaTeX source
  
  
• Assignment 2:
  • Sample solution on Sakai.
  • My LaTeX source
  • Two sets of LaTeX macros for proof boxes
  • The proof-with-boxes package that I've used (possibly the same as one of the above.)
  
  
• Assignment 1:
  • See the paper handout for MIU rules
  • My LaTeX source (won't typeset as-is).
  • Sample solution on Sakai.